High Five
Asked at Goldman Sachs
Problem
High Five gives you a list of [studentId, score] records and asks, for each student, for the integer average of their top five scores, returned in increasing order of student id. It is a grouping plus top-k question.
Asked At
| Company | Difficulty | |
|---|---|---|
| Goldman Sachs | Easy | View all Goldman Sachs questions → |
How to Think About It
Group scores by student id with a hash map (or a sorted map so the output is already in id order).
For each student you only need the five best scores. Keep a min-heap of size 5: push each score and pop whenever the heap grows past 5.
The average uses integer division: sum(top5) // 5.
Alternative: collect all scores per student, sort descending, take the first five. Simpler, slightly slower — fine at this input size.
Every student is guaranteed to have at least five scores.
Optimal Approach
Step 1: scores = {} mapping id to a min-heap.
Step 2: For each (id, s): push s onto scores[id]; if its size exceeds 5, pop the smallest.
Step 3: For each id in sorted order, output [id, sum(heap) // 5].
Time: O(n log 5 + u log u) where u is the number of students. Space: O(u).
What Trips People Up in Real Interviews
Averaging all scores instead of the top five.
Using floating-point division — the expected result is an integer average.
Forgetting to sort the output by student id.
Using a max-heap of all scores when a size-5 min-heap is enough.
Solution Code
import heapq
def highFive(items):
scores = {}
for sid, s in items:
h = scores.setdefault(sid, [])
heapq.heappush(h, s)
if len(h) > 5:
heapq.heappop(h)
return [[sid, sum(scores[sid]) // 5] for sid in sorted(scores)]Frequently Asked Questions
What is the High Five problem?
High Five gives you a list of `[studentId, score]` records and asks, for each student, for the integer average of their top five scores, returned in increasing order of student id. It is a grouping plus top-k question.
How do you solve High Five?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask High Five?
High Five is asked at Goldman Sachs. It is a easy difficulty problem.
What are common mistakes on High Five?
- Averaging all scores instead of the top five.
- Using floating-point division — the expected result is an integer average.
- Forgetting to sort the output by student id.
- Using a max-heap of all scores when a size-5 min-heap is enough.