Amazon Interview Question
Country: India
Interview Type: Phone Interview
Can we not use a Map? The keys would be name of the song presented to the user and values would be the actual media files. This covers random access in O(1). Map implementations like LinkedHashMap in java can also allow ordered access which solved the sequential access issue. Please add to this discussion if you feel this is not appropriate.
1. ArrayList we will use for above condition, because ArrayList allows random access because array works at the index basis.
2. We can play in sequential manner or random as well, in sequential its not a problem, but in random access before accessing the song we have to compare the index value with some array values which have same length as ArrayList and value as index number, if we have play that array index value than we have to remove that value from array, so we can run songs by random without repetition.
The problem looks a little abstract, there probably should be some clarification questions that would affect the answer.
For example what exactly "song" means here (just a media file or a media file + separate metadata or something else) or what other features our player should have (should it have music searching or classifying by artist/genre, etc.) are there any space limitations, can we change the data structure, should our player stop after playing all the songs, etc.
Here's a solution, assuming that music is stored on a file system and our player just takes an array of file paths as input (or we can recursively find those file paths from a given directory instead) and plays files randomly one by one and then stop. O(n) time, O(1) space, Python 2.
import random
def play(file_name):
print 'playing', file_name
def play_random_music(music_files):
last = len(music_files) - 1
while last >= 0:
index = random.randint(0, last)
play(music_files[index])
music_files[index] = music_files[last]
last -= 1
music_files = ['music/%s.ogg' % i for i in 'abcdef']
play_random_music(music_files)
/**
*
*/
package com.divyanshu.song;
import java.io.File;
import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
/**
* @author Divyanshu
*
*/
public class MediaPlayer {
/**
* @param args
*/
public static void main(String[] args) {
HashMap<String, File> map = new HashMap<>();
List<String> indices = new ArrayList<>();
String basePath = "E:\\Archive\\Desktop 14 Jan 2016\\MP3";
loadPlayList(basePath, map, indices);
playRandomSongs(map, indices);
}
private static void playRandomSongs(HashMap<String, File> map,
List<String> indices) {
Random random = new Random();
for (int i = indices.size() - 1; i >= 0; i--) {
if (i == 0) {
System.out.println("Playing Song : " + (map.get(indices.get(i))).getName());
} else {
int nextSong = random.nextInt(i);
swap(indices, nextSong, i);
System.out.println("Playing Song : " + (map.get(indices.get(i))).getName());
}
}
}
private static void swap(List<String> indices,
int nextSong,
int i) {
String temp = indices.get(nextSong);
indices.set(nextSong, indices.get(i));
indices.set(i, temp);
}
private static void loadPlayList(String basePath,
HashMap<String, File> map,
List<String> indexes) {
File baseDirectory = new File(basePath);
if (baseDirectory.isDirectory()) {
File[] files = baseDirectory.listFiles();
for (File file : files) {
map.put(file.getName(), file);
indexes.add(file.getName());
}
} else {
throw new InvalidParameterException("Invalid base path. It must be the path of a directory.");
}
}
}
The songs themselves are write once, read rest of the song's lifetime. So, I would not change the way the song is stored...a sequentially written file.
- smallchallenges March 18, 2016The directory that maintains the list of songs could and will be randomly accessed. So, this directory data structure needs to support random directory reads. In addition, it seems that a consecutive play should not repeat a song i.e. this calls for sequential directory reads.
One good data structure that supports both efficient random reads (lg n) and supports sequential reads is a btree. Other structures like a skiplist provides both random and sequential access with its own tradeoffs.
Lemme know what you guys think...