Shuffle a deck of 52 cards and shuffle them equally to 4 players.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;
/*
 * Write the code to shuffle a deck of 52 cards,
 * and shuffle them equally to 4 players
 */
class Card {
  public enum Rank {
        DEUCE, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING, ACE
    }
    public enum Suit {
        CLUBS, DIAMONDS, HEARTS, SPADES
    }
    private final Rank rank;
    private final Suit suit;
    private Card(Rank rank, Suit suit) {
        this.rank = rank;
        this.suit = suit;
    }
    public Rank rank() {
        return rank;
    }
    public Suit suit() {
        return suit;
    }
    public String toString() {
        return rank + " of " + suit;
    }
    private static final List<Card> protoDeck = new ArrayList<Card>();
    // Initialize prototype deck
    static {
        for (Suit suit : Suit.values())
            for (Rank rank : Rank.values())
                protoDeck.add(new Card(rank, suit));
    }
    public static ArrayList<Card> newDeck() {
        return new ArrayList<Card>(protoDeck); // Return copy of prototype deck
    }
}
public class RandomCards {
    private Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
    public RandomCards() {
    }
    public static void main(String[] args) {
        ArrayList<Card> player1 = new ArrayList<Card>();
        ArrayList<Card> player2 = new ArrayList<Card>();
        ArrayList<Card> player3 = new ArrayList<Card>();
        ArrayList<Card> player4 = new ArrayList<Card>();
 
        ArrayList<Card> deck = Card.newDeck();
        Random random = new Random();
        int j = 1;
        for (int i = 0; i < 52; i++) {
            int temp = random.nextInt(52);
            if (j == 1) {
                player1.add(deck.get(i));
                j++;
                continue;
            } else if (j == 2) {
                player2.add(deck.get(i));
                j++;
                continue;
            } else if (j == 3) {
                player3.add(deck.get(i));
 
                j++;
                continue;
            } else if (j == 4) {
                player4.add(deck.get(i));
                j = 1;
                continue;
            }
        }
        System.out.println(" Player 1 " + player1);
        System.out.println(" Player 2 " + player2);
        System.out.println(" Player 3 " + player3);
        System.out.println(" Player 4 " + player4);
    }
}

Longest palindrome in a string

The best approach is that from the mid of any palindrome, if we go to right and left by 1 place, it’s always same character. For example 12321, here mid is 3 and if we keep moving one position in both sides, we get 2 and then 1.
We will use the same logic in our java program to find out the longest palindrome.
However if the palindrome length is even, the mid size is also even, so we need to make sure in our program that this is also checked, for example 12333321, here mid is 33 and if we keep moving one position in both sides, we get 3, 2 and 1.

public class LongestPalindromeFinder {
 
    public static void main(String[] args) {
        System.out.println(longestPalindromeString("1234"));
        System.out.println(longestPalindromeString("12321"));
        System.out.println(longestPalindromeString("9912321456"));
        System.out.println(longestPalindromeString("9912333321456"));
        System.out.println(longestPalindromeString("12145445499"));
    }
 
    /**
     * This method returns the longest palindrome in the input String
     * 
     * @param in
     * @return
     */
    public static String longestPalindromeString(String in) {
        char[] input = in.toCharArray();
        int longestPalindromeStart = 0;
        int longestPalindromeEnd = 0;
 
        for (int mid = 0; mid < input.length; mid++) {
            // for odd palindrom case like 12321, 3 will be the mid
            int left = mid-1;
            int right = mid+1;
            // we need to move in the left and right side by 1 place till they reach the end
            while (left >= 0 && right < input.length) {
                // below check to find out if its a palindrome
                if (input[left] == input[right]) {
                    // update global indexes only if this is the longest one till now
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
            // for even palindrome, we need to have similar logic with mid size 2
            // for that we will start right from one extra place
            left = mid-1;
            right = mid + 2;// for example 12333321 when we choose 33 as mid
            while (left >= 0 && right < input.length)
            {
                if (input[left] == input[right]) {
                    if (right - left > longestPalindromeEnd
                            - longestPalindromeStart) {
                        longestPalindromeStart = left;
                        longestPalindromeEnd = right;
                    }
                }
                left--;
                right++;
            }
        }
        // we have the start and end indexes for longest palindrome now
        return in.substring(longestPalindromeStart, longestPalindromeEnd + 1);
    }
 
}

Concurrent LRU Cache

public class ConcurrentLRUCache<Key, Value> {
 
private final int maxSize;
private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;
 
public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}
 
/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }
 
    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}
 
/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}
}

Singleton Java

We will be able to create a copy of the Object by cloning it using the Object’s clone methodThe singleton pattern must be carefully constructed in multi-threaded applications. Double check locking is famous idiom and due to that there were java memory model changes in java 1.5 release. let's see how it happens before java 1.5 release even if you declare instance as volatile.

Double Check Lock

public static Singleton getInstance() {  
    if (instance == null){             //  0
      synchronized(Singleton.class) {  //  1
         if (instance == null){        //  2
          instance = new Singleton();  //  3
       }     }   }   
    return instance;                   //  4 
}

This alone is not enough. Here is famous article on this - DCL broken. Nice presentation before Java memory model changes in java 1.5

Singleton class with making instance as volatile

public class Singleton{
 
private static volatile instance; //volatile variable 
 
public static Singleton getInstance(){
 
   if(instance == null){
            synchronized(Singleton.class){
              if(instance == null)
               instance = new Singleton();
            }
   }
   return instance;
}

Singleton class with Initialize on demand Holder Class Idiom

public class Singleton {
        // Private constructor prevents instantiation from other classes
        private Singleton() { }
 
        /**
        * SingletonHolder is loaded on the first execution of Singleton.getInstance() 
        * or the first access to SingletonHolder.INSTANCE, not before.
        */
        private static class SingletonHolder { 
                public static final Singleton INSTANCE = new Singleton();
        }
 
        public static Singleton getInstance() {
                return SingletonHolder.INSTANCE;
        }
}

Singleton class with ENUM

public enum Singleton {
        INSTANCE;
        public void execute (String arg) {
                //... perform operation here ...
        }
}

If you are using multiple class loaders, this could defeat the Singleton implementation and result in multiple instances. If you want a true Singleton across class loaders, then you need a common parent to load the class in question, or you need to specify the class loader yourself. Multiple class loaders are commonly used in many situations—including servlet containers—you can wind up with multiple singleton instances no matter how carefully you've implemented your singleton classes. If you want to make sure the same class loader loads your singletons, you must specify the class loader yourself.

private static Class getClass(String classname) throws ClassNotFoundException {
    ClassLoader classLoader = Thread.currentThread().getContextClassLoader();
    if(classLoader == null) 
        classLoader = Singleton.class.getClassLoader();
      return (classLoader.loadClass(classname));
}

If SingletonClass implements the java.io.Serializable interface, the class's instances can be serialized and deserialized. However, if you serialize a singleton object and subsequently deserialize that object more than once, you will have multiple singleton instances

To avoid the above you need to implement readResolve() method.

private Object readResolve() {
    return INSTANCE;
}

We will be able to create a copy of the Object by cloning it using the Object’s clone method SingletonDemo clonedObject = (SingletonDemo) obj.clone(); So to deal with this we need to override the Object’s clone method which throws a CloneNotSupportedException exception.

public Object clone() throws CloneNotSupportedException {
throw new CloneNotSupportedException();
}

Breaking with Reflection

Singleton pattern can be broken using reflection, as shown below.

import java.lang.reflect.Constructor;
 
public class Test {
 
