The problem
Return the k largest values of nums, largest first. Repeated values count separately. k is between 0 and len(nums).
top_k([5, 1, 9, 3, 7, 2, 8, 6], 3) -> [9, 8, 7]
top_k([5, 5, 1, 5, 2], 2) -> [5, 5]
The heapq module is switched off for this problem: write the heap yourself. A heap is a plain list with sift up and sift down (lessons 1 and 2); you can copy your class from HEAP-P1.
One test passes in numbers that count how often they are compared with <, <=, > or >=. They behave like ordinary numbers otherwise. This is how the tests tell an O(log n) heap step from an O(n) scan, which a timer cannot always do.
Limits
- Up to 200,000 values. With 20,000 values and k = 10, use at most 3n comparisons. Sorting all the values uses too many, and so does calling
max()k times.
Builds on HEAP-5 Top-k and k-way merge.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Three largest | Not run | |
| 2 | k = 1 | Not run | |
| 3 | k = 0 | Not run | |
| 4 | All of them | Not run | |
| 5 | Repeated values | Not run | |
| 6 | Negative values | Not run | |
| 7 | Comparisons | Not run | |
| 8 | 200,000 values | Not run |