Top-K Frequent Item Pairs | Dataford Interview Questions

Quinstreet comparison surfaces record user sessions as sequences of interacted item IDs. Given these sessions, find the k most frequent unordered item pairs that appeared together in at least one session.

A pair counts at most once per session, even if a user interacted with the same item repeatedly. Return pairs ordered by decreasing frequency. When frequencies tie, order pairs lexicographically by their two item IDs.

Formal Specification

Implement top_k_item_pairs(sessions, k), where sessions is a list of lists of non-negative integer item IDs and k is a positive integer. Return a list of pairs, represented as two-element lists [smaller_id, larger_id]. Return fewer than k pairs if fewer distinct pairs exist.

Constraints

0 <= len(sessions) <= 10^4
The total number of interactions is at most 10^5
0 <= item_id <= 10^9
1 <= k <= 10^4
Pairs are unordered and contain two distinct item IDs

Function Signature

def top_k_item_pairs(sessions, k):

Your question is Top-K Frequent Item Pairs. 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

Formal Specification

Constraints

0 <= len(sessions) <= 10^4
The total number of interactions is at most 10^5
0 <= item_id <= 10^9
1 <= k <= 10^4
Pairs are unordered and contain two distinct item IDs

Function Signature

def top_k_item_pairs(sessions, k):

Your question is Top-K Frequent Item Pairs. 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.