Morgan Stanley Interview Question for Software Engineer / Developers






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

Im not sure what Lance means by randomly sorting.

I 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.

- Sundar May 16, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is to generate a sequence of songs' position.
loop all songs and get the remainder of the random_number divided by the number of songs each time to determine this song's play position in the sequence.

- rp March 15, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- vel March 22, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

list all the songs, or their positions, randomly sort that list. Play them in that order.
Discuss that what people think of as 'random' is not truly random. People have a tendency to think that if too many songs of one artist show up your ipod is beig tricky/psychic

- Lance October 11, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use HashSet generic collection in java to sort and add the songs which uses overriden hashCode() and equals() methods of String class to check if two songs are equal. If they are equal then it wont add that song and that way we can play songs.

- Anonymous March 17, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Build an container to save all the number ID of the songs,say 1 to n. And random access these number and play the song, after that, remove the number from the container. After N times random access, all the songs are played by once. And then we keep doing that...

- masterwoo September 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- YetAnotherCoder September 30, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for(i=n;i>0;i--)
{
curr=rand()%i;
play(curr);
swap(curr,i);

}

- Anonymous August 16, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Fisher–Yates shuffle, used for cards shuffling Can be used here too.

- gaurav August 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

or you could just swap it with last element after playing it, and then decrease an auxiliary size.

1: choose any random%size
2: play it
3: swap it with last
4: decrease size
5: repeat while(size>=0)

- imrohitkhatri July 02, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

jhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh hjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkjkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkj k k kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk k kkkkkkkkkkkkkkkkkk kkkkkkkk kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk mmmmmmmmmmmm

- Anonymous April 24, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous March 22, 2023 | Flag Reply


Add a Comment
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.

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