## Amazon Interview Question for Software Engineer / Developers

• 0

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

public void shuffle()
{
for ( int i = 0; i < deck.length; i++ )
{
int j = ( int ) ( Math.random() * 52 );
Card temp = deck[ i ]; // swap
deck[ i ] = deck[ j ];
deck[ j ] = temp;
}
}

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

But still there are chances that card can come at same location because random can give you same position as present. As per the question there should not be even slightest chance of happening that.

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

I would use same code but just put some conditions
1. i != j
2. if swaped (i, j) then should not swap (j, i) in future....

does it make sense ?

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

move every card to its next position

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

Well it will be a known swap rather then a shuffle. First criteria of shuffle is the new position should not be known.

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

public void shuffle()
{
for ( int i = 51; i >= deck.length; i-- )
{
int j;
do {
j = ( int ) ( Math.random() * i );
}
while (j == i); // to check if getting same postion as before
Card temp = deck[ i ]; // swap
deck[ i ] = deck[ j ];
deck[ j ] = temp;
}
}

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

what is the guarantee that it will terminate in reasonable time?

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

if j becomes equal to i, this code goes into infinite loop

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

``````public void shuffle(Card[] deck)
{
for ( int i =  deck.length - 1; i > 0; i-- )
{
int j = ( int ) ( Math.random() * (i - 1) );
Card temp = deck[ i ]; // swap
deck[ i ] = deck[ j ];
deck[ j ] = temp;
}
}``````

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

i think if we consider the shuffle as a real life scenario, it wont be a single card to another card swap. Basically its like moving k cards from down to the top. in other words its basically k elements rotation problem.

Considering that, we can first generate a random number (say N) which will indicate the number of times shuffle will be done. Next we have to generate N random numbers(basically N different values of k).
To ensure the above stated criteria, keep on adding these N k-values.(k1+k2+...kN).
If the sumofKs%sizeofdeck, that will indicate the relative displacement of each card. If it is 0 then keep on generating ks till the sumofKs%sizeofdeck=0.

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

``````#include <iostream>
#include <vector>
#include <ctime>
#include <cstdlib>

using namespace std;

int main() {
vector<int> cards(52);
for (int i = 0; i < 52; ++i) cards[i] = i;

srand(time(NULL));
for (int i = 0; i < 52; ++i) { // get a random permutation of 0..51
int j = rand() % (i + 1);
cards[i] = cards[j];
cards[j] = i;
}

for (int i = 0; i < 26; ++i) { // how to shuffle: swap pairs of cards
cout << cards[i] << " <-> " << cards[i + 26] << endl;
}

return 0;
}``````

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

1. Given an array of size 52 (indexes 0 to 51) we want to shuffle it such that no card will get the same position as previously.

2. Start from the end of the array i.e. at index 51. Generate a random number x between [0,50] using rand() and mod 51 operation. Swap arr[51] and arr[x].

3. Repeat the same step for the rest of the array. That is, in the second step go to index 50. Generate a random number x between [0,49]. Swap arr[50] and arr[x].

4. In the end you come to index 0. You don't have to worry about arr[0] not being swapped as when you were processing at index 1 it would have been definitely been swapped with arr[0].

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

guys..check the solution in CC book.

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

``````shuffle(int deck[])
{
for(i=51;i>=0;i--)
{
r=rand()%i;
t=deck[r];
deck[r]=deck[i];
deck[i]=t;
}
}``````

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

The main focus of the problem is not letting the card getting placed in the position it earlier occupied.
If there is no restriction of doing it in-place
Then we can maintain a hash table<card,pos> which would take card object as the key and position as the value. It updates the value after every successful shuffle.

So you can use any random number generator and before the swap first check if the resulting position is not the one it occupied earlier.
If yes then generate a new random number.
This would maintain the condition of not placing the card in its earlier position.

ps: Any random number generator, how good it might be would give duplicate values.

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

Its standard algorithm by Knuth.
For ith card, generate a random number below i, swap the card and decrement i.

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

I think i can come up with a more interesting algorithm.
Let the Deck of cards be an Array Deck[N]
1) Consider that you actually have a two decks. One deck of cards at odd indices, and one with even indices. O(1)
ie {D[0],D[2]....D[50]] and {D[1],D[3]...D[51]}
2) Now sort both the arrays separately by doing k swaps. where K << 52. O(k)
3) Now rotate the deck by one place, by putting odd elements in even places and even elements in odd places. O(N).

Email: sancho.nitw@gmail.com

Name:

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

### Books

is a comprehensive book on 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.