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

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

int j = rand(i, 52);

make it

int j = rand(1, 52);

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

LMAO!

Non-uniform probability.

Go home and study more math

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

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

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

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.

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.

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

Use Knuth Shuffle

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

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

Use Knuth Shuffle

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

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

nice

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

what nice?

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

{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
}
}

void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
}
}

void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
}

}

void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
}
}

public Card[] perfectShuffle()
{
initializeClub();
initializeDiamonds();
initializeHearts();
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;
}

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

{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
}
}

void initializeClub()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Club",i,randomVal);
}
}

void initializeHearts()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Hearts",i,randomVal);
}

}

void initializeDiamonds()
{
for(int i=1;i<=13;i++)
{
int randomVal = (int)((Math.random()*100)%52);
Card card = new Card("Diamonds",i,randomVal);
}
}

{
initializeClub();
initializeDiamonds();
initializeHearts();
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);
cardKey.put(pos,cardList);
}
else
{
List<Card> cardList = new ArrayList<Card>();
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();

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

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.

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.