Solution: High Five

Let’s solve the High Five problem using the Hash Maps pattern.

Statement

You are given a list of scores for multiple students, represented as items, where items[i]=[IDi,scorei]items[i] = [ID_i, score_i] indicates the ID of a student (IDi)(ID_i) and their score (scorei)(score_i). Your task is to compute the top five average scores for each student.

Return the result as an array of pairs, result, where result[j]=[IDj,topFiveAveragej]result[j] = [ID_j, topFiveAverage_j] represents the student with ID, IDjID_j, and their corresponding top five average scores. The result should be sorted in ascending order by IDjID_j.

Note: To calculate the top five averages for each student, sum their highest five scores and perform integer division by 55.

Constraints:

  • 1<=1 <= items.length <=1000<= 1000

  • items[i].length ==2== 2

  • 1<=IDi<=10001 <= ID_i <= 1000

  • 0<=scorei<=1000 <= score_i <= 100

  • For each IDiID_i, there will be at least five scores.

Solution

The idea is to use a hash map (dictionary) to store the scores for each student and then calculate the average of the top five scores for each student using sorting. The approach keeps track of the scores by using a dictionary where each key represents a student ID, and the corresponding value is a list of scores for that student. The solution sorts the scores for each student to find the top five, ensuring an accurate average calculation.

Now, let’s walk-through the steps of the solution:

  1. We create a dictionary, dict, to store scores for each student ID.

  2. We create a variable max_id, to keep track of the highest student ID encountered.

  3. We iterate through the items list, where each element is a pair [ID,score][ID, score] of a student, and for each pair:

    1. We append the scorescore corresponding to the ID in dict.

    2. We update max_id  to the maximum(current ID,maximum(current ID, max_id)). We do this to keep track of the highest student ID seen.

  4. After iterating through items and storing scores in dict, we initialize an empty list result to store the final output.

  5. Next, we iterate through all possible IDs from 1 to max_id (inclusive) and check whether there are scores in dict for each ID. If there are, we do the following:

    1. We find the top 55 scores for the current student.

    2. We calculate the average of the top 55 scores using integer division.

    3. We append the pair [ID,AverageScore][ID, AverageScore] to the result list.

  6. Finally, we return result, which contains each student's ID and their corresponding top five average scores.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.