Morgan Stanley Interview Question
Software Engineer / Developers@rp: ur method does not ensure non-repetition.
Suppose the number of songs is 10. If succesive random numbers generated are for eg. 40 and 80 (or any multiple of 10), the song at the 0th position is played.
One means to solve this is to delete the song after playing it. If thats not permitted, I guess an extra data structure, that flags the songs as played and not-played is unavoidable.
0 to n-1 songs in array songs
song[i] - represent song at position i
= total number of songs
Rand()- generate number between 0 and 1
(N*Rand() + M) random number generated between M and N
for (i =0 to n-1)
.....CurSong=(n-i)*Rand()
.....play ( CurSong)
.....swap(CurSong,n-1)
Please comment
jhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh hjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkj k k kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk k kkkkkkkkkkkkkkkkkk kkkkkkkk kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk mmmmmmmmmmmm
public static IEnumerable<int> RandomIndexes(int count)
{
if (count > 0)
{
int[] indexes = new int[count];
int indexesCountMinus1 = count - 1;
for (int i = 0; i < count; i++)
{
indexes[i] = i;
}
Random random = new Random();
while (indexesCountMinus1 > 0)
{
int currIndex = random.Next(0, indexesCountMinus1 + 1);
yield return indexes[currIndex];
indexes[currIndex] = indexes[indexesCountMinus1];
indexesCountMinus1--;
}
yield return indexes[0];
}
}
Im not sure what Lance means by randomly sorting.
- Sundar May 16, 2008I would use a dovetail shuffle (a card shuffle technique). Pick a random thickness and a random start.
|--------(------)-------|
becomes
(------)|---------------|
after the shuffle.
and repeat this a 2log(n) number of times. And then play from begin to end.
A doubly linked list as input makes this process very easy.
Google "dovetail shuffle diaconis" to know why a dovetail shuffle makes the order random very fast.
This is O(log n).
If you are allowed to make a random choice after every choice has completed, this can be interleaved with the playing of songs by
making the first shuffle, and playing the first song, and then shuffling again but putting the dovetail under the first song, and continue from the second. The advantage is you don't have to call the random function generator after you've gone through O(log n) songs.