Interview Question for Software Engineer at Amazon.com:

There are several things need to be considered when answering this question. First of all, we need a space to store 100 largest integers (called G). From the number 100th on ward (called x), if x is greater than any number in S, then we need to eliminate the minimum value in S and add x to S. Therefore, the expected data structure should facilitate the extract_minimum efficiently. In my opinion, using max-heap data structure could be one of the answers. For each x we compare with the root of the heap O(1). If x > root, then extract(root) - O(logn), then insert x to the heap O(log n) again.

Is there any other alternative solution?