Retrieving the top 100 numbers from one hundred million of numbers [duplicate]

by

Run them all through a min-heap of size 100: for each input number k, replace the current min m with max(k, m). Afterwards the heap holds the 100 largest inputs.

A search engine like Lucene can use this method, with refinements, to choose the most-relevant search answers.

Edit: I fail the interview — I got the details wrong twice (after having done this before, in production). Here’s code to check it; it’s almost the same as Python’s standard heapq.nlargest():

import heapq

def funnel(n, numbers):
    if n == 0: return []
    heap = numbers[:n]
    heapq.heapify(heap)
    for k in numbers[n:]:
        if heap[0] < k:
            heapq.heapreplace(heap, k)
    return heap

>>> funnel(4, [3,1,4,1,5,9,2,6,5,3,5,8])
[5, 8, 6, 9]

More Related Contents:

  1. Algorithm to beat Strassen’s Algorithm
  2. What does O(log n) mean exactly?
  3. Select k random elements from a list whose elements have weights
  4. How are ssl certificates verified?
  5. Generate an integer that is not among four billion given ones
  6. Find duplicates in an array, without using any extra space
  7. How to generate Sudoku boards with unique solutions
  8. How to round floats to integers while preserving their sum?
  9. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  10. Maximize the rectangular area under Histogram
  11. Efficient algorithm for ordering different types of objects
  12. O(nlogn) Algorithm – Find three evenly spaced ones within binary string
  13. How to find two most distant points?
  14. Smooth spectrum for Mandelbrot Set rendering
  15. Why is the complexity of computing the Fibonacci series 2^n and not n^2?
  16. median of three values strategy
  17. Sorting an array with minimal number of comparisons
  18. Determining if two line segments intersect? [duplicate]
  19. Fastest algorithm for circle shift N sized array for M position
  20. Write a program to find 100 largest numbers out of an array of 1 billion numbers
  21. Lights out game algorithm
  22. How to find distance from the latitude and longitude of two locations?
  23. How does this work? Weird Towers of Hanoi Solution
  24. Generating shuffled range using a PRNG rather than shuffling
  25. Find out which combinations of numbers in a set add up to a given total
  26. Print the biggest K elements in a given heap in O(K*log(K))?
  27. Find local minimum in n x n matrix in O(n) time
  28. Why is bubble sort O(n^2)?
  29. Location of highest density on a sphere
  30. What is the difference between Linear search and Binary search?

Leave a Comment