Data structures and algorithms
You need the 100 largest values from a stream of 10⁹ numbers you cannot store.
You need the 100 largest values from a stream of numbers you cannot store. What do you use?
- ASort everything and take the last hundred values
- BA min-heap of size 100
- CA max-heap holding every value seen so far
- DA hash map counting how often each value appears
Try it
Pick an answer
Next free question: An L1 cache reference costs about 1 ns and a main-memory reference about 100 ns.
Show the answer and worked solution
Answer: B – A min-heap of size 100
Keep a min-heap capped at 100. For each new value, compare it with the heap’s root, which is the smallest of the current best hundred; discard it if it is smaller, otherwise pop the root and push the new value. That is per element and overall, in space, on a single pass. The counter-intuitive part is that you want a min-heap to find maxima, because the element you need cheap access to is the weakest survivor. Sorting or holding every value needs space, which the premise forbids.
Worked solution
- Formula
- Substitute
- Solve
- Answer
Sanity check. A min-heap is what you want for maxima, because the element needing cheap access is the weakest survivor.
- A. You cannot store the stream, and sorting would be with space.
- B. Correct: time and space, and it works on a single pass.
- C. That is space, which the premise rules out.
- D. Frequency is not the question, and it is still linear space.
Takeaway: A size- heap gives the top of a stream in .
Report an issue with this question
Learn the method
Of the kind reported at
More data structures and algorithms questions
- What does the recurrence T(n) = 2T(n/2)+O(n) solve to?Applied · Free solution
- Strassen’s matrix multiplication satisfies T(n) = 7T(n/2)+O(n²).Advanced · Premium
- Climbing a staircase, part 3 of 3Advanced · Premium
- How many times does the inner body run in for i in range(1000): for j in range(i): body()?Foundation · Premium
- A hot-path buffer is a dynamic array with O(1) amortised push.Applied · Premium
- What does the recurrence T(n) = 4T(n/2)+Θ(n²) solve to?Applied · Premium