Implement a Timestamped Counter
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a data structure that records calls to an `increment` method.
Requirements:
- Each call to `increment(timestamp)` receives an integer `timestamp`.
- Timestamps are strictly increasing across calls.
- Implement `query(t)` to return how many times `increment` was called with a timestamp greater than `t`.
Example:
- Calls: `increment(1)`, `increment(3)`, `increment(3)`, `increment(10)`
- `query(3)` should return `1` if `query` means strictly after `3`, or `1` plus any later duplicates depending on the exact interpretation. Make your API behavior explicit.
Follow-up discussion:
1. How would you support a very high call rate, where `increment` may be invoked many times per second?
2. How would you optimize query performance further?
3. If the requirements were extended to support counting calls in any time interval `[start, end]`, what data structures would you consider?
Quick Answer: This question evaluates the ability to design and implement time-indexed counting data structures, reason about strictly increasing timestamps and query semantics, and consider performance and scalability trade-offs.
Record increment timestamps and answer counts strictly after t, plus optional inclusive range counts.
Constraints
- Increment timestamps are non-decreasing
Examples
Input: ((('increment', 1), ('increment', 3), ('increment', 3), ('increment', 10), ('query', 3)),)
Expected Output: [1]
Explanation: Strictly greater than 3 returns one.
Input: ((('query', 5),),)
Expected Output: [0]
Explanation: No increments yet.
Input: ((('increment', 1), ('increment', 2), ('increment', 5), ('range', 2, 5)),)
Expected Output: [2]
Explanation: Inclusive range count.
Hints
- Store timestamps in sorted order and binary-search query boundaries.