Efficient Array Randomization Method - Random Code

Question

I was asked this question in an interview, and I gave various solutions, but the interviewer was not convinced. I am interested in finding a solution. Please enter your opinions:

Q: Write an efficient data structure for implementing shuffling on ipod. He must play all the songs, each time in different random order, the same song should not be repeated. (mostly O (n))

One solution I thought after the interview: I can do a randomized quick sort without recursion. Where we randomly selected 1 pivot O (1) and then do quicksort O (n). Now the songs will be sorted in a certain order, and I will play them to the end. As soon as it reaches the end, I will again select a random rod and repeat this process again and again.

Regards, Sethu

Answer 1

Put all the songs in an array ... For each element of the array, change it to a random position.

Answer 2

You want a fisher-yates shuffle . Be aware of the implementation errors mentioned on this page as your currently accepted answer does not match one.

Answer 3

, , :

, O (n) (, - ). , , ( ).

O (n) + a O (n) + O (n). .

. . , . , .

Answer 4

Nate () - Fisher-Yates O (n), - O (nlogn), (http://en.wikipedia.org/wiki/Fisher% E2% 80% 93Yates_shuffle # Comparison_with_other_shuffling_algorithms). , - , , , (http://www.cigital.com/news/index.php?pg= & artid = 20).

Answer 5

, , , - , .

, . , , , ( , ), k, k , ( ), O ( 2n) O (3n) . , node . , ( node), node node, O (1) . , .

, .