Top-K in Static and Streaming Settings

You are tasked with designing and implementing solutions to answer Top-K queries under three distinct scenarios involving streams of integers.

Variant 1: Static Top-K

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

• Input: An array A of length n and an integer k.
• Output: A list of k values. Any order is acceptable unless specific tie-breaking rules are defined.
• Clarification: The candidate should clarify tie-breaking rules for values with equal frequencies (e.g., smaller value first, or any order).

Variant 2: Real-time (Unbounded) Streaming Top-K

Design and implement an efficient data structure to handle an unbounded stream of integers, supporting the following operations:

• add(x): Adds one occurrence of value x to the stream.
• topk(): Returns the current k most frequent values in the stream.

Variant 3: Real-time Top-K within a Sliding Window

Events arrive as (timestamp, value), where timestamp is in seconds and is monotonically non-decreasing. Support the following operations:

• add(t, x): Records an event x at time t.
• topk(t): Returns the k most frequent values, considering only events with timestamps within the last 1 hour, specifically in the range [t-3600, t].

Constraints and Assumptions

• For the static problem, n can be up to 2e5.
• For streaming operations, the total number of operations can be up to 2e5.
• Values may repeat heavily.

Discussion Points

Candidates should be prepared to discuss:

• Time and space complexity tradeoffs for each variant.
• Strategies for maintaining counts and efficiently retrieving Top-K elements, especially for the sliding window case.
• Edge cases such as:
  • Fewer than k distinct values present.
  • Handling ties in frequency.
  • Scenarios with many unique values.
  • Impact of bursts of events.