Amazon Interview Question Software Engineer / Developers




Comment hidden because of low score. Click to expand.
0
of 0 vote

for(int i = 0; i< 52; i++)
{
  int j = rand(i, 52);
  if(i != j)
  {
      int temp = cards[i];
      cards[i] = cards[j];
      cards[j] = temp;
  }
}

- Anonymous on November 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int j = rand(i, 52);

make it

int j = rand(1, 52);

- Anonymous on November 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

LMAO!

Non-uniform probability.

Go home and study more math

- geniusxsy on November 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The solution given above is an implementation of the Knuth algorithm. Please stop acting like a jerk and do some research before posting something.

- Arjun on November 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Knuth shuffle starts from a[51] rather than a[0] I think.

Starting from a[0] is not uniform apparently, and it looks like geniusxsy is right.

- Anonymous on November 14, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Think about it, why it's non-uniform?
If you still don't get it, try N=3, enumerate all possibilities.

- geniusxsy on November 12, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Knuth Shuffle

http://en.wikipedia.org/wiki/Knuth_shuffle

- Anonymous on November 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use Knuth Shuffle

http://en.wikipedia.org/wiki/Knuth_shuffle

- Coder on November 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nice

- Anonymous on November 13, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

what nice?

- Synonymous on December 23, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous on January 06, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 on January 06, 2010 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More