CODEWITHSUNDEEP
algorithm
navin
navin

Reputation: 394

Given a stream of numbers how would you keep track of the 1,000,000th largest one?

Given a stream of numbers how would you keep track of the 1,000,000th largest one?

I was asked this in an interview.

Upvotes: 1

Views: 542

Answers (2)

ehudt
ehudt

Reputation: 810

One way would be to keep a minimum heap, and restrict the heap's size to 1,000,000. While the heap hasn't reached a 1,000,000 items, we'll add each new item from the stream into our heap. When the heap gets full, we'll compare each new item from the stream to the minimum in the heap, and if it's bigger than the minimum, we'll eject the minimum and insert the new item. This way, the heap's minimum item is always the 1,000,000th largest value.

Pseudo code example:

Handle_Stream_Item(item):
  if(MinHeap.size < 1000000):
    MinHeap.insert(item)
  else if (item > MinHeap.min()):
    MinHeap.extractMin()
    MinHeap.insert(item)

Upvotes: 14

fisharebest
fisharebest

Reputation: 1350

As each number is read from the stream, add it to a B-TREE structure.

https://en.wikipedia.org/wiki/B-tree

Starting with the million and first number, after adding the new number, remove the right-most (i.e. largest) one from the B-TREE.

At any one time, the right-most number in the B-TREE will be your desired number.

Upvotes: 0

Related Questions