Random Number Interview Question

[kinley]

Hi, I had this question in my internship interview today and they only wanted to know the pseudocode.

Input: A bag of balls with numbers from 1 to 52
Output: A sequence of random numbers between 1 and 52 of length 16 such that if a number x exists in the sequence, there must be one more x in the sequence somewhere.
For e.g. following are valid sequences
17, 28, 9, 10, 9, 2, 36, 51, 10, 28, 51, 7, 7, 17, 36, 2

1, 1, 18, 26, 5, 3, 43, 1, 43, 1, 26, 3, 18, 5, 8, 8

Following is the pseudocode I wrote

Declare arr of length 16
Declare first_half of length 8
Initialize srand (time(NULL));
Declare number

For i = 0 through 7
 arr[i] = rand() % 52 + 1 
 first_half[i] = arr[i]
End For

For i = 8 through 15
  number = rand() % 52 + 1
  if (number exists in first_half array)
    arr[i] = number;
  else
    while(number not exists in first_half array)
      number = rand() % 52 + 1
    end while
  end if
End for 

My main logic was that whatever sequence I get from 0 to 7, I have to duplicate it in different position from 8 to 15.

Time ran out and I couldn't spend much time.

In the evening, I tried to implement it but don't get correct sequence.

Please let me know your thoughts?

[Duthomhas]

Generate the sequence 1,2,...,52.
Randomize it.
Pick the first 8 numbers; discard the rest.
Duplicate the sequence (thereby doubling its size).
Randomize it.

[kinley]

Hi Duoas,

I do not quite understand your last Randomize statement.

Say at the end of statement 3, I have a following sequence

1, 7, 2, 1, 9, 48, 10, 3

I then duplicate it. So it becomes

1, 7, 2, 1, 9, 48, 10, 3, 1, 7, 2, 1, 9, 48, 10, 3

How do I randomize this sequence since the pattern follows after 8th ball?

Thank you

[cire]

http://en.cppreference.com/w/cpp/algorithm/random_shuffle

Demo: https://ideone.com/PJwaqS

[kinley]

Thank you very much!

Also, found this topic https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle