Find the Most Frequent Request IDs

Problem Statement

You are monitoring service traffic on an internal microservice at Amazon. Given an array of integers request_ids representing incoming requests in a log window, and an integer k, return the k most frequent request IDs.

The results should be sorted primarily by frequency in descending order. If two request IDs have the same frequency, break the tie by choosing the smaller request ID first (in ascending numerical order).

If k is greater than or equal to the total number of distinct request IDs present in request_ids, return all distinct request IDs ordered according to the ranking rules above.

Function Interface

def top_k_request_ids(request_ids: list[int], k: int) -> list[int]:
    pass

Constraints

• 0 <= len(request_ids) <= 10^5
• 1 <= request_ids[i] <= 10^9
• 1 <= k <= 10^5

Examples

Example 1

Input: request_ids = [101, 202, 101, 303, 202, 101, 404], k = 2
Output: [101, 202]
Explanation:
- 101 appears 3 times.
- 202 appears 2 times.
- 303 appears 1 time.
- 404 appears 1 time.
The top 2 most frequent IDs are 101 and 202.

Example 2

Input: request_ids = [500, 300, 500, 300, 200], k = 5
Output: [300, 500, 200]
Explanation:
- 300 appears 2 times.
- 500 appears 2 times.
- 200 appears 1 time.
Both 300 and 500 have a frequency of 2. By tie-breaker rule, 300 precedes 500. There are only 3 distinct IDs, so all 3 are returned.

Edge Cases

• Empty input list: should return [].
• All IDs have the same frequency: output sorted in ascending order of IDs.
• k is larger than the number of unique IDs: return all unique IDs sorted by the frequency and tie-breaking rules.