algorithms

You are hosting an online auction that's open to millions of people. After your team presents a new item, you will wait for 30 minutes for people to privately send in their bid prices. In other words, during this 30 minutes, you will receive a data stream of integers like: 3100, 200, 4030, 12000, 399...

To get a better sense of how people are feeling about this item, the eager analyst on your team wants you to design an efficient algorithm that can output the median bid price you have seen so far at any given time during this 30 minutes. The complexity of one query for current median has to be O(1). And if you are maintaining some internal data structures, the runtime of maintaining that data structure cannot be greater than O(log n) per new bid price.

Use two heap data structures.