Amazon Interview Question
SDETsTeam: Advertisement
Country: United States
Interview Type: Phone Interview
Many questions to ask the interviewer on this.
1. How many bandnames are expected to be stored? Is there some upper limit? (e.g. it HAS to be < 7.5 billion since that's more than the population of the Earth :)
2. How many songs can a band create? Again, it has to be a small/limited amount.
3. What is the expected response time of the server?
4. How frequently will both API's be called? Will the API for play() be called much much more often than topSong(), or vice-versa?
5. Is any other metadata provided with the play() request other than in the API? e.g. header information?
Based on these questions, we can design a service for your problem. One implementation is using a hash map with key = band name, value = TreeMap{ key = song name, value = count}. This would cost O(log(n)) for insertions, and O(1) for look-ups, as well as O(n) in space (since we're storing all information).
A HashMap of MaxHeaps.
Map<String, MaxHeap> map;
where, key = artist name, MaxHeap.getRoot() will give you the song name.
The nodes will be made up of a simple datastructure with a key-value pair:
class SongNode{
int count;
String songName;
public String getRootName(){
return songName()
}
...
...
Somewhat on these lines it could be answered. Feedback appreciated. Thank you.
Instead of a TreeMap - that would cost log(s) for each insertion, why not just have
SongBook {
Map<String, Count> topSong;
Map<String, Count> allSongs;
}
Map<String, SongBook> bands;
Each insertion would lookup the songBook by using bandName in O(1).
In the songBook, increment the currentCount of the song. If it becomes more than the topSong, replace the entry in the topSong map.
The topSong - is always maintained separately - so a lookup of the entry in the Map would give you the value of the topSong in constant time.
Maintain three HashMaps
First map-
Key-Song Value-Singer
SecondMap-
Key-Song Value-count
ThirdMap-
Key-Singer Value-Top Song
When a new request to play a song comes. Increment the count of current song. Check the singer of the current song and also check the top song of that singer. If the curr song and top song are not same, check if the count of curr song is greater than top song. If so, update the top song of singer
Here is my solution in perl
package Song;
use Moose;
has 'playedCount' => (is => 'rw', default => 0);
has 'title' => (is => 'ro', required => 1);
sub play {
my ($self) = @_;
$self->playedCount($self->playedCount + 1);
}
1;
package Singer;
use Song;
use Moose;
has 'name' => ( is => 'ro', required => 1 );
has 'topSongObj' => (is => 'rw', predicate => '_isSet_topSongObj');
has 'songs' => (is => 'rw', isa => 'ArrayRef', default => sub { [] },);
sub play {
my ($self, $song) = @_;
my $found = 0;
foreach my $songObj ( @{$self->songs} ){
if ($songObj->title eq $song) {
$found = 1;
$songObj->play();
if ($songObj->playedCount > $self->topSongObj->playedCount) {
$self->topSongObj($songObj);
}
}
}
if (! $found) {
my $s = Song->new(title => $song);
$s->play();
if (! $self->_isSet_topSongObj) {
$self->topSongObj($s);
}
push(@{$self->songs}, $s);
}
}
sub topSong {
my ($self) = @_;
return $self->topSongObj->title;
}
1;
use Singer;
my %singers;
sub play {
my ($singer, $song) = @_;
if (! exists $singers{$singer}) {
my $s = Singer->new(name => $singer);
$singers{$singer} = $s;
$s->play($song);
} else {
my $s = $singers{$singer};
$s->play($song);
}
}
sub topSong {
my ($singer) = @_;
if (! exists $singers{$singer}) {
die "Singer hasnt sing any song yet";
}
return $singers{$singer}->topSong;
}
play('singerA' , 'song1');
play('singerA' , 'song2');
play('singerA' , 'song3');
play('singerA' , 'song1');
play('singerA' , 'song2');
play('singerA' , 'song2');
print topSong('singerA') . "\n";
Here is my code in perl
package Song;
use Moose;
has 'playedCount' => (is => 'rw', default => 0);
has 'title' => (is => 'ro', required => 1);
sub play {
my ($self) = @_;
$self->playedCount($self->playedCount + 1);
}
1;
package Singer;
use Song;
use Moose;
has 'name' => ( is => 'ro', required => 1 );
has 'topSongObj' => (is => 'rw', predicate => '_isSet_topSongObj');
has 'songs' => (is => 'rw', isa => 'ArrayRef', default => sub { [] },);
sub play {
my ($self, $song) = @_;
my $found = 0;
foreach my $songObj ( @{$self->songs} ){
if ($songObj->title eq $song) {
$found = 1;
$songObj->play();
if ($songObj->playedCount > $self->topSongObj->playedCount) {
$self->topSongObj($songObj);
}
}
}
if (! $found) {
my $s = Song->new(title => $song);
$s->play();
if (! $self->_isSet_topSongObj) {
$self->topSongObj($s);
}
push(@{$self->songs}, $s);
}
}
sub topSong {
my ($self) = @_;
return $self->topSongObj->title;
}
1;
use Singer;
my %singers;
sub play {
my ($singer, $song) = @_;
if (! exists $singers{$singer}) {
my $s = Singer->new(name => $singer);
$singers{$singer} = $s;
$s->play($song);
} else {
my $s = $singers{$singer};
$s->play($song);
}
}
sub topSong {
my ($singer) = @_;
if (! exists $singers{$singer}) {
die "Singer hasnt sing any song yet";
}
return $singers{$singer}->topSong;
}
play('singerA' , 'song1');
play('singerA' , 'song2');
play('singerA' , 'song3');
play('singerA' , 'song1');
play('singerA' , 'song2');
play('singerA' , 'song2');
print topSong('singerA') . "\n";
One possible solution of this chart problem is to use map with a key of band name and
max-heap for records. Localize of max rate song in max-heap is O(1).
Increase song's rate may cause rearrange max-heap calling max_heapify
- yura.gunko March 05, 2017