Explain how to find 100 largest numbers out of an array of 1 billion numbers

Technology CommunityCategory: Heaps and MapsExplain how to find 100 largest numbers out of an array of 1 billion numbers
VietMX Staff asked 3 years ago
  • The brute force solution will be to sort the array in O(n log n) time complexity and take the last 100 numbers but you can do better.
  • You can keep a priority queue (implemented as a heap) of the 100 biggest numbers, iterate through the billion numbers, whenever you encounter a number greater than the smallest number in the queue (the head of the queue), remove the head of the queue and add the new number to the queue. In general, if you need the largest K numbers from a set of N numbers, the complexity is O(N log K) rather than O(N log N), this can be very significant when K is very small comparing to N.
  • You can also apply problem solving process. Ask interviewer the range or meaning of these numbers to make the problem clear. If, for example, these numbers stands for people’s age of within a country (e.g. China), then it’s a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an int array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it’s a piece of cake to find 100 largest number. By the way this also is called counting sort. Counting sort takes O(n + k) time and O(n + k) space, where n is the number of items we’re sorting and k is the number of possible values.