Google·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026

Summary

Google SWE coding round, one problem the whole time. It was a twist on the classic median-of-two-sorted-arrays problem but with run-length encoding thrown in, so you couldn't just decompress and brute force your way through it.

Questions Asked (1)

Given two sorted arrays in run-length encoded form (each as a list of value-frequency pairs), find the median of the fully merged array without decompressing it. Target O(log(m+n)) time.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the base LC 4 problem well enough, but the RLE wrapping genuinely slowed me down.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the RLE arrays represent sorted sequences and that the merged array size is the sum of frequencies. Then, adapt binary search on the shorter array to work with cumulative frequencies, using prefix sums to map positions to values without decompression. Finally, handle edge cases like empty arrays and ensure the partition logic correctly identifies the median.

Pro tip: Mention that you would precompute prefix sums of frequencies to enable O(1) access to the value at any index, and emphasize that the binary search is on the partition index of the shorter array, not on the values themselves.

1. Clarify and Define

Confirm the input format, total length, and that the median is defined as the middle element (or average of two middle elements) of the fully merged sorted array. Discuss how to handle even/odd total lengths.

2. Preprocess for Efficient Access

Compute prefix sums of frequencies for each RLE array to allow O(1) retrieval of the value at any index via binary search on the prefix sums. This avoids decompression.

3. Binary Search on Partition

Perform binary search on the partition index of the shorter array (by total length). For each partition, compute the corresponding partition in the other array and check if the max of left parts ≤ min of right parts.

4. Handle Edge Cases and Compute Median

Adjust for empty arrays, partitions at boundaries, and compute the median based on the max of left and min of right elements. Ensure the algorithm runs in O(log(min(m,n))) time.

5. Analyze Complexity and Trade-offs

Explain that the time complexity is O(log(min(m,n))) due to binary search, and space complexity is O(1) extra beyond the prefix sums. Discuss why decompression would be O(m+n) and less efficient.

Key Points to Mention

Prefix sums of frequencies to enable O(1) access to the value at any index.
Binary search on the partition index of the shorter array to achieve logarithmic time.
Handling of even and odd total lengths for median calculation.
Edge cases: empty arrays, all elements in one array, partitions at boundaries.
Time complexity: O(log(min(m,n))) and space complexity: O(1) extra (or O(m+n) if prefix sums stored).
Comparison with naive decompression approach and why it's inefficient.

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