Find median of merged RLE arrays
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
You are given two **run-length encoded (RLE)** arrays `A` and `B`. Each is sorted by `value` in non-decreasing order.
- Each element is a pair `(value, frequency)` meaning `value` appears `frequency` times in the underlying uncompressed array.
- Let `UA` be the uncompressed array represented by `A`, and `UB` similarly for `B`.
- Consider the fully merged multiset/array `U = sort(UA ∪ UB)` (i.e., as if you uncompressed both arrays and merged them into one sorted array).
Return the **median** of `U`.
## Median Definition
Let `N = len(U)`.
- If `N` is odd, the median is `U[N//2]` (0-indexed).
- If `N` is even, the median is `(U[N//2 - 1] + U[N//2]) / 2`.
## Constraints / Requirements
- `frequency` values may be very large, so you must **not** explicitly uncompress the arrays.
- `A` and `B` are individually sorted by `value`.
## Example
`A = [(1, 2), (5, 1)]` represents `[1, 1, 5]`
`B = [(2, 3)]` represents `[2, 2, 2]`
Merged: `[1, 1, 2, 2, 2, 5]` → median is `(2 + 2) / 2 = 2`
Quick Answer: The question evaluates understanding of run-length encoding, order-statistics (median) computation, and efficient merging of frequency-annotated sequences, emphasizing handling large frequencies without explicit decompression.
Return the median of the sorted multiset represented by two sorted run-length encoded arrays without expanding them.
Constraints
- A and B are sorted by value
- frequencies are positive
Examples
Input: ([(1, 2), (5, 1)], [(2, 3)])
Expected Output: 2.0
Explanation: Prompt example.
Input: ([(1, 1)], [(2, 1)])
Expected Output: 1.5
Explanation: Even total with average.
Input: ([], [(7, 5)])
Expected Output: 7
Explanation: One side empty.
Input: ([(1, 2), (3, 2)], [(2, 1)])
Expected Output: 2
Explanation: Odd total.
Hints
- Walk the RLE runs in value order and stop when median indices are reached.