Goldman Sachs
Online AssessmentQ1
Easy-Medium50 MarksHigh Five (Average of Top Five Scores)
ArraysHash TableHeap (Priority Queue)
Set 1 • 90 min
Problem Statement
Given a list of test scores of different students, where items[i] = [IDi, scorei] represents one score of a student with IDi.
Calculate each student's top five average score (the average of their 5 highest scores using integer division).
Return the answer as an array of pairs [[ID1, topFiveAverage1], [ID2, topFiveAverage2], ...] sorted by student ID in increasing order.
Candidate Instructions
- ▸Use a Min-Heap of size 5 per student, or sort each student's scores descending.
- ▸Output sorted by student ID.
Input Format
- ▸First line: integer N (number of score entries).
- ▸Next N lines: two space-separated integers IDi and scorei.
Output Format
- ▸Print each student ID and average score on a new line.
Constraints
- 1 <= items.length <= 1000
- items[i].length == 2
- 1 <= IDi <= 1000
- 0 <= scorei <= 100
- Each student has at least 5 scores.
Edge Cases
- ▸Student has more than 5 scores (only top 5 count)
- ▸Scores with identical values
Sample Test Cases
Example 1
Input
6 1 91 1 92 2 93 2 97 1 60 1 65 1 87 1 100 2 77 2 65 2 87
Output
1 87 2 83
Explanation
Student 1 top 5 scores: 100, 92, 91, 87, 65. Average = 435 / 5 = 87.
Student 2 top 5 scores: 97, 93, 87, 77, 65. Average = 419 / 5 = 83.
Complexity
TimeO(N log 5) = O(N)
SpaceO(N)
Expected Approach
Group scores by student ID into a TreeMap. Maintain a Min-Heap of size 5 for each student. When heap exceeds 5, pop the smallest. Compute the sum and integer average of the 5 scores.