Skip to main content
Talentd

Design Exam Scores Tracker - Solution & Explanation

MediumArrayBinary SearchDesignPrefix Sum9 min readAsked at: Meesho
Practice this problem

Problem Statement

Alice frequently takes exams and wants to track her scores and calculate the total scores over specific time periods.

Implement the ExamTracker class:

  • ExamTracker(): Initializes the ExamTracker object.
  • void record(int time, int score): Alice takes a new exam at time time and achieves the score score.
  • long long totalScore(int startTime, int endTime): Returns an integer that represents the total score of all exams taken by Alice between startTime and endTime (inclusive). If there are no recorded exams taken by Alice within the specified time interval, return 0.

It is guaranteed that the function calls are made in chronological order. That is,

  • Calls to record() will be made with strictly increasing time.
  • Alice will never ask for total scores that require information from the future. That is, if the latest record() is called with time = t, then totalScore() will always be called with startTime <= endTime <= t.

 

Example 1:

Input:
["ExamTracker", "record", "totalScore", "record", "totalScore", "totalScore", "totalScore", "totalScore"]
[[], [1, 98], [1, 1], [5, 99], [1, 3], [1, 5], [3, 4], [2, 5]]

Output:
[null, null, 98, null, 98, 197, 0, 99]

Explanation

ExamTracker examTracker = new ExamTracker();
examTracker.record(1, 98); // Alice takes a new exam at time 1, scoring 98.
examTracker.totalScore(1, 1); // Between time 1 and time 1, Alice took 1 exam at time 1, scoring 98. The total score is 98.
examTracker.record(5, 99); // Alice takes a new exam at time 5, scoring 99.
examTracker.totalScore(1, 3); // Between time 1 and time 3, Alice took 1 exam at time 1, scoring 98. The total score is 98.
examTracker.totalScore(1, 5); // Between time 1 and time 5, Alice took 2 exams at time 1 and 5, scoring 98 and 99. The total score is 98 + 99 = 197.
examTracker.totalScore(3, 4); // Alice did not take any exam between time 3 and time 4. Therefore, the answer is 0.
examTracker.totalScore(2, 5); // Between time 2 and time 5, Alice took 1 exam at time 5, scoring 99. The total score is 99.

 

Constraints:

  • 1 <= time <= 109
  • 1 <= score <= 109
  • 1 <= startTime <= endTime <= t, where t is the value of time from the most recent call of record().
  • Calls of record() will be made with strictly increasing time.
  • After ExamTracker(), the first function call will always be record().
  • At most 105 calls will be made in total to record() and totalScore().

Approach Overview

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.

Solution

We use an array times to store the time points of each exam, and another array pre to store the prefix sums, where pre[i] represents the total score of the first i exams. For each call to \texttt{record}(time, score), we add time to times and add the last element of pre plus score to pre.

For each call to \texttt{totalScore}(startTime, endTime), we use binary search to find the first position l in times that is greater than or equal to startTime and the first position r that is greater than endTime, then return pre[r-1] - pre[l-1].

The time complexity is O(log n), where n is the number of exams. The space complexity is O(n).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Range ScanO(n) per queryO(1)Small datasets or when queries are rare
Sorted Array + Prefix SumO(n log n) preprocessing, O(log n) queryO(n)When scores are static and many range queries are expected
Prefix Sum + Binary SearchO(log n) per queryO(n)Best for frequent queries requiring fast range aggregation

Video Solution

Leetcode Biweekly Contest 167 Editorials | Maximum Partition Factor | Design Exam Scores Tracker • Abhinav Awasthi • 1,505 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Design Exam Scores Tracker easy or hard?
Design Exam Scores Tracker is typically rated Medium difficulty. The logic becomes straightforward once you recognize the pattern of combining binary search with prefix sums to handle repeated range queries efficiently.
Design Exam Scores Tracker Python/Java solution
Implement the algorithm by sorting the scores and building a prefix sum list. Use binary search utilities such as bisect in Python or Arrays.binarySearch in Java to locate range boundaries, then subtract prefix values to compute the result in O(log n) time.
How to solve Design Exam Scores Tracker in O(log n)?
Maintain a sorted list of scores and build a prefix sum array. For each query, run two binary searches to locate the start and end indices of the score range. Subtract prefix sums at those indices to compute the total or count instantly, giving an overall O(log n) query time.
What is the best approach for Design Exam Scores Tracker?
The Prefix Sum + Binary Search approach is the most efficient. Scores are stored in sorted order, and a prefix sum array allows constant-time range aggregation. Binary search finds the boundaries of the requested score range in O(log n) time, making each query fast even for large datasets.
Is Design Exam Scores Tracker asked at Google/Amazon/Meta?
Problems combining range queries, prefix sums, and binary search appear frequently in interviews at companies like Google, Amazon, and Meta. Variants involving score tracking, analytics dashboards, or leaderboard queries test similar design and algorithmic skills.
What data structure is used in Design Exam Scores Tracker?
The core data structures are a sorted array and a prefix sum array. Binary search operates on the sorted array to find boundaries, while prefix sums provide constant-time computation of range totals or aggregates.
What is the time complexity of Design Exam Scores Tracker?
The optimized solution runs queries in O(log n) time using binary search to locate range boundaries. Prefix sums allow the final aggregation to be computed in O(1). Space complexity is O(n) because the algorithm stores both the sorted scores and the prefix sum array.

Ready to solve this problem?

Practice Design Exam Scores Tracker with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays