Top Five Average

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
Goldman Sachs

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]]
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
5
7 0
7 0
7 0
7 0
7 0
13
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
Sample Output 1:
7 0
1 14 2 12
Explanation For Sample Input 1:
Test case 1:
There is only one player having ID 7, and his all 5 scores are 0,  Thus top 5 scores average of this player will also be 0, so the list ‘topFiveAverages’ should be [[7, 0]] 

Test case 2:
See the problem statement for an explanation.
Sample Input 2:
1
5
1 1
1 2
1 3
1 4
1 5
Sample Output 2:
1 3
Explanation For Sample Input 2:
Test case 1:
There is only one player having ID 1, and his all 5 scores are 1, 2, 3, 4 and 5.  Thus top 5 scores average of this player will be 3, so the list ‘topFiveAverages’ should be [[1, 3]]
Hint

Is Sorting the list Records helpful and can make it iterative solution?

Approaches (2)
Sorting

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:

  1. Sort the list ‘RECORDS’ in non-decreasing order of IDs, and in case IDs are equal sort them in non-increasing order of scores.
  2. Create a list ‘TOPFIVEAVERAGES’.
  3. 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’.
  4. Return ‘TOPFIVEAVERAGES’.
Time Complexity

O(N * log(N)),  where ‘N’ is the size of the list ‘RECORDS’. 

 

We can sort Records in O(N*log(N)) times using merge-sort or heap-sort algorithm. And iterating over ‘RECORDS’ will take O(N) times. Thus overall time complexity will be O(N*log(N)) + O(N) = O(N*log(N).

Space Complexity

O(N),  where ‘N’ is the size of the list ‘RECORDS’.

 

The list  ‘TOPFIVEAVERAGES’ can have the size of the order O(N). Thus overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Top Five Average
Full screen
Console