Design Exam Scores Tracker

Design Exam Scores Tracker

1. What is this problem about?

The Design Exam Scores Tracker interview question asks you to build a system that manages student IDs and their exam scores. You need to support updating a student's score and calculating the rank of a specific score among all scores recorded so far. This Design Exam Scores Tracker coding problem is about maintaining a dynamically updated sorted collection of values.

2. Why is this asked in interviews?

Meesho uses this to test your ability to use Binary Search interview patterns and efficient sorting. It evaluates how you handle frequent updates to values that affect global rankings. It's a test of whether you can optimize a search from $O(N)$ to $O(\log N)$ using sorted structures or specialized data representations.

3. Algorithmic pattern used

This problem follows the Hash Map + Frequency Tracking pattern.

• Map<StudentID, Score>: To keep track of each student's current score.
• Score Storage:
  • Option 1: A sorted list of all scores. Updates take $O(N)$, queries $O(\log N)$.
  • Option 2: A Binary Indexed Tree (BIT) or Segment Tree over the range of possible scores (if the score range is small, e.g., 0-100).
  • Option 3: A Balanced BST or Skip List where nodes store subtree sizes.

4. Example explanation

1. update(std1, 80), update(std2, 90), update(std3, 85).
2. Scores: [80, 85, 90].
3. getRank(85): There is 1 score higher than 85. Rank is 2.
4. update(std1, 95): Scores list becomes [85, 90, 95].
5. getRank(85): Now there are 2 scores higher than 85. Rank is 3.

5. Common mistakes candidates make

• Linear Ranking: Counting every score higher than the target one-by-one ($O(N)$), which is too slow for large datasets.
• Stale Data: Failing to remove the old score from the sorted structure when a student's score is updated.
• Handling Duplicates: Not correctly accounting for multiple students having the same score when calculating ranks.

6. Interview preparation tip

If the range of values (scores) is small, Binary Indexed Trees are incredibly efficient. If the range is large, look into Ordered Sets that support "Order Statistic" operations (finding the index of an element in sorted order).