Sliding-Window Hashmap Aggregation | Dataford Interview Questions

An AMD ROCm profiling pipeline receives metric labels emitted by consecutive GPU events. Given the labels and a window size, return the number of distinct labels in every contiguous window of exactly k events.

Implement an efficient sliding-window solution using a hash map. When a label enters the window, update its frequency. When a label leaves, decrement its frequency and remove it when the frequency reaches zero.

Formal Specification

Implement distinct_metrics_in_windows(events, k).

Input events: a list of strings representing consecutive ROCm metric labels.
Input k: a positive integer window size.
Output: a list of integers, where the value at index i is the number of distinct labels in events[i:i + k].
If k is greater than the number of events, return an empty list.

Constraints

1 <= len(events) <= 100000
1 <= k <= 100000
Each label is a non-empty string of at most 64 characters
The input order represents event order

Function Signature

def distinct_metrics_in_windows(events, k):

Your question is Sliding-Window Hashmap Aggregation. 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