Amazon Interview Question
Software Engineer / DevelopersThe solution given above is an implementation of the Knuth algorithm. Please stop acting like a jerk and do some research before posting something.
class Card
{
String type;
int value;
int randomVal;
boolean struck;
Card(String type,int value,int randomVal)
{
this.type = type;
this.value = value;
this.randomVal = randomVal;
struck=false;
}
}
List<Card> deck = new ArrayList<Card>();
void initializeSpade()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Spade",i,randomVal);
deck.add(card);
}
}
void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
deck.add(card);
}
}
void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
deck.add(card);
}
}
void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
deck.add(card);
}
}
public Card[] perfectShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
Card[] originalList = new Card[52];
for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}
int iter=51;
while(iter>0)
{
iter--;
int randomVal = (int)((Math.random()*100)%iter);
Card temp = originalList[iter];
originalList[iter]=originalList[randomVal];
originalList[randomVal]=temp;
}
System.out.println("Number of iterations are : " + iter);
return originalList;
}
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import javax.print.attribute.standard.OrientationRequested;
public class CardShuffling {
class Card
{
String type;
int value;
int randomVal;
boolean struck;
Card(String type,int value,int randomVal)
{
this.type = type;
this.value = value;
this.randomVal = randomVal;
struck=false;
}
}
List<Card> deck = new ArrayList<Card>();
void initializeSpade()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Spade",i,randomVal);
deck.add(card);
}
}
void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
deck.add(card);
}
}
void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
deck.add(card);
}
}
void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
deck.add(card);
}
}
public Card[] quadraticShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
int[] sortedArr = sort();
//for(int i=0;i<sortedArr.length;i++)
// System.out.println(sortedArr[i]);
Card[] card = reArrange(sortedArr);
return card;
}
public int[] sort()
{
int arr[]= new int[deck.size()];
for(int i=0;i<arr.length;i++)
{
arr[i] = deck.get(i).randomVal;
}
Arrays.sort(arr);
return arr;
}
public int binarySearch(int[] arr,int left,int right,int val)
{
int mid=(left+right)/2;
if(arr[mid]==val)
return mid;
else if(arr[mid]>val)
return (binarySearch(arr,left,mid-1,val));
else if(arr[mid]<val)
return (binarySearch(arr,mid+1,right,val));
else
return -1;
}
public Card[] reArrange(int[] arr)
{
Hashtable<Integer,List<Card>> cardKey = new Hashtable<Integer,List<Card>>();
for(int i=0;i<deck.size();i++)
{
int pos = binarySearch(arr, 0, arr.length-1, deck.get(i).randomVal);
if(cardKey.containsKey(pos))
{
List<Card> cardList = cardKey.remove(pos);
cardList.add(deck.get(i));
cardKey.put(pos,cardList);
}
else
{
List<Card> cardList = new ArrayList<Card>();
cardList.add(deck.get(i));
cardKey.put(pos,cardList);
}
}
Set set = cardKey.keySet();
Iterator it = set.iterator();
Card[] card = new Card[deck.size()];
for(int t=0;t<card.length;)
{
while (it.hasNext())
{
System.out.println();
List<Card> cardList = cardKey.get(it.next());
for(int i=0;i<cardList.size();i++)
{
card[t] = cardList.get(i);
t++;
}
}
System.out.println("Final value of t : " + t);
}
return card;
}
public Card[] linearShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
Card[] originalList = new Card[52];
Card[] shuffledList = new Card[52];
for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}
int count=0;
int remainCards = 52;
int iter=0;
while(count<52)
{
iter++;
int randomVal = (int)((Math.random()*100)%52);
if(originalList[randomVal].struck==false)
{
originalList[randomVal].struck=true;
shuffledList[count]=originalList[randomVal];
count++;
remainCards--;
}
}
System.out.println("Number of iterations are : " + iter);
return shuffledList;
}
public Card[] perfectShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
initializeSpade();
Card[] originalList = new Card[52];
for(int i=0;i<deck.size();i++)
{
originalList[i]=deck.get(i);
}
int iter=51;
while(iter>0)
{
iter--;
int randomVal = (int)((Math.random()*100)%iter);
Card temp = originalList[iter];
originalList[iter]=originalList[randomVal];
originalList[randomVal]=temp;
}
System.out.println("Number of iterations are : " + iter);
return originalList;
}
public static void main(String[] args) {
CardShuffling obj = new CardShuffling();
//Card[] card = obj.quadraticShuffle();
//Card[] card = obj.linearShuffle();
Card[] card = obj.perfectShuffle();
int count=0;
for(int i=0;i<card.length;i++)
{
System.out.println();
if(card[i]!=null)
{
count++;
System.out.print(" ");
System.out.print(card[i].type);
System.out.print(" ");
System.out.print(card[i].value);
System.out.print(" ");
System.out.print(card[i].randomVal);
}
}
System.out.println();
System.out.println("count is: " + count);
}
}
- Anonymous November 12, 2009