Answer static and streaming Top-K queries

Q: Answer static and streaming Top-K queries

This question evaluates understanding of frequency counting, top-K selection, streaming and sliding-window algorithms and data-structure design in the Coding & Algorithms domain, testing both conceptual algorithmic reasoning and practical implementation skills.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at CloudKitchens.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at CloudKitchens during technical interviews.

Question

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.