    public static void main(String[] args) throws Exception {
 
        Singleton s = Singleton.getInstance();
 
        Class clazz = Singleton.class;
 
        Constructor cons = clazz.getDeclaredConstructor();
        cons.setAccessible(true);
 
        Singleton s2 = (Singleton) cons.newInstance();
    }
}

Java’s own way of handling such mischievous behavior is to use a SecurityManager which restricts the ‘supressAccessChecks’permission of java.lang.reflect.ReflectPermission. The default security manager implementation does it. Following example shows this:

import java.lang.reflect.Constructor;
 
public class Test {
 
    public static void main(String[] args) throws Exception {
 
        SecurityManager mgr = new SecurityManager();
        System.setSecurityManager(mgr);
 
        Singleton s = Singleton.getInstance();
 
        Class clazz = Singleton.class;
 
        Constructor cons = clazz.getDeclaredConstructor();
        cons.setAccessible(true);
 
        Singleton s2 = (Singleton) cons.newInstance();
    }
}

This would throw the exception while trying to create the second instance using Reflection.

Exception in thread "main" java.security.AccessControlException: access denied (java.lang.reflect.ReflectPermission suppressAccessChecks)

at java.security.AccessControlContext.checkPermission(AccessControlContext.java:323)


at java.security.AccessController.checkPermission(AccessController.java:546)


at java.lang.SecurityManager.checkPermission(SecurityManager.java:532)


at java.lang.reflect.AccessibleObject.setAccessible(AccessibleObject.java:107)


at com.test.singleton.securitymgr.Test.main(Test.java:17)

But the downside of this is that some of the libraries that we use, for example ‘Hibernate’ relies on reflective access to object properties. When we mark a field (instead of public getter / setter) with @Id or @Column annotation, Hibernate uses reflection to access the particular field to obtain the meta-data. So if we put a security manager which restricts reflective access, theoretically Hibernate should fail. One approach to solve this problem is to do the constructor checks to see if the instance variable is already set. If it is, then the constructor would throw an exception avoiding the instantiation.

public class Singleton {
 
    private static final Singleton INSTANCE = new Singleton();
 
    private Singleton() {
 
        // Check if we already have an instance
        if (INSTANCE != null) {
           throw new IllegalStateException("Singleton" +
             " instance already created.");
        }
 
        System.out.println("Singleton Constructor Running...");
    }
 
    public static final Singleton getInstance() {
        return INSTANCE;
    }
}

Minimum Sum of the given array.

You have given an array of Integer. You can change the sign of any element of the array. Write a program-me to find minimum sum of the given array.
For Example: 2 1 3 4 2
Minimum sum = 0 if -2, -1, -3 , 4,  2
Approach: Problem can be reduced to dividing a sequence of integers into two sets such that the sum of the digits in one set is equal to the sum of the digits in the other set.

public class MinimumSum {

	public static boolean calculate(int arr[], int tot, int totalSum)
	{
	    int n = arr.length;
		boolean dp[][] = new boolean[totalSum+1][n+1];
	    if(dp[tot][n-1] == false)
	    {
	       for(int i = 0; i < n; i++)
	         dp[arr[i]][i] = true;
	       
	 
	       int sum = arr[0];
	       for(int k = 1; k < n; k++)
	       {
	          sum += arr[k];
	          int lim = tot < sum ? tot : sum;
	          for(int i = 1; i <=lim; i++)
	          {
	              dp[i][k] |= dp[i][k-1];
	              if(i > arr[k])
	                  dp[i][k] |= dp[i-arr[k]][k-1];
	          }
	       }
	    }
	    
	    return dp[tot][n-1];
	}
	 
	public static int solve(int arr[])
	{
		int n = arr.length;
	    int tot = 0;
	    if (n == 1)
	       return arr[0];
	 
	    for(int i = 0; i < n; i++)
	    {
	       tot += arr[i];
	    }
	    
	     
	    int min_sum = Integer.MAX_VALUE;
	    for(int i = 1; i <= tot/2; i++)
	    {
	       boolean temp1, temp2;
	      
	       temp1 = calculate(arr, i,tot);
	       temp2 = calculate(arr, tot - i,tot);
	       
	       if((temp1 == true) && (temp2 == true))
	       {
	          if(min_sum  > (tot-i-i))
	             min_sum = tot - i - i;           
	          
	       }
	   }        
	   return min_sum;
	}
	 
	public static void main(String[] args) {
		int arr[] = {2,1,3,4,2};
		System.out.println("elements min sum"+solve(arr));

	}

}

Longest Increasing and Decreasing Subsequence problem

You have a sequence of numbers from which you must create the longest subsequence satisfying the following condition: it can be 'cut' into two parts that share exactly one common element (the last element of the first part is the first element of the second part), and the first part is sorted in strictly ascending order while the second part is sorted in strictly descending order. For example, the sequence { 1, 4, 6, 5, 2, 1 } can be 'cut' into { 1, 4, 6 } and { 6, 5, 2, 1 }. The two parts share the 6, and the first sequence is sorted in ascending order while the second sequence is sorted in descending order.
You are given a int[] numbers, a sequence of numbers. Return the minimal number of elements you must throw out from the given sequence such that the remaining subsequence satisfies the condition described above.

0)
{1, 4, 6, 5, 2, 1}
Returns: 0
This sequence already satisfies the condition, so the answer is 0.
1)
{1, 2, 1, 2, 3, 2, 1, 2, 1}
Returns: 4
The longest subsequence is { 1, 2, 3, 2, 1 }, so you need to throw out at least 4 elements.
2)
{2, 2, 2, 2, 2}
Returns: 4
3)
{4,5,65,34,786,45678,987,543,2,6,98,580,4326,754,54,2,1,3,5,6,8,765,43,3,54}
Returns: 14

http://community.topcoder.com/stat?c=problem_statement&pm=5922

public class IncreasingDecreasingSubseq {

	
	public static void findMinimumCuts(int arr[])
	{
		
		int size = arr.length;
		int lis[] = new int[size];
		int lds[] = new int[size];
		// Longest Increasing sequence
		   for(int i = 0; i < size; ++i)
		   {
		       for(int j = 0; j < i; ++j)
		       {
		           if(arr[j] < arr[i])
		           {
		               lis[i] = Math.max(lis[j] + 1, lis[i]);
		           }
		       }
		   }
		   
		   // Longest decreasing sequence
		   for(int i = size - 1; i >= 0; --i)
		   {
		      for(int j = size - 1; j > i; --j)
		      {
		          if(arr[j] < arr[i])
		          {
		             lds[i] = Math.max(lds[j] + 1, lds[i]);
		          }
		      }
		   }
		   
		   int best = 0;
		   for(int i = 0; i < size; ++i)
		   {
		      best = Math.max(best, lds[i] + lis[i]);
		   }
		   System.out.println("Best"+best);
		   System.out.println("Number to be removed : " + (size - best - 1));
		
	}
	
	public static void main(String[] args) {

		int a[] = {1, 2, 1, 2, 3, 2, 1, 2, 1};
		int b[] = {4,5,65,34,786,45678,987,543,2,6,98,580,4326,754,54,2,1,3,5,6,8,765,43,3,54};
		findMinimumCuts(a);
		findMinimumCuts(b);
	}

}

Maximal Increasing subsequence

A subsequence of a sequence of numbers a is the result of erasing zero or more elements from a. An increasing subsequence is a subsequence in which each element (except the first) is strictly greater than the previous element. An increasing subsequence of a is maximal if unerasing any of the erased elements of a does not result in a longer increasing subsequence.
For example, if a={1,3,2,6,4,5} then {1,3,4} is an increasing subsequence but not a maximal increasing subsequence. {1,2,4,5}, {1,3,4,5}, {1,2,6} and {1,3,6}, on the other hand, are maximal increasing subsequences.
You will be given a as an int[] representing a sequence of distinct numbers. Return the number of maximal increasing subsequences it contains

http://community.topcoder.com/stat?c=problem_statement&pm=7753

public class MaximalIncreasinSubsequence {

	public static long findMaximalIncreasingSubsequence(int arr[]) {
		int size = arr.length;
		int end[] = new int[size];
		end[0] = 1;

		for (int i = 1; i < size; i++) {
			int shadow = 0;
			int sum = 0;
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] > shadow && arr[j] < arr[i]) {
					shadow = arr[j];
					sum = sum + end[j];
				}
			}
			if (sum == 0)
				sum = 1;
			end[i] = sum;
		}
		long finalanswer = 0;

		int max = 0;
		for (int i = size - 1; i >= 0; i--) {
			if (max < arr[i]) {
				finalanswer = finalanswer + end[i];
				max = arr[i];
			}
		}
		return finalanswer;
	}

	public static void main(String[] args) {
		
		int arr[] = {1,3,2,6,4,5};
		int b[] = {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2};
		System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(arr));
		System.out.println("Maximal Increasing subsequence"+findMaximalIncreasingSubsequence(b));

	}

}

Three product

Given a set of positive integers s = {a1, a2, ..., an},
There exists ai * aj = ak,  i != j != k
Find the maximum number satisfying the above conditions, if there are no three numbers satisfying the above condition, the output –1

public static int findProduct(int a[]) {
		int n = a.length;

		for (int i = 0; i < n; i++) {
			for (int j = 0, k = i + 1; j < i && k < n;) {
				if (a[i] * a[j] == a[k]) {
					return a[k]; // find
				} else if (a[i] * a[j] > a[k])
					k++;
				else
					j++;
			}
		}

		return -1;
	}

Insertion Sort Variant

Problem Statement

We have an array A and we want to sort it in non-decreasing order. The only allowable operation is to move one element of the array into any other place (before all elements, after all elements or between any two adjacent elements). The cost of the single operation is equal to the value of the moved element. We want to minimize the total cost of sorting the array.

For example, we have an array {7, 1, 2, 3}. We can sort it by moving 7 from the head to the tail. But the cost of this operation is 7 which is not optimal. The optimal sorting algorithm is to consecutively move 1, 2 and 3 to the proper places before 7. The total cost of these three movements will be 1+2+3=6, which is less than 7.

You will be given a int[] theArray. Return the minimal total cost required to sort the array.

http://community.topcoder.com/stat?c=problem_statement&pm=4844

public class MinimalCostSort {

	public static int calcMinimalCost(int[] arr) {
		int[] f = new int[arr.length];
		int res = 0;
		for (int i = 0; i < arr.length; i++) {
			f[i] = arr[i];
			for (int j = 0; j < i; j++) {
				if (arr[j] <= arr[i])
					f[i] = Math.max(f[i], f[j] + arr[i]);
			}
			res = Math.max(res, f[i]);
		}
		res = -res;
		for (int i = 0; i < arr.length; i++)
			res += arr[i];
		return res;
	}

	public static void main(String[] args) {

		int a[] = {6, 4, 5, 3, 8, 2, 7, 2, 11, 2, 2};
		int b[] = {8, 2, 6, 5, 1, 4};

		System.out.println("Minimal cost is "+calcMinimalCost(a));
		System.out.println("Minimal cost is "+calcMinimalCost(b));
	}

}

Longest substring with 2 unique characters.

Q: Find the longest substring with at most two unique characters(ASCII) in a given string .

eg
input aabbccccceeedd
return ccccceee

We create a set of length 256 to keep the last index from the left. Whenever we reach a new character and count is still less than or equal to 2 we check if the current substring length is greater than the previous result. If it is we update the result as the current longest substring.

import java.util.Arrays;

public class Problem {

	public static String longestTwoUnique(String s) {
		char str[] = s.toCharArray();
		int[] set = new int[256];
		Arrays.fill(set, -1);
		int i = 0, j = 0;
		String res = "";
		int count = 0;
		while (j < s.length()) {
			if (set[str[j]] == -1) {
				set[str[j]] = j;
				count++;
				if (res.length() <= j - i)
					res = s.substring(i, j);
				if (count > 2) {
					count--;
					int nextI = set[str[i]];
					set[str[i]] = -1;
					i = nextI + 1;
				}
			} else {
				set[str[j]] = j;
				if (res.length() <= j - i)
					res = s.substring(i, j);
			}
			j++;
		}
		if (count <= 2 && res.length() <= j - i)
			res = s.substring(i, j);
		return res;
	}

	public static void main(String args[]) {
		System.out.println("longest string"
				+ longestTwoUnique("aabbccccceeedd"));

	}
}

Find element in bitonic array

Given an array which is monotonically increasing and then decreasing . Write an algorithm to search for a given element. Expected algorithm O(Log n)

An array of number is bitonic if it consists of a strictly increasing sequence followed by a strictly decreasing sequence. We can solve the problem in 3logN comparisons by finding the maximum in the array and then doing two binary searches, one on the increasing and one on the decreasing sequence. The maximum can be found in Log N comparisons using binary search. Each step compares two adjacent numbers A[i] and A[i+1]. If hey are equal, they are both maximum. If A[i] is smaller, we restrict the search to indices at most i, if A[i+1] is bigger, we restrict the search to indices greater than i.

 

public static int getMaximumElement(int a[], int low, int high)
	{
		if(low == high) return high;
		int mid = low + (high - low)/2;
		if(a[mid] < a[mid+1])
			return getMaximumElement(a, mid+1, high);
		else if(a[mid] > a[mid+1])
			return getMaximumElement(a, low, mid-1);
		else return mid;
	}

Given an int array which might contain duplicates, find if it is a sequence.

Given an int array which might contain duplicates, find if it is a sequence.
Eg. {45,50,47,46,49,48}
is a sequence 45, 46,47,48,49,50
Sorting is an obvious solution. Can this be done in O(n) time and O(1) space

                                            (Or)
