Top K in Streaming | Dataford Interview Questions

How do you find the top K elements in streaming data, optimizing for time complexity better than a heap-based approach?

Asked in the Phone Screen stage. The interviewer was dissatisfied with the standard heap solution, prompting the candidate to suggest a bucket-based method for O(1) time complexity.

Task

Implement top_k_stream(stream, k, max_value). The stream contains integers from 0 through max_value. Return the largest k values in descending order, preserving duplicates. Use a bucket or direct-address counting strategy. The input guarantees 1 <= k <= len(stream).

Constraints

1 <= len(stream) <= 1000
1 <= k <= len(stream)
0 <= max_value <= 10000
0 <= stream[i] <= max_value

Function Signature

def top_k_stream(stream, k, max_value):

Your question is Top K in Streaming. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem