Answer static and streaming Top-K queries

Top-K in static and streaming settings (3 variants)

You are given integers and asked to answer Top-K queries under three different scenarios.

Variant 1: Static Top-K

Given an array A of n integers and an integer k, return the k most frequent values.

• Input: A (length n), k
• Output: list of k values (any order is acceptable unless you specify tie-breaking)
• Clarify tie-breaking for equal frequencies (e.g., smaller value first, or any order).

Variant 2: Real-time (unbounded) streaming Top-K

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.

Variant 3: Real-time Top-K within the last 1 hour (sliding window)

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]

Constraints to assume (unless you choose others)

• n up to 2e5 for the static problem.
• Streaming operations up to 2e5.
• Values may repeat heavily.

What to discuss

• Time/space complexity tradeoffs for each variant.
• How you maintain counts and retrieve Top-K efficiently, especially for the sliding window case.
• Edge cases: fewer than k distinct values, ties, many unique values, bursts of events.