Write a method that takes an int array of size m, and returns (True/False) if the array consists of the numbers n...n+m-1, all numbers in that range and only numbers in that range. The array is not guaranteed to be sorted. (For instance, {2,3,4} would return true. {1,3,1} would return false, {1,2,4} would return false.

By working with a[i] % a.length instead of a[i] you reduce the problem to needing to determine that you've got the numbers 0 to a.length - 1.

Approach:
Example array: A = {4, 1, 3, 3, 2}
1. get the min and max.
min=1 and max=4
2. if (max - min) > A.length then "its NOT a sequence".
3. else for each element in A[i] do the following:
a. calculate A[i] - min till A[i]-min=i;
i=0; 4 - 1 = 3, swap A[0] and A[3]
Now we have A = {3, 1, 3, 4, 2}
Again,
i=0; 3 - 1 = 2, now A[0] and A[2] are same so swap A[0] and A[length-1] and put A[length] = infinite.
A = {2, 1, 3, 4, INF}
Again,
i=0; 2 - 1 = 1, swap A[0] and A[1],
A = {1, 2, 3, 4, INF}
i=1; 2 - 1 = 1 (which is same as i)
similarlty for i=2, i=3
finally we have A as,
A = {1, 2, 3, 4, INF}

public static boolean isSequence(int A[])
{
    int min = Integer.MINIMUM;
    int max = Integer.MAXIMUM;
    int len = A.length;
    for(int i=0;i<len;i++)
    {
        if(A[i] < min)
        {
            min = A[i];
        }else if(A[i] > max)
        {
            max = A[i];
        } 
    }
    
    if(max-min > A.length)
        return false;
    
    int i=0;
    while(i<len)
    {
        while(i<len && i != (A[i] - min))
        {
              if(A[A[i] - min] == A[i])
              {
                   A[i] = A[len-1] ;
                   A[len-1] = Integer.MAXIMUM;
                   len = len-1;
              }else
              {
                  int k = A[i] - min;
                  int temp= A[i];
                  A[i] = A[k];
                  A[k] = temp;
              }
        
        }
        
        i++;
  
    }
    
    for(int i=1;i<len;i++)
    {
        if((A[i] - A[i-1]) != -1
        return false;
    }
    
    return true;
}

Longest Contiguous Subarray with Average Greater than or Equal to k

Consider an array of N integers. Find the longest contiguous sub array so that the average of its elements is greater (or equal) than a given number k.

We can reduce this problem to longest contiguous sub array with sum >= 0 by subtracting k from all values in O(n) time

public static int maxSubSum3( int [ ] a )
    {
        int maxSum = 0;
        int thisSum = 0;

        for( int i = 0, j = 0; j < a.length; j++ )
        {
            thisSum += a[ j ];

            if( thisSum > maxSum )
            {
                maxSum = thisSum;
                seqStart = i;
                seqEnd   = j;
            }
            else if( thisSum < 0 )
            {
                i = j + 1;
                thisSum = 0;
            }
        }

        return maxSum;
    }

Implement rand7() using rand5()

public static int rand7() {
    int vals[][] = {
        { 1, 2, 3, 4, 5 },
        { 6, 7, 1, 2, 3 },
        { 4, 5, 6, 7, 1 },
        { 2, 3, 4, 5, 6 },
        { 7, 0, 0, 0, 0 }
    };
 
    int result = 0;
    while (result == 0)
    {
        int i = rand5();
        int j = rand5();
        result = vals[i-1][j-1];
    }
    return result;
}

Another approach is

public static int rand7() {
    while (true) {
        int num = 5 * (rand5() - 1) + (rand5() - 1);
        if (num < 21)
            return (num % 7 + 1);
    }
}

Given a sorted, shifted array find the minimum element

Given a sorted, shifted array find the minimum element. For example in {3,4,5,1,2} the minimum is 1, in {4,5,1,2,3} the minimum is 1.

Concept of Binary search can be use with little modification.

// finds the smallest number and returns
// it , if not found it returns -1
public static int findSmallest(int a[], int N)
{
    if(length==0 || a==NULL)
        return -1;

    int start=0,end=N-1;

    while(start <= end)
    {
        int mid=(start end)/2;

        // this is the standard comparison condition
        if(a[mid] > a[mid+1])
            return a[mid+1];

        // an extra comparison that adds the optimization that 
        // if the mid element is the smallest one, there will not be 
        // extra iterations
        if(a[mid] < a[mid-1])
            return a[mid];

        // the left half is in strictly increasing order
        // so we search in the second half
        if(a[mid] > a[start])
        {
            start = mid+1;
        }
        // The array is not rrotated so we simply
        // return the first element of the array
        else if(a[mid] >= a[start] && a[mid] <= a[end])
             return a[0];

        // the right half is in strictly increasing order
        // and hence we will search in the left half
         else
           end= mid-1;

    }
    return -1;
}

Search in Rotated array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). How do you find an element in the rotated array efficiently

 

public static int rotatedBinarySearch(int a[], int N, int key)
{
    int low =0;
    int high = N-1;
    
    while(low <= high)
    {
        int mid = (L+R)/2;
        
        if(a[mid] == key)
            return mid;
          
        //lower half is sorted 
        if(a[low] <= a[mid])
        {
            if(A[low]<= key && key < a[mid])
                high = mid -1;
            else
                low = mid +1;
        }     
        else   // upper half is sorted
        {
            if(a[mid] < key && key < a[high])
                low = mid + 1;
            else
                high = mid - 1;
        
        }       
    }
    
    return -1;
}

Stocks buy and sell, Max profit

Stock prices are stored in an array in the order of date. How do you get the most profit from a
sequence of stock prices? For example, the most profit to be gained from the sequence of ordered stock prices {9, 11, 5, 7, 16, 1, 4, 2} is 11, bought when the price was 5 and sold when the price was 16.

public static int maxStock(int stock[])
{
    if(stock == null || stock.length < 2)
    {
        return 0;
    }
    
    int minStock = stock[0];
    int maxDiff = stock[1]-stock[0];
    
    for(int i=2;i<stock.length;i++)
    {
        if(stock[i-1] < minStock)
            minStock = stock[i-1];
            
        int currDiff = stock[i] - minStock;
        if(currDiff > maxDiff)
            maxDiff = currDiff;  
    }
     
    return maxDiff;

}

Pattern matching.

How to find the phone numbers in 50,000 txt file and replace.

The phone numbers could be in several formats like below

"***-*******"
"**********"
"*** *******"
"***-***-****"

final String regex = "[\\s](\\({0,1}\\d{3}\\){0,1}" +
			"[- \\.]\\d{3}[- \\.]\\d{4})|" +
			"(\\+\\d{2}-\\d{2,4}-\\d{3,4}-\\d{3,4})";
	final Pattern phonePattern = Pattern.compile(regex);

	/* The result set */
	Set<File> files = new HashSet<File>();

	File dir = new File("/initDirPath");
	if (!dir.isDirectory()) return;

	for (File file : dir.listFiles()) {
		if (file.isDirectory()) continue;

		BufferedReader reader = new BufferedReader(new FileReader(file));

		String line;
		boolean found = false;
		while ((line = reader.readLine()) != null 
				&& !found) {
			
			Matcher matcher = phonePattern.matcher(line);
			if (found = matcher.find()) {
				matcher.replaceAll("xxxxxxxxxxx");
			}
		}
	}

	for (File file : files) {
		System.out.println(file.getAbsolutePath());
	}

Array of maximum value in sliding window

A long array A[] is given to you. There is a sliding window of size w which is moving from the very left of the array to the very right. You can only see the w numbers in the window. Each time the sliding window moves rightwards by one position. Following is an example:

The array is [1 3 -1 -3 5 3 6 7], and w is 3

Window position Max

---

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

Input: A long array A[], and a window width w Output: An array B[], B[i] is the maximum value of from A[i] to A[i+w-1] Requirement: Find a good optimal way to get B[i].

The double-ended queue is the perfect data structure for this problem. It supports insertion/deletion from the front and back. The trick is to find a way such that the largest element in the window would always appear in the front of the queue. How would you maintain this requirement as you push and pop elements in and out of the queue?

Besides, you might notice that there are some redundant elements in the queue that we shouldn't even consider about. For example, if the current queue has the elements: [10 5 3], and a new element in the window has the element 11. Now, we could have emptied the queue without considering elements 10, 5, and 3, and insert only element 11 into the queue.

Removing redundant elements and storing only elements that need to be considered in the queue is the key to achieve the efficient O(n) solution below.

Every time, we move to a new window, we will be getting a new element and leave an old element. We should take care of:

1. Popping elements outside the window from queue front.
2. Popping elements that are less than new element from the queue.
3. Push new element in the queue as per above discussion.

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindow {

	public static void maxSlidingWindow(int A[], int n, int w, int B[]) {
		Deque<Integer> Q = new ArrayDeque<Integer>();

		// Initialize deque Q for first window
		for (int i = 0; i < w; i++) {
			while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
				Q.pollLast();
			Q.offerLast(i);
		}

		for (int i = w; i < n; i++) {
			B[i - w] = A[Q.getFirst()];

			// update Q for new window
			while (!Q.isEmpty() && A[i] >= A[Q.getLast()])
				Q.pollLast();

			// Pop older element outside window from Q
			while (!Q.isEmpty() && Q.getFirst() <= i - w)
				Q.pollFirst();

			// Insert current element in Q
			Q.offerLast(i);
		}
		B[n - w] = A[Q.getFirst()];
	}

	public static void main(String args[]) {
		int w = 3;
		int a[] = { 1, 3, -1, -3, 5, 3, 6, 7 };
		int b[] = new int[a.length - w + 1];

		maxSlidingWindow(a, a.length, w, b);
		
		System.out.println("Sliding Window Maximum is ");
		for (int i = 0; i < b.length; i++) {
			System.out.print(b[i] + ",");
		}

	}
}

Each element in the list is being inserted and then removed at most once. Therefore, the total number of insert and delete operations is 2n. Therefore it is an O(n) solution.

A queue with constant time operations

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

We know that push and pop are constant time operations But when we think of get_min()[i.e to find the current minimum number in the queue] generally the first thing that comes to mind is searching the whole queue every time the request for the minimum element is made. But this will never give the constant time operation, which is the main aim of the problem.

To do this we have to use two more queues which will keep the track of minimum element and we have to go on modifying these 2 queues as we do push and pop operations on the queue so that minimum element is obtained in O(1) time.

import java.util.LinkedList;
import java.util.Queue;

public class MinQueue {

	Queue<Integer> q = new LinkedList<Integer>();
	Queue<Integer> minq1 = new LinkedList<Integer>();
	Queue<Integer> minq2 = new LinkedList<Integer>();
	boolean isMinq1Current = true;

	public void push(int a) {
		q.offer(a);
		if (isMinq1Current) {
			if (minq1.isEmpty())
				minq1.offer(a);
			else {
				while (!minq1.isEmpty() && minq1.peek() <= a)
					minq2.offer(minq1.poll());
				minq2.offer(a);
				while (!minq1.isEmpty())
					minq1.poll();
				isMinq1Current = false;
			}
		} else {
			if (minq2.isEmpty())
				minq2.offer(a);
			else {
				while (!minq2.isEmpty() && minq2.peek() <= a)
					minq1.offer(minq2.poll());
				minq1.offer(a);
				while (!minq2.isEmpty())
					minq2.poll();
				isMinq1Current = true;
			}
		}
	}

	public int pop() {
		int a = q.poll();
		if (isMinq1Current) {
			if (a == minq1.peek())
				minq1.poll();
		} else {
			if (a == minq2.peek())
				minq2.poll();
		}
		return a;
	}

	public int min() {

		if (isMinq1Current) {
			return minq1.peek();
		} else {
			return minq2.peek();
		}
	}

}

Remove extra brackets from a paranthesized expression

How to remove extra bracket from expressions like ((((A+B))C)) to give (A+B)C in the most optimized way?

Remember the input expression will be valid expression and output expression generated must also be valid and should give the same result as the input expression.

This can be done in O(n) time complexity using stack data structure.

The algorithm

1. Start traversing the expression from left examining every bracket.
2. If you encounter "(" such that there is another "(" to the right of it, this might be one of the extra brackets to be removed. However we can't be sure right now. So put the minus times the index of this bracket in the integer stack.(we put minus times the index to distinguish brackets having similar brackets to their right from the ones not having )
3. If you encounter "(" such that there is a character other than "(" to its right , put its index in the stack.
4. If you encounter ")" such that there is another ")" to its left and we have a negative number on the top of the stack, pop the stack and replace current ")" and bracket at the index minus times top of the stack with "$"(so that these brackets can be removed later and are useless).
5. If you encounter ")" such that there is a character other than ")" to its left and top of the stack has the positive number than you need that bracket so just pop the stack.

At the end we will have useless brackets replaced with "$" sign, which can be removed in a single traversal. Thus giving us an O(n) complexity. Here is the running code using above explained algorithm.

import java.util.Stack;

public class ExpressionValidate {

	public static String validateExpression(String expr) {

		char r[] = expr.toCharArray();
		char s[] = expr.toCharArray();
		Stack<Integer> st = new Stack<Integer>();
		int i = 0;
		while (i < s.length) 
		{
			if (s[i] == '(') {
				if (s[i + 1] == '(') {
					st.push(-i);
				} else {
					st.push(i);
				}
				i++;
			} else if (s[i] != ')' && s[i] != '(') {
				i++;
			} else if (s[i] == ')') {
				int top = st.peek();
				if (s[i - 1] == ')' && top < 0) {
					r[-top] = '$';
					r[i] = '$';
					st.pop();
				}

				else if (s[i - 1] == ')' && top > 0) {
					System.out.println("Something is wrong!!");
				}

				else if (s[i - 1] != ')' && top > 0)
					st.pop();
				i++;
			}
		}

		StringBuffer result = new StringBuffer();

		for (i = 0; i<r.length; i++) {
			if (r[i] == '$') {
				continue;
			}
			result.append(r[i]);
		}

		return result.toString();

	}

	public static void main(String[] args) {
		String expr = "((((A+B))C))";
		System.out.println("Validate expression"+validateExpression(expr));

	}

}

Interval Tree

Question: Find the intervals from a set of intervals in which a given point lies

Given a set of intervals such as (10,20), (15,25), (28,40), (50,70), (0,9) (60,90) and build a data structure. Query the data structure for point x, and it find out all the intervals that contain this point x.

The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection.

In a simple case, the intervals do not overlap and they can be inserted into a simple binary search tree and queried in O(log n) time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naive approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in O(log n) time, but the results must be merged, requiring O(n) time. This gives us queries in O(n + log n) = O(n), which is no better than brute-force.

Interval trees solve this problem.

To construct an interval tree from the input given in the question, the following steps should be taken

1. Firstly we will arrange the end points of all the intervals in the increasing order. So for the above given input it will become 0 9 10 15 20 25 28 40 50 60 90. If there are N intervals, there will be 2N end-points and hence sorting will take O(NlogN) time. The entire range of all the intervals now becomes 0-90.

2. We start by taking the entire range of all the intervals and dividing it in half at x_center (in practice, x_center should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of x_center which we'll call S_left, those completely to the right of x_center which we'll call S_right, and those overlapping x_center which we'll call S_center.

3. The intervals in S_left and S_right are recursively divided in the same manner until there are no intervals left.

4. The intervals in S_center that overlap the center point are stored in a separate data structure linked to the node in the interval tree. This data structure consists of two lists, one containing all the intervals sorted by their beginning points, and another containing all the intervals sorted by their ending points.

The result is a binary tree with each node storing:

• A center point
• A pointer to another node containing all intervals completely to the left of the center point
• A pointer to another node containing all intervals completely to the right of the center point
• All intervals overlapping the center point sorted by their beginning point
• All intervals overlapping the center point sorted by their ending point

To find the intervals in which a given number 'x' lies we do the following:

1. For each tree node, x is compared to x_center, the midpoint used in node construction above. If x is less than x_center, the leftmost set of intervals, S_left, is considered. If x is greater than x_center, the rightmost set of intervals, S_right, is considered.

2. As each node is processed as we traverse the tree from the root to a leaf, the ranges in its S_center are processed. If x is less than x_center, we know that all intervals in S_center end after x, or they could not also overlap x_center. Therefore, we need only find those intervals in S_center that begin before x. Suppose we find the closest number no greater than x in this list. All ranges from the beginning of the list to that found point overlap x because they begin before x and end after x (as we know because they overlap x_center which is larger than x). Thus, we can simply start enumerating intervals in the list until the endpoint value exceeds x.

3. Likewise, if x is greater than x_center, we know that all intervals in S_center must begin before x, so we find those intervals that end after x using the list sorted by interval endings.

4. If x exactly matches x_center, all intervals in S_center can be added to the results without further processing and tree traversal can be stopped.

Intersection with Interval

First, we can reduce the case where an interval R is given as input to the simpler case where a single point is given as input. We first find all ranges with beginning or end points inside the input interval R using a separately constructed tree. In the one-dimensional case, we can use a simple tree containing all the beginning and ending points in the interval set, each with a pointer to its corresponding interval.

A binary search in O(log n) time for the beginning and end of R reveals the minimum and maximum points to consider. Each point within this range references an interval that overlaps our range and is added to the result list. Care must be taken to avoid duplicates, since an interval might both begin and end within R. This can be done using a binary flag on each interval to mark whether or not it has been added to the result set.

The only intervals not yet considered are those overlapping R that do not have an endpoint inside R, in other words, intervals that enclose it. To find these, we pick any point inside R and use the algorithm below to find all intervals intersecting that point (again, being careful to remove duplicates).

The complete java implementation can be found here.

http://thekevindolan.com/2010/02/interval-tree/

A pair with given sum in a Balanced BST

Find two elements in balanced BST which sums to a given a value. Constraints Time O(n) and space O(log n).

The Brute Force Solution is to consider each pair in BST and check whether the sum equals to X. The time complexity of this solution will be O(n^2).

A Better Solution is to create an auxiliary array and store Inorder traversal of BST in the array. The array will be sorted as Inorder traversal of BST always produces sorted data. Once we have the Inorder traversal, we can pair in O(n) time. This solution works in O(n) time, but requires O(n) auxiliary space.

The idea is same as finding the pair in sorted array. We traverse BST in Normal Inorder and Reverse Inorder simultaneously. In reverse inorder, we start from the rightmost node which is the maximum value node. In normal inorder, we start from the left most node which is minimum value node. We add sum of current nodes in both traversals and compare this sum with given target sum. If the sum is same as target sum, we return true. If the sum is more than target sum, we move to next node in reverse inorder traversal, otherwise we move to next node in normal inorder traversal. If any of the traversals is finished without finding a pair, we return false. Following is C++ implementation of this approach.

 

public static int[] findSum(int toSearch, Node root){
        Stack<Node> s1 = new Stack<Node>();
        Stack<Node> s2 = new Stack<Node>();
        Node cur1 = root;
        Node cur2 = root;
        boolean done1 = false, done2 = false;

        int val1 = 0, val2 = 0;

        while (true) {
            while(!done1){
                if(cur1 != null){
                    s1.push(cur1);
                    cur1 = cur1.left;
                }
                else {
                    if(s1.isEmpty()) done1 = true;
                    else {
                        cur1 = s1.pop();
                        val1 = cur1.value;
                        cur1 = cur1.right;
                        done1 = true;
                    }
                }
            }
            while(!done2){
                if(cur2 != null){
                    s2.push(cur2);
                    cur2 = cur2.right;
                }
                else {
                    if(s2.isEmpty()) done2 = true;
                    else {
                        cur2 = s2.pop();
                        val2 = cur2.value;
                        cur2 = cur2.left;
                        done2 = true;
                    }
                }
            }
            if (val1 + val2 == toSearch){
                int[] res = {val1,val2};
                return res;
            }
            else if (val1 + val2 > toSearch){
                done2 = false;
            }
            else {
                done1 = false;
            }
        }
    }

Reverse adjacent nodes in a linked list

Reverse the adjacent nodes in a linked list If the nodes of a linked list are as follows 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 then after reverse they should be 2 -> 1 -> 4 -> 3 Here the number of entries are odd hence the last link is not reversed. If number of nodes are even then last node should also be reversed.

node * swapAdjacent(node * head){
    node *a,*b,*c,*d;
    a = head;
    if(a == null)
        return a;
    b = a->next;
    if(b == null)
        return a;
    c = b->next;
    if(c == null){
        b->next = a;
        a->next = c;
        return b;
    }
    d = c->next;

    //now all a,b,c are non null. size of list is  >=3
    node * newHead = b;
    while(b!= null){
        b->next = a;
        if(d != null)
            a->next = d;
        else
            a->next = c;
        a = c;
        b = d;
        c = (b!=null)?b->next : null;
        d = (c!=null)?c->next : null;
    }
    return newHead;
}

Subsets of size k

Question: Print All k size subset of given array of size n

Algorithm:
Suppose array size is of length 5 ie A = {1,2,3,4,5};
and we need all the subsets of size k=3.

If we were supposed to find all the subsets then we would have taken all the binary representations of numbers from 1 to (2^5 - 1) and then according to the bits set, we would have chosen the corresponding number from Array A.

Now the idea is get the minimum number where all "k" lower bits are set.
In our case that would be = "00111" => 7 in decimal
Now find the next decimal number > 7 where 3 bits are set.
Keep on finding the next numbers till you hit "11100" = 28 since that is the largest binary number with 3 bits set of length 5.

Given an integer, method to find the next smallest number that have the same numbers of bits set:
1. Traverse from right to left, Once we have passed a 1, turn on the next 0.
ex: 101110 becomes 111110
2. Turn off the one that's just to the right side of that (where you switched on '0' to '1').
now 111110 becomes 110110.
3. Make the number as small as possible by rearranging all the 1's to be as far as right as possible.
ex: 110110 becomes 110011.

public class KSubSet {

	public static void main(String[] args) {
		int[] A = { 1, 2, 3, 4, 5 };
		int k = 3;
		int len = A.length;
		int result = 0;

		StringBuffer sb = new StringBuffer();
		int diff = len - k;

		for (int i = 1; i <= diff; i++) {
			sb.append('0');
		}
		for (int i = 1; i <= k; i++) {
			sb.append('1');
		}

		String binStr = sb.toString();
		String finalBinStr = sb.reverse().toString();
		int last = Integer.parseInt(finalBinStr, 2);
		// System.out.println("LAST:" + last);
		System.out.println("Subsets of size " + k + " are: ");
		printSubSet(A, binStr);
		result = Integer.parseInt(binStr, 2);
		while (result < last) {
			binStr = findNext(result, len);
			printSubSet(A, binStr);
			result = Integer.parseInt(binStr, 2);
		}
	}

	public static void printSubSet(int[] A, String binaryString) {
		int len = binaryString.length();
		for (int i = 0; i < len; i++) {
			if (binaryString.charAt(i) == '1') {
				System.out.print(A[i] + " ");
			}
		}
		System.out.println();
	}

	// finds the next smallest number with same number of k bits set.
	public static String findNext(int n, int k) {
		StringBuffer sbuff = new StringBuffer();

		int l = Integer.toBinaryString(n).length();
		if (l < k) {
			for (int i = 1; i <= (k - l); i++) {
				sbuff.append('0');
			}
		}
		char[] ch = (sbuff.toString() + Integer.toBinaryString(n))
				.toCharArray();
		int len = ch.length;
		boolean switched = false;
		int index = 0;
		for (int i = len - 1; i >= 0; i--) {
			if (ch[i] == '1') {
				for (int j = i - 1; j >= 0; j--) {
					if (ch[j] == '0') {
						ch[j] = '1';
						ch[j + 1] = '0';
						index = j + 1;
						// System.out.println("J:" + j + " J+1:" + (j+1));
						switched = true;
						break;
					}
				}
				if (switched) {
					break;
				}
			}
		}
		int i = index + 1;
		int j = len - 1;

		while (i < j) {
			if (ch[i] == '1' && ch[j] == '0') {
				ch[i] = '0';
				ch[j] = '1';
				++i;
				--j;
			}
			++i;
		}
		StringBuffer sb = new StringBuffer();
		for (i = 0; i < len; i++) {
			sb.append(ch[i]);
		}

		return sb.toString();
	}

}

Inversions in an Array

For Array[0.....N-1], an inversion is an element pair that satisfes i<j and A[i]>A[j]. For instance, in array (1,3,5,2,4,6),  such pairs are (3,2) (5,2) (5,4), so number of inversions is 3.  The challenge is to implement an algorithm that computes the number of inversions with the array given to you.

Method1 (Brute Force Approach)

For each element, count number of elements which are on right side of it and are smaller than it.

public static int getInversionCount(int arr[])
	{
	  int invCount = 0;
	  int i, j;
	  int n = arr.length;
	 
	  for(i = 0; i < n - 1; i++)
	  {
	    for(j = i+1; j < n; j++)
	    {
	      if(arr[i] > arr[j])
	    	  invCount++;
	    }
	  }
	 
	  return invCount;
	}

Method2 ( Merge Sort Approach)

Suppose we know the number of inversions in the left half and right half of the array (let be inv1 and inv2), what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is – the inversions we have to count during the merge step. Therefore, to get number of inversions, we need to add number of inversions in left subarray, right subarray and merge().


How to get number of inversions in merge()?


In merge process, let i is used for indexing left sub-array and j for right sub-array. At any step in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j]

/* An auxiliary recursive function that sorts the input array and
	  returns the number of inversions in the array. */
	public static int mergeSort(int arr[], int temp[], int left, int right)
	{
	  int mid, invCount = 0;
	  if (right > left)
	  {
	    // Divide the array into two parts and call _mergeSortAndCountInv()
	    //   for each of the parts 
	    mid = (right + left)/2;
	  
	    // Inversion count will be sum of inversions in left-part, right-part
	    //  and number of inversions in merging 
	    invCount  = mergeSort(arr, temp, left, mid);
	    invCount += mergeSort(arr, temp, mid+1, right);
	  
	    //Merge the two parts
	    invCount += merge(arr, temp, left, mid+1, right);
	  }
	  return invCount;
	}
	  
	// This function merges two sorted arrays and returns inversion count in
	//  the arrays.
	public static int merge(int arr[], int temp[], int left, int mid, int right)
	{
	  int i, j, k;
	  int inv_count = 0;
	  
	  i = left; // i is index for left subarray
	  j = mid;  // i is index for right subarray
	  k = left; // i is index for resultant merged subarray
	  while ((i <= mid - 1) && (j <= right))
	  {
	    if (arr[i] <= arr[j])
	    {
	      temp[k++] = arr[i++];
	    }
	    else
	    {
	      temp[k++] = arr[j++];
	      inv_count = inv_count + (mid - i);
	    }
	  }
	  
	  // Copy the remaining elements of left subarray
	  // (if there are any) to temp
	  while (i <= mid - 1)
	    temp[k++] = arr[i++];
	  
	  // Copy the remaining elements of right subarray
	  // (if there are any) to temp
	  while (j <= right)
	    temp[k++] = arr[j++];
	  
	  // Copy back the merged elements to original array
	  for (i=left; i <= right; i++)
	    arr[i] = temp[i];
	  
	  return inv_count;
	}
	  

Subset Sum

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

The previous post talks about recursive approach which has exponential complexity

Lets see a dynamic programming approach which has polynomial complexity.

// Returns true if there is a subset of set[] with sun equal to given sum
	public static boolean isSubsetSumDynamic(int set[], int n, int sum)
	{
	    // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
	    //  with sum equal to i
	    boolean subset[][] = new boolean[sum+1][n+1];
	 
	    // If sum is 0, then answer is true
	    for (int i = 0; i <= n; i++)
	      subset[0][i] = true;
	 
	    // If sum is not 0 and set is empty, then answer is false
	    for (int i = 1; i <= sum; i++)
	      subset[i][0] = false;
	 
	     // Fill the subset table in bottom up manner
	     for (int i = 1; i <= sum; i++)
	     {
	       for (int j = 1; j <= n; j++)
	       {
	         subset[i][j] = subset[i][j-1];
	         if (i >= set[j-1])
	           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];
	       }
	     }
	     return subset[sum][n];
	}

