Amazon Interview Question


Country: India
Interview Type: Phone Interview




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

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.

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

- smallchallenges March 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Asif Garhi March 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- alopatindev March 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can use a double ended queue (deque), initially the pointer is at the first song, as soon as the song is finished playing, we can pop it and push it at the end of the queue.

- ak795 March 23, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

vector<Song> myplaylist;
int songToPlay = myplatlist.size() - 1;

while (songToPlay > 0)
{
	int selectedSong = randomNumber(0, songToPlay);
	swap(selectedSong, songToPlay);
	PlaySong(myplaylist, songToPlay);
	--songToPlay;
}

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

vector<Song> myplaylist;
int songToPlay = myplatlist.size() - 1;

while (songToPlay > 0)
{
	int selectedSong = randomNumber(0, songToPlay);
	swap(selectedSong, songToPlay);
	PlaySong(myplaylist, songToPlay);
	--songToPlay;
}

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

/**
 * 
 */
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.");
        }
    }

}

- Divyanshu Shekhar March 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Rahul Lakhmara April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. HashMap can serve the purpose here as the song name will be termed as key and the media file will be the value.
As in Iteration HashMap will give the songs in random order and that too a single time.
So this can meet our requirment.

- meamitagarwal20 May 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Create a Array(0-n)
2. Play in rundom number(0-n) and swap to last
3. Play in rundom number (0-n-1) and swap to last

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

- Divyanshu Shekhar What is the swap code doing? String temp = indices.get(nextSong);
indices.set(nextSong, indices.get(i));
indices.set(i, temp)

- test March 04, 2019 | 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