We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

High Five

Number: 1074

Difficulty: Easy

Paid? Yes

Companies: Goldman Sachs, Amazon

Problem Description

Given a list of student scores where each element is in the form [ID, score], calculate each student's top five average. The top five average is obtained by summing the highest five scores of that student and using integer division by 5. The result should be returned as an array of pairs sorted by student ID in increasing order.

Key Insights

  • Use a hash table (or dictionary/Map) to group scores by student ID.
  • For each student, maintain a data structure (min-heap) to keep track of the top five scores efficiently.
  • If the heap size exceeds five and a new score is greater than the smallest score, replace it.
  • After processing, compute the average of the scores in the heap using integer division.
  • Finally, sort the results by student ID before returning.

Space and Time Complexity

Time Complexity: O(n log k) for iterating through all scores (with k fixed at 5, this is essentially O(n)), plus O(m log m) for sorting the m student IDs.
Space Complexity: O(n) for storing the scores grouped by student IDs.

Solution

The solution groups scores by student ID using a dictionary. For each student, a min-heap (or priority queue) is used to maintain the top five scores. As scores are processed, if a student's heap has fewer than 5 scores, the new score is simply added. Once the heap contains five scores, subsequent scores are compared with the current minimum; if a new score is greater, it replaces the smallest element in the heap. After processing all scores, the sum of each student's top five scores is divided by 5 (using integer division) to get the top five average. Finally, the results are sorted by student ID and returned.

Code Solutions

import heapq

def high_five(items):
    # Dictionary to map student IDs to a min-heap of their top five scores.
    student_scores = {}
    
    # Process each item in the list.
    for student_id, score in items:
        if student_id not in student_scores:
            student_scores[student_id] = []
        # Push the new score into the student's heap.
        heapq.heappush(student_scores[student_id], score)
        # If there are more than five scores, remove the smallest one.
        if len(student_scores[student_id]) > 5:
            heapq.heappop(student_scores[student_id])
    
    result = []
    # Calculate the average for each student.
    for student_id in student_scores:
        # Sum the top five scores.
        average = sum(student_scores[student_id]) // 5
        result.append([student_id, average])
    
    # Sort the result by student ID in increasing order.
    result.sort(key=lambda x: x[0])
    return result

# Example usage:
items = [[1,91],[1,92],[2,93],[2,97],[1,60],
         [2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
print(high_five(items))
← Back to All Questions