Algorithms Coded in Java

Problem : Design a stack of Numbers which will give you the minimum and maximum of all the elements it contains. This problem is also known as MinStack or MaxStack problem which expects you to find only the minimum or maximum. It is restated here to capture both. A stack typically has push(), pop() and size() operations. In order to find the minimum and the maximum, we will need to iterate over the elements of the stack each time we want to find the minimum and maximum. This will result in O (n) time complexity. And typically stack does not let us iterate over the elements. Many do not know that the java.util.Stack implementation does allow it as it extends java.util.Vector. We can make it more efficient by storing the minimum and maximum as instance variables in our stack and update them when ever we push a new number on to the stack. This will result in O(1) complexity for updating the max and min when pushing new numbers on stack, but when we pop the number which is currently set a...

Problem : Given a number, can you find out how many trailing zeroes are there in the factorial of that number. This is an interesting problem. One solution to this problem is to find the factorial of the given number and then count the trailing zeroes. Here is the code for this -  /** * This will find the number of trailing zeroes * in the factorial of a number. * * @param n * @return int */ public static int trailingZeroesInFactorial(int n) { BigInteger factorial = factorial(n); String string = factorial.toString(); int trailingZeroCount = 0; for (int i = string.length() - 1; i >= 0; i--) { if (string.charAt(i) == '0') { trailingZeroCount++; } else { break; } } return trailingZeroCount; } There is another solution to this problem where in we do not need to find the factorial of the given number in order to find the number ...

Problem: Given an iterator of iterators, can you give me back an iterator which flattens the given iterator. Ex : Suppose you are given an iterator which has these objects - "1", "2", "3", , , then the flattened iterator returned by you should have "1", "2", "3", "4", "5", "6", "7", "8", "9". Iterators may be nested to any level. This problem can be solved by implementing a FlattenIterator which takes in the given iterator as an agrument in the constructor and delegating the hasNext() and next() calls to the given iterator using a stack. The given iterator is pushed on to the stack. Nested iterators are pushed on to the stack before traversing and once there are no more elements in the iterator, it is popped from the stack. Here is the code - import java.util.*; /** * User: blogkoder * Date: Jul 28, 2008 * Time: 9:32:39 PM */ public class FlattenIterator implement...

Problem : Given an iterator of integers, can you give me back another iterator which iterates over the given iterator of integers such that the new iterator gives only even integers. There a couple of different ways to solve this problem. * The first option is to create a new list of integers and add only the even integers from the given iterator and then return an iterator by calling list.iterator(). This has a time complexity of O (n) but also has a space complexity of O (n) in the worst case, which is not desirable. Here is the code for it - public static Iterator<Integer> giveEvenIntegersIterator(Iterator<Integer> iterator) { List<Integer> evenIntegers = new ArrayList<Integer>(); if (iterator != null) { while(iterator.hasNext()) { Integer number = iterator.next(); if (number != null && number % 2 == 0) { evenIntegers.add(number); } } } retu...

Problem : Given a number, determine if it is prime or not. To determine if a given number is prime or not, you have to check if the given number is divisible by any number other than 1 and itself. If it is, then it is not a prime number.  * In this algorithm, we check if the given number is less than or equal to zero. If it is then it is not a prime number.  * Next we check to see if the given number is 2.  2 is the only even prime number.  * Then we check if the given number is even. If it is, then it is not a prime number.  * Lastly we divide the given number starting from 3 till the square root of the given number.     /**      * This method checks if the given number n is a prime number or not.      *      * @param n - The number to be checked.      * @return boolean      */     public static boolean isPrime(int n)     {         if (n         {             return false;         }         if (n == 2)         {             return true;         }         if (n % 2 == 0)         {     ...