Efficient Data Processing Implementation | Dataford Interview Questions

Your question is Efficient Data Processing Implementation. Start with the requirements on the right.

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

Problem

A ThoughtWorks MLOps pipeline receives an array of integer feature IDs emitted by model-serving events. Implement a function that returns the k most frequently occurring feature IDs.

Rank IDs by descending frequency. If two IDs have the same frequency, rank the smaller ID first. Return exactly k IDs, or all distinct IDs if fewer than k exist.

Formal Specification

Implement top_k_features(events, k):

Input events: a list of integers, where each integer is a feature ID.
Input k: a positive integer.
Output: a list of up to k distinct integers ordered by descending frequency and then ascending feature ID.

The result must not contain duplicate IDs. The algorithm should avoid sorting every distinct ID when k is much smaller than the number of distinct IDs.

Constraints

1 <= len(events) <= 10^5
1 <= k <= 10^5
0 <= events[i] <= 10^9
The input may contain repeated feature IDs

Function Signature

def top_k_features(events, k):