Top-K Retrieval From Stream | Dataford Interview Questions

Match Group services may process a large stream of candidate profiles or recommendations scored by a ranking system. Implement a function that returns the top k items without storing or sorting the entire stream.

The input stream is finite but may be provided as any iterable, including a generator. Each element is a two-item sequence [item_id, score], where item_id is a string and score is an integer. Return up to k elements as [item_id, score] pairs, ordered by descending score. If two items have the same score, the item encountered later in the stream ranks higher.

Your algorithm must process each stream element once and use memory proportional to k, excluding the returned result. Do not mutate the input items.

Constraints

0 <= k <= 10^5
The stream contains at most 10^7 elements
Each element is a two-item sequence [item_id, score]
item_id is a unique non-empty string
Scores are integers in [-10^9, 10^9]

Function Signature

def top_k_items(stream, k):

Your question is Top-K Retrieval From Stream. 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

Your algorithm must process each stream element once and use memory proportional to k, excluding the returned result. Do not mutate the input items.

Constraints

0 <= k <= 10^5
The stream contains at most 10^7 elements
Each element is a two-item sequence [item_id, score]
item_id is a unique non-empty string
Scores are integers in [-10^9, 10^9]

Function Signature

def top_k_items(stream, k):

Your question is Top-K Retrieval From Stream. 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.