Loading page…
Practice problem · medium
A monitoring system logs every request to a web service. Each log line holds the number of the endpoint that was hit, such as the login page or the search page. The dashboard shows the k busiest endpoints.
A day of traffic gives up to 100,000 log lines, and there are up to 100,000 different endpoints. The dashboard must name the busiest ones without sorting everything.
Write busiest(hits, k).
hits[i] is the number of the endpoint hit by the ith request.k highest-ranked endpoints, best first. If fewer than k endpoints were hit, return all of them.Input: hits = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]| Endpoint | Hits | Rank |
|---|---|---|
| 1 | 3 | first |
| 2 | 2 | second |
| 3 | 1 | third: dropped from the heap |
The heap of size 2 starts with endpoints 1 and 2. Endpoint 3 has fewer hits than the weakest on top, so it is dropped. The answer is 1, then 2.
Input: hits = [5, 7, 7, 5, 9], k = 2
Output: [5, 7]Endpoints 5 and 7 have 2 hits each, and 9 has 1. The tie between 5 and 7 goes to the smaller number, so the answer is 5, then 7.
Input: hits = [4], k = 3
Output: [4]Only one endpoint was hit, so the answer has one number.
1 ≤ length of hits ≤ 10^50 ≤ hits[i] ≤ 999991 ≤ k ≤ 10^5With up to 100,000 log lines you can count the hits in one pass. The harder part is the ranking: sorting all 100,000 endpoints works, but the dashboard needs only k of them, and k is often small.
A heap that never holds more than k endpoints picks the best k with about log k work for each endpoint, instead of log of all endpoints.
busiest · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.