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();
		}
	}

}