Design a streaming median structure
Overview
This question evaluates a candidate's competency in designing efficient data structures and algorithmic reasoning for dynamic order-statistics and streaming data within the Coding & Algorithms domain, emphasizing APIs, internal invariants, and rigorous time/space complexity analysis.
Amazon
Aug 7, 2025, 12:00 AM
Software Engineer
Onsite
Coding & Algorithms
0
0
Design a data structure for a number stream that supports: add(num: int) in O(log n) time and median() -> float in O(
- or O(log n) time. It must handle up to 10^6 operations, duplicates, and both even/odd counts. Describe the APIs, internal invariants, and prove the time/space complexity. Implement the core methods.