Find Median from Data Stream
Hard · Heap & Priority Queue · about 25 minutes
Asked at Google, Amazon, Netflix, Databricks, Datadog, Elastic, Cohere, Hugging Face, Akamai.
Design a structure supporting addNum(x) and findMedian() over a stream of integers. findMedian should run in O(1) and addNum in O(log n).