Subset sum

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

 

public class SubsetSum {

	public static boolean isSubsetSum(int set[], int n, int sum)
	{
	   if (sum == 0)
	     return true;
	   if (n == 0 && sum != 0)
	     return false;
	 
	   if (set[n-1] > sum)
	     return isSubsetSum(set, n-1, sum);
	 
	   return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
	}
	 
	public static void main(String args[])
	{
	  int set[] = {3, 34, 4, 12, 5, 2};
	  int sum = 9;
	  
	  if (isSubsetSum(set, set.length, sum) == true)
	     System.out.println("Found a subset with given sum");
	  else
	     System.out.println("No subset with given sum");
	}
	
}

Continuous sub array adding to a number

Given an array having positive integers, find a continuous sub array which adds to a given number.?

Complexity:

Despite having two nested loops, this code runs in linear time because i and j never decrease, and can only be incremented O(N) times.

public class ContinousSum {

	public static void findContinousArray(int A[], int target) {
		for (int i = 0, j = 0, sum = 0; i < A.length; i++) {
			while(j < A.length && sum < target) {
				sum += A[j];
				if(sum >= target)break;
				j++;
			}
			if (sum == target) {
				System.out.println("sub array indices" + i + "," + j);
				return;
			}
			sum -= A[i];
		
		}

	}

