Maintain a Streaming Median
Company: Cognitiv
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are designing a component that receives integers one at a time and must return the current median after each update.
Example:
- After processing `[2, 3, 1]`, the median is `2`.
- After processing one more value to form `[2, 3, 1, 4]`, the median is `(2 + 3) / 2 = 2.5`.
Implement a data structure with two operations:
- `add(x)`: insert an integer
- `getMedian()`: return the median of all inserted values so far
Discuss the time complexity of your approach.
Follow-up: if the full input array is available up front and you want to avoid extra auxiliary space, how would you compute the median while minimizing additional memory usage?
Quick Answer: This question evaluates understanding of streaming algorithms and dynamic data structures for maintaining order statistics, along with analysis of time complexity and memory trade-offs.
Process add and median operations using two heaps, returning medians for median queries.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([["add",2],["add",3],["add",1],["median"],["add",4],["median"]],)
Expected Output: [2, 2.5]
Explanation: Medians after odd and even counts.
Input: ([["median"],["add",5],["median"]],)
Expected Output: [None, 5]
Explanation: Empty stream median is None.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.