Good for interviews: Python general sort -> insertion sort -> two heaps -> follow-ups
\n# sort O(NlogN)\nclass MedianFinder:\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.store = []
```\n# sort O(NlogN)\nclass MedianFinder:\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.store = []\n\n    def addNum(self, num: int) -> None:\n        self.store.append(num)\n        \n    def findMedian(self) -> float:\n        self.store.sort()\n        \n        n = len(self.store)-1\n        return self.store[n//2] if n % 2 == 0 else (self.store[n//2] + self.store[n//2 + 1])/2.0\n\n# insertion sort -> bisect using binary search O(logN)\n# insert -> O(N)\n# Time O(N) + O(logN) = O(N)\nfrom bisect import bisect_left\nclass MedianFinder:\n\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        self.store = []\n\n    def addNum(self, num: int) -> None:\n        if not self.store:\n            self.store.append(num)\n        else:\n            idx = bisect_left(self.store, num)\n            self.store.insert(idx, num)\n        \n    def findMedian(self) -> float:        \n        n = len(self.store)-1\n        return self.store[n//2] if n % 2 == 0 else (self.store[n//2] + self.store[n//2 + 1])/2.0\n\n# Time O(logN)\nfrom heapq import heappush, heappop\nclass MedianFinder:\n\n    def __init__(self):\n        """\n        initialize your data structure here.\n        """\n        # holds the smaller half\n        self.max = []\n        # holds the larger half\n        self.min = []\n        \n\n    def addNum(self, num: int) -> None:\n        heappush(self.max, -num)\n        heappush(self.min, -heappop(self.max))\n        if len(self.min) > len(self.max):\n            heappush(self.max, -heappop(self.min))\n\n        \n    def findMedian(self) -> float:\n        if len(self.max) == len(self.min):\n            return (self.min[0] - self.max[0])/2.0\n        else:\n            return -self.max[0]\n\n```\nOther nice things to mention:\nUse self-balancing BST, the median is either the root node or children of root, insertion takes O(logN).\nRed-black trees are better than AVL trees in this scenario because of a lot of insertions happening. \nMultiset data structures in a lot of languages are implemented using red-black trees.\n\nFollow-ups:\n\n1. If all integer numbers from the stream are between 0\xA0and 100, how would you optimize it?\n- bucket sort, create an array of bucket of length 101, keep the count of numbers in each bucket, and the count of overall numbers, then it\'s easy to locate the bucket where the median number resides and find the median by looping through the array-> O(1)\n2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?\n- 99% of all integer numbers lie in [0,100] means the median is definitely inside [0,100]. Besides the bucket range [0,100] as mentioned above, we just need to keep the count of all numbers, numbers smaller than 0, and numbers larger than 100, and adjust the index of the median element in our buckets of range [0,100].\nFor example, if we have 100 numbers streamed, and one of the number is smaller than 0, that means the median\'s index moved forward by 1, we just need to find the 49th element in our buckets in a sorted manner.
[]