Amazon OA 2020 Amazon Music Pairs SOLUTIONS

Music Pairs Solution Amazon OA

Amazon Music is working on a new “community radio station” feature which will allow users to iteratively populate the playlist with their desired songs. Considering this radio station will also have other scheduled shows to be aired, and to make sure the community soundtrack will not run over other scheduled shows, the user-submitted songs will be organized in full-minute blocks. Users can choose any songs they want to add to the community list, but only in pairs of songs with durations that add up to a multiple of 60 seconds (e.g. 60, 120, 180).

As an attempt to insist on the highest standards and avoid this additional burden on users, Amazon will let them submit any number of songs they want, with any duration, and will handle this 60-second matching internally. Once the user submits their list, given a list of song durations, calculate the total number of distinct song pairs that can be chosen by Amazon Music.

See Also : Amazon Online Assessment Questions 2021 Preparation

Solution:

The pair is disguised by their indexes. So if they have the same value but on different positions, then we still consider them different.

For example, [60, 60, 60], there will be 3 pairs which are (0, 1), (0, 2), and (1, 2) in indexes.

So the naïve solution is O(N^2), we just use a two-layer for loop, for each pair, check their sum can be divided by 60. But this is not the interviewer want.

A better way can reach O(N).

We  just need to get the remainders of each element, for example, [60, 60, 60] will becomes [0, 0, 0]. Then we know there are 3 elements that can be divided by 60. So we just need to pick 2 of them to form a pair, so there will be n*(n-1)/2 pairs.

In other cases, if we have x with count of a and (60 – x) with count of b, then we can form a*b pairs.

So in summary:

1): get the remainders of each elements;

2): count the number of each remainders;

3): analyze the counts to find the valid pair

The time complexity is O(N), and space complexity is O(N).

See the code below:

int findPair(vector<int>& nums) {

int res = 0;

vector<int> cts(60, 0);

for(auto &a : nums) ++cts[a%60];

for(int i=1; i<30; ++i) res += cts[i]*cts[60-i];

res += cts[0]*(cts[0]-1)/2 + cts[30]*(cts[30]-1)/2;

return res; 

}

Amazon Online Assessment Test Questions:

September Long Challenge 2021 Solution