	public static void main(String[] args) {
		int a[] = { 1, 2, 3, 4 };
		findContinousArray(a, 5);

	}
}

Postfix expression evaluation

Algorithm:

for each expression token:
  if the token is a number:
    push it
  else (the token is an operator, OP):
    second = pop();
    first = pop();
    compute: result = first OP second
    push the result on the stack

when there are no more tokens, pop the answer off the stack

4 2 3 - -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  3      [3, 2, 4]
  -      [-1, 4]
  -      [5]
 END     []    ⇒ answer = 5

public static Double evaluatePostfix(String rpn) {
		char[] exp = rpn.toCharArray();
		Stack<Double> stack = new Stack<Double>();

		int len = exp.length;
		for (int i = 0; i < len; i++) {
			if (!isOperator(exp[i])) {
				stack.push(Double.parseDouble("" + exp[i]));
			} else {
				double b = stack.pop();
				double a = stack.pop();
				stack.push(evaluate(a, b, exp[i]));
			}
		}
		double result = stack.pop();
		System.out.println("Result:" + result);
		return result;
	}

	private static Double evaluate(double a, double b, char operator) {
		double result = 0.0;
		switch (operator) {
		case '/':
			result = a / b;
			break;
		case '*':
			result = a * b;
			break;
		case '+':
			result = a + b;
			break;
		case '-':
			result = a - b;
			break;
		}
		return result;
	}

