2dbi
Home/Asana/Find Median From a Data Stream
AAsana·DSASDE-2Onsite – Coding 1

Find Median From a Data Stream

Problem

Design a structure supporting addNum and findMedian over a stream.

Example

addNum(1),addNum(2) -> 1.5; addNum(3) -> 2

Constraints

  • up to 5 × 10^4 calls

Approach

Two heaps (max-heap lower half, min-heap upper half). Reported Asana question.

added 6 days ago
LeadersAccount