Design Exam Scores Tracker - Solution & Explanation

Problem Overview: You need to design a system that tracks exam scores and efficiently answers queries about score ranges or aggregated statistics. The challenge is supporting repeated queries without scanning the entire dataset every time.

Approach 1: Brute Force Range Scan (Time: O(n) per query, Space: O(1))

The most direct approach stores all scores in an array. For every query, iterate through the entire array and compute the required statistic such as total scores, counts, or averages within a given range. This works because the array already contains all information needed to answer the query. However, each query requires scanning the full list, which becomes expensive when the number of scores or queries grows large. This approach is useful for understanding the problem but does not scale well.

Approach 2: Sorted Array + Prefix Sum (Time: O(n log n) preprocessing, O(log n + 1) query, Space: O(n))

Instead of repeatedly scanning the array, first sort the scores. Then build a prefix sum array where prefix[i] stores the cumulative total up to index i. Sorting allows efficient boundary discovery using binary search. For a query range, locate the left and right indices with binary search and subtract prefix values to compute the result instantly. This eliminates repeated linear scans and reduces query cost dramatically.

Approach 3: Prefix Sum + Binary Search (Time: O(log n) per query, Space: O(n))

The optimal design maintains scores in a sorted structure and precomputes prefix sums. When a query arrives, perform two binary searches to find the first index >= lower bound and the last index <= upper bound. With those indices, compute the aggregated score using a simple prefix subtraction. Binary search ensures logarithmic lookup time, while prefix sums provide constant-time range aggregation. This approach leverages properties of a sorted array and is the standard technique for repeated range queries.

Recommended for interviews: Start by explaining the brute force scan to demonstrate understanding of the requirement. Then move to the Prefix Sum + Binary Search approach. Interviewers expect this optimization because it reduces query cost from O(n) to O(log n) while keeping the implementation simple and predictable.