Google·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Google SWE interview with a pretty involved data structures question that had a lot of moving parts. The core problem wasn't that hard to set up but the follow-ups on edge cases and bit operations made it a real workout.

Questions Asked (1)

Design a data structure for an online stream of positive integers that supports insert(x). After each insertion it should output: (a) the running median (for even counts, use the average of the two middle values), and (b) a 'loose median' interval [2^k, 2^(k+1)] where k is the unique integer such that 2^k < median < 2^(k+1). Describe your algorithms, time and space complexity, how you'd use bit operations to find k from the median, and how you'd handle edge cases like the median landing exactly on a power of two, non-integer medians, or zero/negative inputs.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

I got the two-heap setup pretty fast, min-heap and max-heap balanced to give O(log n) inserts and O(1) median reads.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and edge cases, then propose a two-heap solution for the running median and a bitwise method to compute the loose median interval. Analyze time and space complexity, and discuss trade-offs and edge cases such as exact powers of two and non-integer medians.

Pro tip: Mention that the loose median interval can be computed in O(1) using bitwise operations on the integer part of the median, and proactively discuss how to handle non-integer medians by considering the floor or ceiling. This shows attention to detail and efficiency.

1. Clarify requirements and edge cases

Ask about input constraints (e.g., positive integers, stream size, memory limits) and confirm the definition of loose median interval, especially for medians that are exactly powers of two or non-integers.

2. Design running median data structure

Use two heaps: a max-heap for the lower half and a min-heap for the upper half, balancing them after each insertion to allow O(log n) insertion and O(1) median retrieval.

3. Compute loose median interval with bit operations

For a median m, compute k = floor(log2(m)) using bitwise operations (e.g., find the highest set bit of the integer part), then the interval is [2^k, 2^(k+1)]. Handle exact powers of two by adjusting k to ensure strict inequality.

4. Analyze complexity and trade-offs

State that insertion is O(log n) time, median retrieval is O(1), and space is O(n). Discuss alternatives like balanced BSTs or order-statistic trees and their trade-offs.

5. Address edge cases and validation

Explain handling of non-integer medians (use floor/ceiling), exact powers of two (adjust k), and invalid inputs (zero/negative) by rejecting or clarifying assumptions.

Key Points to Mention

Two-heap approach for running median: max-heap for lower half, min-heap for upper half, with balancing to maintain size difference ≤ 1.
Bitwise computation of k: use highest set bit of the integer part of the median, e.g., via bit_length() or a loop shifting bits.
Handling exact powers of two: if median is exactly 2^k, the interval should be [2^(k-1), 2^k] to satisfy strict inequality, or clarify with the interviewer.
Non-integer medians: compute k from the floor or ceiling, and explain the choice; ensure the interval contains the median.
Time and space complexity: O(log n) insertion, O(1) median and interval retrieval, O(n) space.
Edge cases: zero/negative inputs (reject or handle separately), empty stream, and very large numbers (consider overflow in averaging).

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.