Amazon Interview Question SDETs
Team: 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, 2017template<typename T> class heap { heap(const heap&) = delete; heap& operator=(const heap&) = delete; public: heap() : m_heap(nullptr) , m_size(0) , m_last(-1) { m_size = reallocate(); } ~heap() { delete []m_heap; } size_t PARENT(size_t i) const { return i / 2; } size_t LEFT(size_t i) const { return i * 2 + 1; } size_t RIGHT(size_t i) const { return i * 2 + 2; } void insert(const T&value) { if (m_last == m_size - 1) { m_size = reallocate(); } m_last++; m_heap[m_last] = value; insertImpl(m_last); } void build_max_heap() { const size_t actual_size = m_last + 1; for (int i = actual_size / 2; i >= 0; i--) { max_heapify(i, actual_size); } } void max_heapify(size_t index, size_t len) { T &curr = m_heap[index]; size_t l = LEFT(index); size_t r = RIGHT(index); size_t largest = index; if ((l < len) && curr < m_heap[l]){ largest = l; } if (r < len && m_heap[largest] < m_heap[r]) { largest = r; } if (largest != index) { std::swap(curr, m_heap[largest]); max_heapify(largest, len); } } size_t size() const { return m_size; } size_t last() const { return m_last; } T* data() const { return m_heap; } protected: private: int reallocate() { int size = m_size; if (!m_heap) { size = (m_size == 0) ? 128 : m_size; m_heap = new T[size]; } else { const size_t new_size = m_size * 2; T *new_heap = new T[new_size]; memcpy(static_cast<void*>(new_heap), static_cast<void*>(m_heap), m_size * sizeof(T)); delete[] m_heap; m_heap = new_heap; size = new_size; } return size; } void insertImpl(size_t index) { while (index) { size_t parent = PARENT(index); if (m_heap[parent] < m_heap[index]) { std::swap(m_heap[parent], m_heap[index]); } index = parent; } } private: T *m_heap; size_t m_size; int m_last; }; class Chart { public: struct Record { std::string name; size_t rate; Record() : name() , rate(0) {} Record(const std::string &_name) : name(_name) , rate(1){} void incRate() { rate++; } bool operator < (const Record &other) { return rate < other.rate; } }; using TChart = std::map<std::string, heap<Record>*>; Chart() {} ~Chart() { for each (auto &item in m_chart){ delete item.second; } } void PlaySong(const std::string &author, const std::string &name) { TChart::const_iterator iter_find = m_chart.find(author); if (iter_find == m_chart.end()) { m_chart.insert(std::make_pair(author, new heap<Record>())); } bool bFind = false; Record *pdata = m_chart[author]->data(); int len = m_chart[author]->last(); for (int i = 0; i <= len; i++) { if (pdata[i].name == name) { pdata[i].incRate(); m_chart[author]->build_max_heap(); bFind = true; break; } } if (!bFind) { m_chart[author]->insert(Record(name)); } } std::string TopSong(const std::string &author) { std::string out; TChart::const_iterator iter_find = m_chart.find(author); if (iter_find != m_chart.end()) { if (m_chart[author]->last() >= 0) { out = m_chart[author]->data()[0].name; } } return out; } protected: private: TChart m_chart; }; //-------------------------------- TEST(HeapChart, Chart) { Chart chart; chart.PlaySong("Lady Gaga", "La-la-la"); chart.PlaySong("Lady Gaga", "Pokerface"); chart.PlaySong("Lady Gaga", "Pokerface"); chart.PlaySong("Sting", "Desert rose"); EXPECT_EQ(chart.TopSong("Lady Gaga"), std::string("Pokerface")); }