Top K Frequently Purchased Items | Dataford Interview Questions

Target wants to identify the items purchased most frequently by its guests. Given a list of purchased item identifiers and an integer k, return the k most frequently purchased items.

Return items ordered by decreasing purchase frequency. If multiple items have the same frequency, order those items lexicographically. Each item identifier is a non-empty string, and repeated identifiers represent separate purchases.

Formal Specification

Implement top_k_items(transactions, k), where transactions is a list of strings and k is a positive integer. Return a list of at most k strings. The result must contain every item with a higher frequency than any excluded item, subject to the stated tie-breaking rule.

Constraints

1 <= len(transactions) <= 10^5
1 <= k <= number of distinct items
Each item identifier contains 1 to 50 lowercase letters
The input may contain duplicate item identifiers

Function Signature

def top_k_items(transactions, k):

Your question is Top K Frequently Purchased Items. 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