Amazon Interview Question Software Engineer / Developers




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

- Anonymous on December 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous on December 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- Ajay on December 19, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

move every card to its next position

- Anonymous on December 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on December 08, 2010 | Flag
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;
}
}

- Anonymous on December 08, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on December 08, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous on January 10, 2011 | Flag
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;
    }
}

- Anonymous on December 09, 2010 | Flag Reply
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.

- Hinax on December 13, 2010 | Flag Reply
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;
}

- maxxum on December 14, 2010 | Flag Reply
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].

- spookymulder83 on December 17, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

guys..check the solution in CC book.

- Newbie on January 04, 2011 | Flag Reply
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;
   }
}

- chiragjain1989 on January 09, 2011 | Flag Reply
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.

- ketz on January 09, 2011 | Flag Reply
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.

- Anil on January 28, 2011 | Flag Reply
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

- Sancho Sebastine on May 20, 2011 | 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