Find Top-K Frequent Interactions | Dataford Interview Questions

Your question is Find Top-K Frequent Interactions. 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

Pearson MyLab collects student engagement logs, where each log identifies an interaction such as "view_assignment" or "submit_quiz". Given a list of interaction names and an integer k, return the k most frequent interactions.

Use frequency counting and an efficient selection strategy rather than sorting every interaction when k is much smaller than the number of distinct interactions.

Formal Specification

Implement top_k_interactions(logs, k).

Input: logs, a list of strings, and k, a positive integer.
Output: A list of [interaction, frequency] pairs.
Order results by decreasing frequency. If two interactions have the same frequency, order them lexicographically by interaction name.
Return all distinct interactions if k exceeds the number of distinct interactions.

Constraints

1 <= len(logs) <= 10^5
1 <= k <= 10^4
Each interaction name is a non-empty string of at most 50 characters
The number of distinct interactions may be as large as len(logs)

Function Signature

def top_k_interactions(logs, k):