How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Maintain streaming median and loosemedian

Quick Overview

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.

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].

Input: ([8],)

Expected Output: [[8.0, 8.0, 16.0]]

Explanation: Median is exactly the power of two 8 = 2^3, so it sits on the lower boundary: interval [8, 16].

Input: ([5, 5, 5, 5],)

Expected Output: [[5.0, 4.0, 8.0], [5.0, 4.0, 8.0], [5.0, 4.0, 8.0], [5.0, 4.0, 8.0]]

Explanation: All duplicates: median stays 5 at every step; 4 < 5 < 8 so the interval is always [4, 8].

Input: ([1000000],)

Expected Output: [[1000000.0, 524288.0, 1048576.0]]

Explanation: Large value: 2^19 = 524288 <= 1000000 < 1048576 = 2^20, so the interval is [524288, 1048576].

Input: ([7, 3, 1, 9, 5],)

Expected Output: [[7.0, 4.0, 8.0], [5.0, 4.0, 8.0], [3.0, 2.0, 4.0], [5.0, 4.0, 8.0], [5.0, 4.0, 8.0]]

Explanation: Unsorted stream. Running medians are 7, 5, 3, 5, 5; the heaps keep the running order correct so each median maps to the right power-of-two bucket.

Input: ([2, 6],)

Expected Output: [[2.0, 2.0, 4.0], [4.0, 4.0, 8.0]]

Explanation: After 2: median 2 = 2^1 on the lower boundary -> [2,4]. After 6: even count, median = (2+6)/2 = 4 = 2^2 on the lower boundary -> [4,8].

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].

Quick Overview