Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
Here is a possible solution:
For the data structures part: you could use an 'IndexedPriorityQueue<song, count>' (Hash map along with a heap for each song in the album).
Maintain a Trie (or one trie for each.. say, a server). The trie would have the album as the key and our IndexedPriorityQueue as value.
For maintaining the count, before increasing a count check if the count reaches the max of Double capacity. You may need to do some normalization of values. However, you might need to take care that the amortized worst case complexity would be still be O(number of songs in the album).
Since the number of songs is assumed to be small(<100) for each album. The reheapification process for heap won't affect the amortized run time complexity over the time.
Any constructive suggestions would be helpful. :-)
The class structure can be something like this,
public class MusicStore{
//SINCE THERE ARE HUGE NUMBER OF STRINGS. WE MAY USE A TRIE
Map trie = new Trie();
public void play(String album, String song){
if(!trie.contains(album)){
return;
}
/*
You increase the priority of the song in the data structure.
*/
IndexedPriorityQueue q = trie.get(album);
double delta = 1;
q.changePriority(song, delta);
}
public String topSong(String album){
// PULL OUT THE ALBUM AND THEN THE SONG WITH MAX COUNT.
IndexedPriorityQueue q = trie.get(album);
return q.getMax();
}
//METHOD STUB FOR ADDING SONGS AND ALBUMS
public addAlbumSong(String album, String song){
}
}
/*############################*/
private class IndexedPriorityQueue{
//HEAP IS USED FOR MAINTAINING THE TOP SONG.
private Queue heap;
// USED TO GET QUICK ACCESS TO THE SONG AND CHANGE THE COUNT.
private Map map;
//THIS WOULD ALLOW LARGE NUMBER OF PLAY COUNTS TO BE STORED.
private double scale;
public IndexedPriorityQueue(){
map = new Hashtable<String, Double>();
/*COMPARATOR IS USED TO FACILITATE THE FORMATION OF HEAP USING THE COUNT VALUES FROM MAP*/
Comparator<String> c = new Comparator<String>(){
int compareTo(String o1, String o2){
if(map.get(o1) < map.get(o2)){
return -1;
}
if(map.get(o1) > map.get(o2)){
return 1;
}
return 0;
}
};
heap = new PriorityQueue<String>(1,c);
}
public void changePriority(Strig key, int delta){
if(!hash.contains(key)){
/*GET THE COUNT CHANGE IT BY DELTA, AND PUT IT IN THE HASH. you might have to do some data transformation for the heap count before adding a new count.*/
hash.put(key, hash.get(key) + count);
//REHEAPIFY THE HEAP
heap.remove(key);
heap.add(key);
}else{
hash.put(key, 1);
heap.add(key);
}
}
public String getMax(){
//JUST GET THE TOP SONG.
return heap.peek();
}
}
Class Player
{
public:
void play(string bandName, string songName);
string topSong(string bandName);
private:
Hash<string bandName, Class Band> bands = new Hash<string, Class Band>();
}
Class Band
{
public:
string Name;
void play(string songName);
string topSong();
private:
Hash songs = new <string songName, Song songs>();
// Will ensure that the topSong variable is updated by one thread at a time
volatile song topSong;
}
Class Song
{
public:
Song song;
void IncrementRequest();
int GetNumberofRequests();
private:
int numberOfRequests; // initialized to 0 in the constructor
}
string topSong()
{
return this.topSong;
}
void play(string SongName)
{
// Assuming that in case of same number of plays, the latest song wins
if (topSpong.GetNumberOfRequests <= (song.GetNumberOfRequests + 1))
{
topSong = song;
}
song.incrementRequest();
song.play();
}
void IncrementRequest()
{
this.numberOfRequests++;
}
int GetNumberOfRequests()
{
return numberOfRequests;
}
I'd use a Hashtable with BandName as the key, and a sorted linkedlist of struct as the value. Every times a song is played, the linkedlist gets updated by removing the old Song and inserting a new song with song.times incremented.
Hashtable Band(string name, LinkedList<Songs> linkedList);
struct Songs
{
int times;
string title;
}
Hashtable within a Hashtable should do the job. The outer Hashtable has the albums and the inner Hashtable has the songs. The the outer Hashtable can also have a String and count for the top song and max play count along with the song map. This is depicted below using class albumDetails. These 2 fields keep getting updated each time a request to play comes in.
Class albumDetails ()
{
String *topSong;
int topSongCount;
HashTable *hashSongs;
}
void playSongs (String album, String song)
{
albumDetails *aAlbumDetail = (albumDetails*) hashTable [album];
Hashtable *hashSongs = aAlbumDetails.hashSongs;
int currentCount = hashSongs [song];
currentCount++;
hashSongs [song] = currentCount;
if (currentCount >= aAlbumDetails.topSongCount)
{
aAlbumDetails.topSongCount = currentCount;
aAlbumDetails.topSong = song;
}
}
String topSong (album)
{
albumDetails *aAlbumDetail = (albumDetails*) hashTable [album];
return aAlbumDetails.topSong;
}
main ()
{
// Loading data into memory.
HashTable albums = new HashTable <String, albumDetails>;
HashTable hashSongs = new HashTable <String, int>;
hashSongs ["Sweet Child Of Mine"] = 0;
hashSongs ["November Rain"] = 0;
hashSongs ["Welcome To The Jungle"] = 0;
albums ["Guns N Roses"] = new ablumDetails ("", 0, hashSongs);
:
:
}
I suggest a different approach - please tell me what I'm missing from the question.
Store is where the web services are directed at, it holds a hash table of the bands.
Getting a band takes an O(1) containing it takes O(#bands) space
public class Store {
Hashtable<String, Band> bands; //hash table - key is the band name
public void play(String band, String song) {
Band bReq = bands.get(band);
bReq.playSong(song);
}
String topSong(String band) {
Band bReq = bands.get(band);
return bReq.getTopSong();
}
}
The Band class holds a sorted LinkedList in order to make seaching for a specific
song when requested by play faster - we can search for a song with binary search,
therefore it will only take O(log(#songs)) to find it and takes O(#songs) to contain.
The top song is always held be a separate reference so it can be retried and updated
within O(1) - updating takes O(1) because searching for it already took O(log(#songs))
public class Song {
String name;
String freq;
String album; //not needed for this question
public Song(String name) {
this.name = name;
this.freq = 0; //initial value
}
void playSong() {
freq++;
... //actions related to actual playing
}
}
public class Band {
LinkedList<Song> songs;
Song topSong;
void addSong(String name) { songs.add(new Song(name)); }
void playSong(String name) {
Song s = songs.binarySearch(name);
s.playSong();
if(s.freq > topSong.freq)
topSong = s;
}
String getTopSong() { return topSong.name; }
}
We can perhaps replace the LinkedList with something else, even another Hashtable<String, Song> where the key is the song name and the value is the Song class. In this case the size will not change but the search for the song can be O(1)
We can have hash within a hash
Where Key is bandname and its value will be another hash which contains song as the key and value will be the number of times the song has been played.
{
Band1 => {
"Song1" => Count of number of times played
''Song2" => Count of number of times played
}
Band2 => {
"Song3" => Count of number of times played
''Song4" => Count of number of times played
}
}
I would use hash within a hash, where
Outerhash will have Bandname as the key and its value will be another hash containing songname as the key and number of times this song has been played as the value.
{
Band1 => {
song1 => count of times song1 played
song2 => count of times song2 played
}
Band2 => {
song3 => count of times song1 played
song4 => count of times song2 played
}
}
============================================================================================================================
CODE:
import java.util.HashMap;
import java.util.Map;
public class SongAlbum {
Map<String, Map<String, Integer>> band_song_count = new HashMap <String, Map<String, Integer>>();
public void play(String bandname, String songname){
System.out.println("BandName :" + bandname + " --->Song :" + songname);
//Increment the count for song played in the band_song_count hashmap
//first check if contains bandname key
Map tempMap = band_song_count.get(bandname);
if(band_song_count.containsKey(bandname))
{
if(tempMap.containsKey(songname)) {
int new_count = (int) tempMap.get(songname) + 1;
tempMap.put(songname, new_count);
}
else
{
tempMap.put(songname, 1);
}
}
else
{
band_song_count.put(bandname, tempMap = new HashMap<>());
band_song_count.get(bandname).put(songname, 1);
}
}
String topSong(String bandname) {
//parsing logic
String song_name = null;
int max_count = 0;
if(band_song_count.containsKey(bandname))
{
for(Map.Entry<String , Integer> t: band_song_count.get(bandname).entrySet())
{
if(t.getValue() > max_count)
{
song_name = t.getKey();
max_count = t.getValue();
}
}
}
System.out.println("Maximum Song played is: " + song_name + " Played " + max_count + " times" );
return song_name;
}
public void print(){
for(Map.Entry <String, Map <String, Integer>> t :this.band_song_count.entrySet()){
String bandIs = t.getKey();
for (Map.Entry<String,Integer> e : t.getValue().entrySet())
System.out.println("OuterKey:" + bandIs + " InnerKey: " + e.getKey()+ " VALUE:" +e.getValue());
}
}
}
I would use hash within a hash, where
Outerhash will have Bandname as the key and its value will be another hash containing songname as the key and number of times this song has been played as the value.
{
Band1 => {
song1 => count of times song1 played
song2 => count of times song2 played
}
Band2 => {
song3 => count of times song1 played
song4 => count of times song2 played
}
}
============================================================================================================================
CODE:
import java.util.HashMap;
import java.util.Map;
public class SongAlbum {
Map<String, Map<String, Integer>> band_song_count = new HashMap <String, Map<String, Integer>>();
public void play(String bandname, String songname){
System.out.println("BandName :" + bandname + " --->Song :" + songname);
//Increment the count for song played in the band_song_count hashmap
//first check if contains bandname key
Map tempMap = band_song_count.get(bandname);
if(band_song_count.containsKey(bandname))
{
if(tempMap.containsKey(songname)) {
int new_count = (int) tempMap.get(songname) + 1;
tempMap.put(songname, new_count);
}
else
{
tempMap.put(songname, 1);
}
}
else
{
band_song_count.put(bandname, tempMap = new HashMap<>());
band_song_count.get(bandname).put(songname, 1);
}
}
String topSong(String bandname) {
//parsing logic
String song_name = null;
int max_count = 0;
if(band_song_count.containsKey(bandname))
{
for(Map.Entry<String , Integer> t: band_song_count.get(bandname).entrySet())
{
if(t.getValue() > max_count)
{
song_name = t.getKey();
max_count = t.getValue();
}
}
}
System.out.println("Maximum Song played is: " + song_name + " Played " + max_count + " times" );
return song_name;
}
public void print(){
for(Map.Entry <String, Map <String, Integer>> t :this.band_song_count.entrySet()){
String bandIs = t.getKey();
for (Map.Entry<String,Integer> e : t.getValue().entrySet())
System.out.println("OuterKey:" + bandIs + " InnerKey: " + e.getKey()+ " VALUE:" +e.getValue());
}
}
}
I would use hash within a hash, where
Outerhash will have Bandname as the key and its value will be another hash containing songname as the key and number of times this song has been played as the value.
{
Band1 => {
song1 => count of times song1 played
song2 => count of times song2 played
}
Band2 => {
song3 => count of times song1 played
song4 => count of times song2 played
}
}
============================================================================================================================
CODE:
import java.util.HashMap;
import java.util.Map;
public class SongAlbum {
Map<String, Map<String, Integer>> band_song_count = new HashMap <String, Map<String, Integer>>();
public void play(String bandname, String songname){
System.out.println("BandName :" + bandname + " --->Song :" + songname);
//Increment the count for song played in the band_song_count hashmap
//first check if contains bandname key
Map tempMap = band_song_count.get(bandname);
if(band_song_count.containsKey(bandname))
{
if(tempMap.containsKey(songname)) {
int new_count = (int) tempMap.get(songname) + 1;
tempMap.put(songname, new_count);
}
else
{
tempMap.put(songname, 1);
}
}
else
{
band_song_count.put(bandname, tempMap = new HashMap<>());
band_song_count.get(bandname).put(songname, 1);
}
}
String topSong(String bandname) {
//parsing logic
String song_name = null;
int max_count = 0;
if(band_song_count.containsKey(bandname))
{
for(Map.Entry<String , Integer> t: band_song_count.get(bandname).entrySet())
{
if(t.getValue() > max_count)
{
song_name = t.getKey();
max_count = t.getValue();
}
}
}
System.out.println("Maximum Song played is: " + song_name + " Played " + max_count + " times" );
return song_name;
}
public void print(){
for(Map.Entry <String, Map <String, Integer>> t :this.band_song_count.entrySet()){
String bandIs = t.getKey();
for (Map.Entry<String,Integer> e : t.getValue().entrySet())
System.out.println("OuterKey:" + bandIs + " InnerKey: " + e.getKey()+ " VALUE:" +e.getValue());
}
}
}
I would use hash within a hash, where
Outerhash will have Bandname as the key and its value will be another hash containing songname as the key and number of times this song has been played as the value.
{
Band1 => {
song1 => count of times song1 played
song2 => count of times song2 played
}
Band2 => {
song3 => count of times song1 played
song4 => count of times song2 played
}
}
void play(String bandname, String songname);
- Use HashMap with key = "bandname + songname" & value = "music file path"
String topSong(String bandname);
- Use HashMap with key = "bandname" & value = "top song name"
Very well, :-)
haha, No need to use a priority queue!
Sometimes we tend to miss the obvious. :-/
I don't get how this simple solution works. If you don't keep track of how many times a song is requested, how can you tell it is a top song? The solution seems to return the most recent one. In addition, the ways keys are constructed in play(...) and topSong(...) are different. They are supposed to be the same, right? Thanks!
The solution given by '@running' DOES NOT WORK RIGHT AWAY. My bad, I should have pointed out that earlier.
using the value field for the count in ("bandname + songname" & value = count) can help.
The Hash would have to store the count of the songs. But you can simply keep a top song field for each album. When you increase the count. just compare it with the top one(using info. from the other hash and then pulling the count from the prev. hash). then change the top song accordingly.
for playing: use the album+song as key to increase the count. Then use the top song hash to cross check the play count with the recently increased song count. And then make the necessary changes.
However, scalability could be an issue since you are replicating the 'album' string multiple times. Also, the song name is stored twice. Space complexity is O(no. of albums * avg.no. of songs per album) + O(all albums). For time, play() => ~O(1). this may not be a big improvement considering the small size of the number of songs.
This solution is useful for finding the top song. But won't work when you are asked for the top three songs or so... for that you would require to use a Heap or an store which runs insertion sort on it. (Correct me if I am wrong, insertion sort would work the best for small sized nearly sorted arrays).
we can create a max heap of songs where in the heap is arranged as per the count of the song.
- DashDash April 05, 2013Or
if we need only the song which is played max times then we can have a hash of songs where song can be the key and contains count as value. we also have a max variable which contains the max count of a song at that time. When we encounter a song we increase the count of the song by one and update the max if the count is more than max