Find the Most Frequent Request IDs
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
A service receives a large sequence of request IDs. Return the `k` IDs with the highest frequency so an operator can identify the heaviest request sources.
## Function Contract
Implement `top_request_ids(request_ids, k)` and return a list of IDs.
## Rules
- Rank IDs by descending frequency.
- When two IDs have the same frequency, rank the smaller ID first.
- Return every distinct ID when `k` exceeds the number of distinct IDs.
- The result must be deterministic and already in ranking order.
## Constraints
- `1 <= len(request_ids) <= 500000`.
- `1 <= k <= len(request_ids)`.
- Each request ID is an integer in `[0, 10^9]`.
## Examples
```text
request_ids = [8, 4, 8, 2, 4, 8, 2, 4]
k = 2
output = [4, 8]
```
Both IDs occur three times, so the smaller ID wins the tie.
Quick Answer: Find the most frequent request IDs in a large event stream and return the top k in ranked order. The task tests frequency counting, deterministic tie-breaking by smaller ID, and handling k values larger than the distinct-ID count.
Given a nonempty sequence of integer request IDs and k, return up to k distinct IDs ranked by descending frequency. If two IDs have equal frequency, the smaller ID ranks first. If k exceeds the number of distinct IDs, return every distinct ID. The returned list must already be in this deterministic ranking order.
Constraints
- 1 <= len(request_ids) <= 500000.
- 1 <= k <= len(request_ids).
- Every request ID is an integer in [0, 1000000000].
Examples
Input: ([8, 4, 8, 2, 4, 8, 2, 4], 2)
Expected Output: [4, 8]
Explanation: IDs 4 and 8 tie at three occurrences, so 4 ranks first.
Input: ([5], 1)
Expected Output: [5]
Explanation: The only distinct ID is returned.
Hints
- Count frequencies before ranking distinct IDs.
- Use the ID itself as the ascending secondary key when counts tie.