Store the largest 5000 numbers from a stream of numbers

by

The simplest solution for this is maintaining a min heap of max size 5000.

  • Every time a new number arrives – check if the heap is smaller then
    5000, if it is – add it.
  • If it is not – check if the minimum is smaller then the new
    element, and if it is, pop it out and insert the new element instead.
  • When you are done – you have a heap containing 5000 largest elements.

This solution is O(nlogk) complexity, where n is the number of elements and k is the number of elements you need (5000 in your case).

It can be done also in O(n) using selection algorithm – store all the elements, and then find the 5001th largest element, and return everything bigger than it. But it is harder to implement and for reasonable size input – might not be better. Also, if stream contains duplicates, more processing is needed.

More Related Contents:

  1. Heap vs Binary Search Tree (BST)
  2. How do you validate a binary search tree?
  3. In Order Successor in Binary Search Tree
  4. Finding height in Binary Search Tree
  5. Apply Quicksort to the list M,E,R,G,E,S,O,R,T
  6. How to determine if a point is in a 2D triangle? [closed]
  7. How does the Google “Did you mean?” Algorithm work? [closed]
  8. How to find all combinations of coins when given some dollar value [closed]
  9. Data structures for loaded dice?
  10. Writing your own square root function
  11. Merge Sort a Linked List
  12. How do you like your primary keys? [closed]
  13. How to read values from numbers written as words?
  14. Sorting in place
  15. Programming Riddle: How might you translate an Excel column name to a number?
  16. fitting n variable height images into 3 (similar length) column layout
  17. Given a number, produce another random number that is the same every time and distinct from all other results
  18. Strategies for simplifying math expressions
  19. Painter puzzle – algorithmic estimation from first principles
  20. Polynomial time and exponential time
  21. How to count integers between large A and B with a certain property?
  22. Why is depth-first search claimed to be space efficient?
  23. How can I convert between a double-double and a decimal string?
  24. When is each sorting algorithm used? [closed]
  25. Convert light frequency to RGB?
  26. What is the problem name for Traveling salesman problem(TSP) without considering going back to starting point?
  27. 3-PARTITION problem
  28. Binary tree level order traversal
  29. Portable efficient alternative to PDEP without using BMI2?
  30. Postfix notation to expression tree

Leave a Comment