Top Five Average

PROBLEM STATEMENT

You are given a list ‘Records’ of size ‘N’, representing runs scored by different Cricket players in different matches, where Records[i] = [ID_i, Score_i] represent one score of the player with ‘ID_i’.

Your task is to find each player’s top 5 scores average. Return a list ‘topFiveAverages’ where topFiveAverages[j] = [ID_j, top_five_average_j] represents a player with ID_j and floor value of average of his 5 highest scores. The list ‘topFiveAverages’ should be sorted in increasing order of IDs.

Note:

1. It is guaranteed that for each player, there are at least 5 entries of his scores in the list ‘Records’.
2. You need to find the floor value of the top 5 scores average.
3. Different players have different IDs.

Example:

Consider a List ‘Records’ = [[1, 10], [1, 11], [2, 13], [2, 15], [1, 9], [2, 1], [1, 21], [2, 21], [2, 1], [1, 19], [1, 9], [2, 11], [1, 7]],  
Clearly, there are two players, with ID 1 and 2, respectively.
The top 5 scores of the player with ID 1 are 21, 19, 11, 10, 9, and the average of these scores is 14.
The top 5 scores of the player with ID 2 are 21, 15, 13, 11, 1, and the average of these scores is 12.
Thus, we should return a list ‘topFiveAverages’ = [[1, 14], [2, 12]]

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line of each test case consists of a single integer ‘N’, representing the size of the list ‘Records’.

Then next ‘N’ lines follow in each test case, and each of these ‘N’ lines consists of two space-separated integers, represent the ID and Score of the player.

Output format:

For each test case, in a separate line, print 2*K space-separated integers, where ‘K’ is the number of unique players in ‘Records’. The Id and top 5 average of the player having the ith smallest ID are given by (2*i + 1)th and (2*i + 2)th integer respectively.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10^4
1 <= ID <= 10^9
0 <= Score <= 10^5 

Time limit: 1 sec

Approach 1

Approach: We can sort the list ‘RECORDS’ in non-decreasing order of IDs, and in case IDs are equal we sort them in non-increasing order of scores. Now, if the first entry of a player is found at index ‘i’ in list ‘RECORDS’ then its top 5 scores are between index ‘i’ and ‘i+4' inclusive.

Algorithm:

Sort the list ‘RECORDS’ in non-decreasing order of IDs, and in case IDs are equal sort them in non-increasing order of scores.
Create a list ‘TOPFIVEAVERAGES’.
Run a loop where ‘i’ ranges from 0 to ‘N’ - 1 and in each step do the following.
- If ID of RECORDS[i] equals ‘COMPLETED’ then continue.
- Otherwise, let ‘AVERAGE’ := (RECORDS[i].SCORE + RECORDS[i+1].SCORE + … + RECORDS[i + 4].SCORE) / 5. And append [RECORDS[i].ID, AVERAGE] in list ‘TOPFIVEAVERAGES’.
Return ‘TOPFIVEAVERAGES’.

Try Problem

Approach 2

Approach: We can use a bucket data structure here, In which we use the Id of the player as indices, and stores a list of his scores in the corresponding bucket. We can implement buckets using HashMap, where the key is the Id of the player, and the value is the list of his scores.

Algorithm:

Create HashMap ‘BUCKETS’, where the key will be the Id of the player, and the value will be the list of his scores.
Run a loop where ‘i’ ranges from 0 to ‘N - 1’ and for each ‘i’ add ‘RECORDS[i].SCORE’ in ‘BUCKET[RECORDS[i].ID]’.
Sort all the buckets in non-increasing order.
Create a list ‘TOPFIVEAVERAGES’.
Iterate over all the buckets, and add the list of Id and the floor value of the average of the first 5 elements of that bucket in ‘TOPFIVEAVERAGES’.
Sort ‘TOPFIVEAVERAGES’ in ascending order of Ids and return it.

Try Problem