Amazon OA 2020 Amazon Music Pairs SOLUTIONS

Amazon Music Pairs

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.

 

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; 

}

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

close
error: Content is protected !!