Wednesday, September 11, 2013

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

}

Monday, September 9, 2013

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