call(back)
Algorithms & Data StructuresmediumSign in to star problems

Recent Event Window Queries

Events arrive with non-decreasing integer timestamps, and only the most recent m additions are retained — an add beyond that evicts the oldest. Process operations in order:

["add", timestamp, key]       store the event; result null
["unique_before", t]          how many distinct retained keys have timestamp <= t
["top_before", t]             the most frequent retained key with timestamp <= t,
                              smallest key on a tie; null when none qualifies

Return the result of every operation, in order.

eventWindow(3, [
  ["add", 1, "a"], ["add", 2, "b"], ["add", 3, "a"],
  ["unique_before", 2], ["top_before", 3],
  ["add", 4, "c"], ["unique_before", 4],
])
  ->  [null, null, null, 2, "a", null, 3]

Adding c evicts the first a, so the last count sees b, a, c. m is at most 5,000.

Hints

Hint 1

The retained events are a queue: push on add, drop from the front when it holds more than m.

Hint 2

Timestamps never decrease, so the events with timestamp <= t are a prefix of the queue — stop scanning at the first one that is too late.

Asked at