You are given integers and asked to answer Top-K queries under three different scenarios.
Given an array A of n integers and an integer k, return the k most frequent values.
A
(length
n
),
k
k
values (any order is acceptable unless you specify tie-breaking)
You receive a stream of integers supporting operations:
add(x)
: add one occurrence of value
x
topk()
: return the current
k
most frequent values
Design an efficient data structure and implement these operations.
Events arrive as (timestamp, value) where timestamp is in seconds (monotonic non-decreasing). Support:
add(t, x)
: record event
x
at time
t
topk(t)
: return the
k
most frequent values considering only events with timestamps in
[t-3600, t]
n
up to 2e5 for the static problem.
k
distinct values, ties, many unique values, bursts of events.