Katkat
Back

Implement a Timestamped Counter

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to design a data structure that handles time-series data and performs efficient range-based queries using binary search.

Problem Statement

Design a TimestampedCounter class that tracks events occurring at specific integer timestamps. You need to support adding events and querying the total number of events that occurred within a given inclusive time window [start_time, end_time].

Requirements

Implement the following methods:

  • void add_event(int timestamp): Records an event at the given timestamp.
  • int get_count(int start_time, int end_time): Returns the number of events that occurred between start_time and end_time inclusive.

Constraints

  • add_event will be called with non-decreasing timestamps.
  • Total number of events can reach 10^6.
  • Queries should be performed in sub-linear time relative to the number of events.

Examples

counter = TimestampedCounter()
counter.add_event(1)
counter.add_event(2)
counter.add_event(5)
counter.add_event(5)

print(counter.get_count(1, 3)) # Output: 2 (Events at 1, 2)
print(counter.get_count(5, 5)) # Output: 2 (Two events at 5)
print(counter.get_count(6, 10)) # Output: 0

Edge Cases

  • Queries with start_time > end_time.
  • Queries where no events exist in the requested range.
  • Multiple events occurring at the exact same timestamp.

Hints

Hint 1

Since timestamps are added in non-decreasing order, you can maintain a simple list of timestamps and use binary search to locate ranges.

Hint 2

For `get_count`, use binary search twice: once to find the index of the first occurrence >= `start_time` and once to find the index of the last occurrence <= `end_time`.

Hint 3

If multiple events occur at the same timestamp, ensure your binary search logic accounts for the leftmost and rightmost indices of that value.

Follow-up questions

  • How would your implementation change if timestamps were added in random order rather than non-decreasing order?
  • How would you optimize `get_count` if the number of events is extremely large, but the number of unique timestamps is relatively small?
  • What are the space and time complexities of your current implementation for both `add_event` and `get_count`?