Query Unique and Most-Frequent Keys in a Recent Event Window

Problem Statement

Design an in-memory data structure that processes a continuous, timestamp-ordered stream of events. The system must retain only the most recent m events, automatically discarding older events once capacity is exceeded.

Implement the EventTracker class:

• EventTracker(m: int): Initializes the tracker to retain at most m events.
• record_event(timestamp: int, key: str) -> None: Records an event with the given timestamp and key. Timestamps are guaranteed to arrive in non-decreasing order. If the tracker already holds m events, the oldest event is evicted.
• query(min_timestamp: int) -> tuple[int, str]: Computes metrics across all currently retained events with timestamp >= min_timestamp. Returns a tuple (distinct_count, top_key) where:
  • distinct_count is the number of unique keys among the qualifying events.
  • top_key is the key with the highest frequency in the qualifying events. In case of a tie in frequency, return the lexicographically smallest key.
  • If no retained events qualify, return (0, "").

Interface

class EventTracker:
    def __init__(self, m: int):
        pass

    def record_event(self, timestamp: int, key: str) -> None:
        pass

    def query(self, min_timestamp: int) -> tuple[int, str]:
        pass

Examples

Example 1

tracker = EventTracker(3)
tracker.record_event(10, "apple")
tracker.record_event(20, "banana")
tracker.record_event(30, "apple")

# Retained: [(10, "apple"), (20, "banana"), (30, "apple")]
assert tracker.query(15) == (2, "apple")
# Qualifying events: (20, "banana") and (30, "apple")
# Unique keys: 2 ("apple", "banana")
# Both occur once; "apple" is lexicographically smaller.

tracker.record_event(40, "cherry")
# (10, "apple") is evicted. Retained: [(20, "banana"), (30, "apple"), (40, "cherry")]

assert tracker.query(10) == (3, "apple")
# Qualifying events: (20, "banana"), (30, "apple"), (40, "cherry")
# All occur once; "apple" is lexicographically smallest.

assert tracker.query(50) == (0, "")
# No events have timestamp >= 50.

Constraints

• 1 <= m <= 10^5
• 1 <= timestamp <= 10^9, non-decreasing across calls to record_event
• key consists of 1 to 32 lowercase English letters.
• The total number of calls to record_event is at most 2 * 10^5.
• The total number of calls to query is at most 2,000.

Edge Cases

• query timestamp greater than all retained timestamps.
• query timestamp smaller than all retained timestamps (all retained events qualify).
• Multiple keys having the same frequency (must correctly resolve lexicographical order).
• Multiple events with identical timestamps.