Notes
Algorithm Interview
Sorting and Selection

Sorting and Selection

Two Heaps

Overview

Find Median from Data Stream

Description

  • Implement a class that can take numbers from a data stream, and can return the median of all the number it had taken

Solution

  • A brute-force approach could be to maintain a sorted list.
  • As with priority queue, we do not need a fully sorted structure to only find the median. We use a heap to find the max/min value of all the elements, and we can use a min heap and a max heap with the same size to find

Exercise

SearchingDynamic Programming