Top-K Popular Items With Hash and Heap | Dataford Interview Questions

CloudKitchens needs to identify the most popular menu items from a massive stream of order events. Given item IDs and an integer k, return the k items with the highest frequencies using a hash map and a heap.

Return items ordered by decreasing frequency. If two items have the same frequency, return the smaller item ID first.

Formal Specification

Implement top_k_items(item_ids, k), where item_ids is an iterable of non-negative integers representing ordered menu items and k is the requested number of results. Return a list of at most k item IDs. If fewer than k distinct items occur, return all distinct items.

The solution should count frequencies with a hash map and maintain a min-heap containing only the current top k items. The input may contain billions of events, so avoid sorting every event or storing unnecessary per-event data.

Constraints

0 <= len(item_ids) <= 10^9
0 <= item_ids[i] <= 10^12
0 <= k <= 10^6
The input can be processed as an iterable or stream
Exact frequency counts are required

Function Signature

def top_k_items(item_ids, k):

Your question is Top-K Popular Items With Hash and Heap. 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