## Microsoft Interview Question

Software Developers**Country:**Israel

**Interview Type:**Phone Interview

```
String[] songs = {"Muse - Dead Inside","Scorpions - Send Me An Angel",
"RHCP - Californication","Scorpions - Wind of Change","Muse - Psycho",
"Metallica - Fade to Black","Apple - Binary Symphony"};
ArrayList <String> array = new ArrayList<>();
System.out.println("UNSORTED LIST");
for(int i=0;i<=100;i++) {
int randnum = (int) Math.floor(Math.random() * songs.length);
for (int i1=0; i1<=array.size(); i1++){
if (!array.contains(songs[randnum])){
System.out.println(songs[randnum]);
array.add(songs[randnum]);
}
}
}
Set<String> seted = new TreeSet<>(array);
Object[] objects = ((TreeSet<String>) seted).headSet(String.valueOf(((TreeSet<String>) seted).isEmpty())).toArray();
System.out.println();
System.out.println("SORTED LIST(ALPHABETICALLY)");
for (int i = 0; i<objects.length; i++) {
System.out.println(objects[i]);
}
```

```
var songs [
{
id: 1,
song: "doom dom"
},
{
id: 100,
song: "all other songs in between"
}
]
let playedSongs = [];
function findNextSong() {
let nextSongId = songs.length * Math.random();
if(playedSongs.includes(nextSongId)){
findNextSong()
}
playedSongs.push(nextSongId);
return nextSongId;
}
shuffle() {
const nextSongId = findNextSong();
return playSong(nextSongId);
}
playSong(songId) {
// write play song algorithm here
}
```

```
var songs = [
{
id: 1,
song: "doom dom"
},
{
id: 100,
song: "all other songs in between"
}
]
let playedSongs = [];
function findNextSong() {
let nextSongId = songs.length * Math.random();
if(playedSongs.includes(nextSongId)){
findNextSong()
}
playedSongs.push(nextSongId);
return nextSongId;
}
function shuffle() {
const nextSongId = findNextSong();
return playSong(nextSongId);
}
function playSong(songId) {
// write play song algorithm here
```

}

var songs = [

{

id: 1,

song: "doom dom"

},

{

id: 100,

song: "all other songs in between"

}

]

let playedSongs = [];

function findNextSong() {

let nextSongId = songs.length * Math.random();

if(playedSongs.includes(nextSongId)){

findNextSong()

}

playedSongs.push(nextSongId);

return nextSongId;

}

function shuffle() {

const nextSongId = findNextSong();

return playSong(nextSongId);

}

function playSong(songId) {

// write play song algorithm here

}

There is a much much simpler solution for this problem that uses constant memory for 100 songs. we listen to the first song, then we skip two. for 10 songs it looks like this:

1, 4, 7, 10

then we wrap around skipping 1 and 2:

3, 6, 9

then we wrap around again:

2, 5, 8

so we have listened to all the songs not in order without any memory with strides of 3, user 2 can do this with strides of 6 and user 3 can do it with strides of 9

this algorithm works for any number such that for stride x:

N % x = 1

Initiate random number with value 0 to n. get a number from this function and then swap this number with last number of array. then call the random fucntion with 0 to n-1... and swap the number with n-1 index and repeat the process.

- sandeepmnit35 July 10, 2018