Maintain streaming median and loosemedian
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design a data structure for an online stream of positive integers supporting insert
(x). After each insertion, output:
(a) the median of all values seen so far (for an even count, define the median as the average of the two middle values); and
(b) the 'loose median' interval [2^k, 2^(k+
1)] where k is the unique integer satisfying 2^k < median < 2^(k+
1). Describe the algorithms and data structures, their time and space complexities, and how to implement bit operations to compute 2^k from the median. Discuss how you would handle boundary cases (e.g., median equals a power of two, zero/negative numbers, or non-integer medians).
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Maintain streaming median and loosemedian states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
You are given an online stream of positive integers. Process the integers one at a time in the given order. After each insertion, compute two things over all values seen so far:
(a) the **median** of the values inserted so far. For an odd count this is the middle value; for an even count it is the average of the two middle values (so it may be a non-integer such as 3.5).
(b) the **loose median** interval `[2^k, 2^(k+1)]` that contains the current median, where `k = floor(log2(median))`. Equivalently, find the largest power of two not exceeding the median; that power is the lower bound `2^k` and the next power of two is the upper bound `2^(k+1)`. When the median is exactly a power of two it sits on the lower boundary of its interval (e.g. a median of 8 gives `[8, 16]`).
Return a list with one entry per insertion. Each entry is a 3-element list `[median, low, high]` where `median` is the current median and `[low, high] = [2^k, 2^(k+1)]` is the loose-median interval.
Implementation hint: maintain two heaps — a max-heap for the lower half and a min-heap for the upper half — to get O(log n) inserts and O(1) median lookups. Compute `2^k` with a bit shift (`1 << k`) rather than floating-point exponentiation, and watch out for floating-point error when taking `log2` of a value near a power of two.
Example: stream `[3, 4, 5]` -> after 3: median 3, interval [2,4]; after 4: median 3.5, interval [2,4]; after 5: median 4, interval [4,8]. Result: `[[3.0, 2.0, 4.0], [3.5, 2.0, 4.0], [4.0, 4.0, 8.0]]`.
Constraints
- 1 <= len(nums)
- All values are positive integers (x >= 1), so log2(median) is always defined and the loose-median interval exists.
- Median may be a non-integer (.5) when the count is even.
- Compute 2^k with a bit shift (1 << k); guard log2 against floating-point error near powers of two.
Examples
Input: ([3, 4, 5],)
Expected Output: [[3.0, 2.0, 4.0], [3.5, 2.0, 4.0], [4.0, 4.0, 8.0]]
Explanation: Odd then even then odd counts. After 4 the count is even so median = (3+4)/2 = 3.5, still in [2,4]. After 5 the median is 4, which lands on the lower boundary of [4,8].
Input: ([1],)
Expected Output: [[1.0, 1.0, 2.0]]
Explanation: Single element: median 1 = 2^0, interval [1, 2].
Hints
- Maintain two heaps: a max-heap for the lower half and a min-heap for the upper half. Keep their sizes balanced so the median is at the heap tops.
- For an even count the median is the average of the two heap tops and can be a non-integer such as 3.5; for an odd count it is the larger heap's top.
- The loose median k = floor(log2(median)). Compute the bounds as 1<<k and 1<<(k+1). Because log2 of a float can be slightly off near a power of two, verify and nudge k with a small while-loop so that 2^k <= median < 2^(k+1).
- When the median equals a power of two (e.g. 8), it sits on the lower boundary, giving [8, 16].