Infix to postfix Conversion

Algorithm:

for each expression token:
  if the token is a number:
    add it to output
  else if the token is a left paren:
    push it
  else if the token is a right paren:
    pop and add to output all tokens on stack up to left paren
    pop the left paren, but don't add to output
  else if the token is an operator:
    if stack is empty or the top is a left paren:
       push it
    else if the stack top is a lower precedence operator:
       push it
    else
       pop and add to output all operators of higher or equal precedence 
       push it

when there are no more tokens,
  pop and add to output all remaining operators on stack

Example:

7 - 3 + 5 - 2

token   stack     output
-----   -----     ------
        []
  7               7
  -     [-]
  3               7 3
  +     [+]       7 3 -
  5               7 3 - 5
  -     [-]       7 3 - 5 +
  2               7 3 - 5 + 2
 END    []        7 3 - 5 + 2 -

Code:

import java.util.*;

public class InfixToPostfix {
	
	// Translate's the expression to postfix
	public static String translate(String expression) {

		String output = "";
		char character = ' ';
		Stack<Character> stack = new Stack<Character>();

		for (int x = 0; x < expression.length(); x++) {
			character = expression.charAt(x);

			if (isOperator(character)) {
				while (!stack.empty()
						&& precedence(stack.peek()) >= precedence(character))
					output += stack.pop() + " ";
				stack.push(character);
			} else if (character == '(') {
				stack.push(character);
			} else if (character == ')') {
				while (!stack.peek().equals('('))
					output += stack.pop() + " ";
				stack.pop();
			} else {
					output += character;
			}
		}

		while (!stack.empty()) {
			output += stack.pop() + " ";
		}

		return output;
	}

