Most Frequent k Words or Bestselling Titles with Alphabetical Tie-Breaks
Company: Snowflake
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of items, such as the words in a stream of text (the hot words) or the book titles in a list of sales (the bestsellers), return the `k` items that occur most often.
### Function Signature
```python
def top_k_frequent(items: list[str], k: int) -> list[str]:
```
### Rules
- The count of an item is the number of times it appears in `items`.
- Return `k` distinct items ordered from the highest count to the lowest.
- Items with equal counts are ordered alphabetically, in ascending character order, and that order also decides which items are included when several items tie at the cut-off.
### Constraints
- `1 <= len(items) <= 10^5`
- Every item consists of 1 to 20 lowercase English letters.
- `1 <= k <=` the number of distinct items.
### Examples
**Example 1**
```text
Input: items = ["sql", "rust", "go", "sql", "go", "sql", "java"], k = 2
Output: ["sql", "go"]
```
`sql` appears 3 times and `go` twice; `rust` and `java` appear once each.
**Example 2**
```text
Input: items = ["sql", "rust", "go", "sql", "go", "sql", "java"], k = 3
Output: ["sql", "go", "java"]
```
`java` and `rust` tie with one occurrence each, and `java` comes first alphabetically.
**Example 3**
```text
Input: items = ["dune", "emma", "dune", "emma", "ulysses"], k = 1
Output: ["dune"]
```
`dune` and `emma` tie with two occurrences each, and `dune` comes first alphabetically.
Overview: Given a list of items such as trending words or bestselling book titles and a number k, return the k most frequent items ordered by count, with ties broken alphabetically. It tests frequency counting, sorting with a compound key and heap-based selection.
Given a list of items, such as the words in a stream of text (the hot words) or the book titles in a list of sales (the bestsellers), return the `k` items that occur most often.
Implement `top_k_frequent(items, k)`, which returns a list of strings.
### Rules
- The count of an item is the number of times it appears in `items`.
- Return exactly `k` distinct items, ordered from the highest count to the lowest.
- Items with equal counts are ordered alphabetically, in ascending character order. This is ordinary lexicographic string order, so a word comes before any longer word that begins with it (for example, `go` comes before `gol`).
- That same alphabetical order also decides which items are included when several items tie at the cut-off.
Because these rules rank every pair of distinct items, the returned list is always unique.
### Constraints
- `1 <= len(items) <= 10^5`
- Every item consists of 1 to 20 lowercase English letters (`a` to `z`).
- `1 <= k <=` the number of distinct items in `items`.
- No count and no value of `k` exceeds `10^5`, so no value exceeds `2^31 - 1`; 32-bit integers are enough in every language.
### Example 1
```text
Input: items = ["sql", "rust", "go", "sql", "go", "sql", "java"], k = 3
Output: ["sql", "go", "java"]
```
`sql` appears 3 times and `go` twice. `java` and `rust` tie with one occurrence each for the last place, and `java` comes first alphabetically.
### Example 2
```text
Input: items = ["dune", "emma", "dune", "emma", "ulysses"], k = 1
Output: ["dune"]
```
`dune` and `emma` tie with two occurrences each, and `dune` comes first alphabetically.
Constraints
- 1 <= len(items) <= 10^5
- Every item consists of 1 to 20 lowercase English letters (a to z).
- 1 <= k <= the number of distinct items in items.
- No count and no value of k exceeds 10^5, so no value exceeds 2^31 - 1; 32-bit integers are enough in every language.
Examples
Input: (['sql', 'rust', 'go', 'sql', 'go', 'sql', 'java'], 2)
Expected Output: ['sql', 'go']
Explanation: Source Example 1: sql appears 3 times and go twice; rust and java appear once each.
Input: (['sql', 'rust', 'go', 'sql', 'go', 'sql', 'java'], 3)
Expected Output: ['sql', 'go', 'java']
Explanation: Source Example 2: java and rust tie at one occurrence for the last slot; java wins alphabetically even though rust appears first.
Hints
- Start by working out how many times each distinct item occurs: the answer depends only on those counts, not on where the items appear.
- Comparing two items needs both rules at once: the higher count wins, and only an exact tie in count falls back to alphabetical order.
- Check ties at the cut-off and prefix pairs such as a and ab: the alphabetically earlier item is the one that makes the list.