Page Contents

*Amazon* *Music Pairs Solution Amazon OA*

*Amazon*

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

Also See: Amazon OA Online Assessment 2021 Questions and Answers

*Solution:*

*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; }

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

*Amazon Online Assessment Test Questions:*

*Robot Bounded in Box**Number Game**Find All Combination of Numbers Sum to Target / Shopping Options**Fill the Truck**Music Pairs**Slowest key**Five Star Seller**Split String Into Unique Primes**Storage Optimization**Minimum Difficulty of a Job Schedule**Autoscale Policy, Utilization Check**Optimal Utilization**Merge Two Sorted Lists**Two Sum Unique Pairs**Shopping Patterns**Reorder Data in Log Files**Top K Frequent Words**Trees Height*