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

	}

}