Exercise 1 solution

    import heapq

    class KthLargest:
        def __init__(self, k):
            self.k = k
            self.heap = []          # min-heap holding the k largest so far

        def add(self, x):
            if len(self.heap) < self.k:
                heapq.heappush(self.heap, x)
            elif x > self.heap[0]:
                heapq.heapreplace(self.heap, x)
            return self.heap[0] if len(self.heap) == self.k else None

    t = KthLargest(3)
    for x in [4, 5, 8, 2, 10, 1, 9]:
        print(x, "->", t.add(x))

Output:
    4 -> None
    5 -> None
    8 -> 4
    2 -> 4
    10 -> 5
    1 -> 5
    9 -> 8

The heap never holds more than k items, so each add costs O(log k) and the
memory stays small however long the stream is. Because it is a MIN-heap of
the k largest values, its smallest item (heap[0]) is exactly the k-th
largest overall. A new value only matters if it beats that smallest item,
in which case heapreplace removes the old smallest and inserts the new one
in a single step. Until k values have arrived there is no k-th largest, so
None is returned.