The k most frequent endpoints, without sorting the log
An access log is a list of endpoint paths, one per request. Return the k endpoints that appear most often, most frequent first. When two endpoints have the same count, the one that sorts first alphabetically comes first.
The log can have a hundred million lines and a few thousand distinct endpoints. Counting is unavoidable; sorting every distinct endpoint to take k of them is not, and the follow-up asks you to say why.
If there are fewer than k distinct endpoints, return all of them in that order.
Example
- input
log = ["/orders", "/health", "/orders", "/users", "/health", "/orders"], k = 2output["/orders", "/health"]/orders appears three times, /health twice, /users once.
Constraints
- 1 ≤ k ≤ 1,000
- 0 ≤ log.length ≤ 100,000,000
- paths are non-empty ASCII strings
Hints
Hint 1
Count with a HashMap and merge. Then keep a min-heap of size k: push every entry, and when the heap has k + 1 elements, poll the smallest.
Hint 2
The heap's comparator is the OPPOSITE of the output order: the entry that should come last in the answer is the one the heap must evict first.
Hint 3
Empty the heap into a list and reverse it. That is O(d log k) for d distinct endpoints, against O(d log d) for a sort.
Stuck? The lesson behind this problem: 🧮 Which structure, which collection
java
Tab indents · Escape first to tab out
Test cases
These are the specification. Run tests checks your answer against them.
| Case | Input | Expected |
|---|---|---|
| the example | ["/orders","/health","/orders","/users","/health","/orders"], k = 2 | ["/orders","/health"] |
| a tie breaks alphabetically | ["/b","/a","/b","/a"], k = 1 | ["/a"] |
| fewer than k endpoints | ["/x"], k = 5 | ["/x"] |
| empty log | [], k = 3 | [] |
| many distinct, small k | 1,000 distinct paths, path i appearing i times, k = 3 | ["/p999","/p998","/p997"] |