	// Check priority on characters
	public static int precedence(char operator) {
		if (operator == '+' || operator == '-')
			return 1;
		else if (operator == '*' || operator == '/')
			return 2;
		else
			return 0;
	}

	public static boolean isOperator(char element) {
		if (element == '*' || element == '-' || element == '/'
				|| element == '+')
			return true;
		else
			return false;
	}
	
	public static void main(String args[])
	{
		System.out.println("Postfix conversion"+InfixToPostfix.translate("((2 * 3) - 5) / 4"));
		
	}
}

Maximum Contiguous Subsequence Sum of At Least Length L.

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) of length atleast L for which the sum of elements in the subsequence is maximized.

Set sumL to the sum of the first L array elements.
Set runningSum = sumL.
Set maxSum = sumL
For k = L + 1 up to n, the length of the array:
Set sumL = sumL + A(k) - A(k - L)
Set runningSum = max(runningSum + A(k), sumL)
Set maxSum = max(maxSum, runningSum)
Output maxSum

public class MaxContSumL {
	public static void main(String[] args) {
		int[] A = { 0, 5, -3, -1, 2, -4, -1, 7, 8 };
		int L = 2;
		maxContiguousSumOfLenAtleastL(A, L);

		int[] B = { -5, -1, 2, -3, 0, -3, 3, };
		L = 3;
		maxContiguousSumOfLenAtleastL(B, L);
	}

	public static void maxContiguousSumOfLenAtleastL(int[] A, int L) {
		int len = A.length;
		int sumL = 0;
		for (int i = 0; i < L; i++) {
			sumL += A[i];
		}
		int runningSum = sumL;
		int maxSum = sumL;
		int start = 0, finish = 0;
		for (int i = L; i < len; i++) {
			sumL += (A[i] - A[i - L]);
			runningSum = Math.max(runningSum + A[i], sumL);
			
			if (runningSum > maxSum) {
				maxSum = runningSum;
				start = i - L + 1;
				finish = i;
			}
		}

		System.out.println("Max sum: " + maxSum);
		System.out.println("Indices: i=" + start + " : j=" + finish);
	}
}

Largest rectangle area in histogram

Given an array of positive integers that represent the bars in a histogram,
find the rectangle with the largest area under the curve and above the axis

import java.util.Stack;

public class Histogram {
	public static void main(String[] args) {
		int[] A = { 4, 1, 6, 3, 4, 7, 5, 2 };
		int area = largestRectangleArea(A);

		System.out
				.println("reactange with largest area under the curve and above the axis: "
						+ area);
	}

	public static int largestRectangleArea(int[] height) {

		Stack<Integer> stack = new Stack<Integer>();
		int i = 0, max = 0;
		while (i < height.length) {
			if (stack.isEmpty() || height[stack.peek()] <= height[i])
				stack.push(i++);
			else
				max = Math.max(max, height[stack.pop()]
						* (stack.isEmpty() ? i : i - stack.peek() - 1));
		}
		while (!stack.isEmpty())
			max = Math.max(max, height[stack.pop()]
					* (stack.isEmpty() ? i : i - stack.peek() - 1));
		return max;
	}

}

Print 2 BSTs in ascending order

Give two binary search trees, print the numbers of both together in ascending order.

import java.util.Random;
import java.util.Stack;

public class BST {
	public static Node root1 = null;
	public static Node root2 = null;
	public static final int N = 7;
	public static final int RANGE = 100;

	public static void main(String[] args) {
		System.out.println("Building first BST with values:");
		root1 = buildBST(root1);

		System.out.println("Building second BST with values:");
		root2 = buildBST(root2);

		System.out.println("printing 2 BSTs in ascending order: ");
		printTwoBSTsInorder(root1, root2);
	}

	public static void printTwoBSTsInorder(Node r1, Node r2) {
		Stack<Node> stk1 = new Stack<Node>();
		Stack<Node> stk2 = new Stack<Node>();
		boolean isFinished = false;
		while (!isFinished) {
			if (r1 != null && r2 != null) {
				stk1.push(r1);
				r1 = r1.left;
				stk2.push(r2);
				r2 = r2.left;
			} else if (r1 != null && r2 == null) {
				stk1.push(r1);
				r1 = r1.left;
			} else if (r1 == null && r2 != null) {
				stk2.push(r2);
				r2 = r2.left;
			} else if (r1 == null && r2 == null) {
				if (!stk1.isEmpty() && stk2.isEmpty()) {
					r1 = stk1.pop();
					System.out.print(r1.data + " ");
					r1 = r1.right;
				} else if (stk1.isEmpty() && !stk2.isEmpty()) {
					r2 = stk2.pop();
					System.out.print(r2.data + " ");
					r2 = r2.right;
				} else if (!stk1.isEmpty() && !stk2.isEmpty()) {
					if (stk1.peek().data <= stk2.peek().data) {
						r1 = stk1.pop();
						System.out.print(r1.data + " ");
						r1 = r1.right;
					} else {
						r2 = stk2.pop();
						System.out.print(r2.data + " ");
						r2 = r2.right;
					}
				} else {
					isFinished = true;
				}
			}
		}
	}

	public static Node buildBST(Node node) {
		Random rand = new Random();

		for (int i = 0; i < N; i++) {
			int value = rand.nextInt(99) + 1;
			System.out.print(value + " ");
			node = insertIntoBST(node, value);
		}
		System.out.println();
		return node;
	}

	public static Node insertIntoBST(Node node, int value) {
		if (null == node) {
			return new Node(value);
		}
		if (value <= node.data) {
			node.left = insertIntoBST(node.left, value);
		} else {
			node.right = insertIntoBST(node.right, value);
		}
		return node;
	}
}

class Node {
	int data;
	Node left;
	Node right;

	public Node(int data) {
		this.data = data;
		this.left = null;
		this.right = null;
	}
}