RLE Iterator

RLE Iterator

What is this problem about?

The RLE Iterator interview question asks you to design an iterator over a run-length encoded sequence. The encoding is given as an array where even-indexed elements are counts and odd-indexed elements are values (e.g., [3, 8, 2, 5] means three 8s followed by two 5s). The iterator must support a next(n) operation that exhausts the next n elements and returns the last value exhausted, or -1 if the sequence is exhausted.

Why is this asked in interviews?

Databricks, Meta, and Google ask this problem because it tests object-oriented design, state management, and lazy evaluation — core concepts in data streaming systems, media encoding, and storage optimization. Run-length encoding is used in image compression (PCX, BMP), fax transmission, and DNA sequence storage. Designing an iterator that efficiently processes the sequence without decoding it first is the key skill.

Algorithmic pattern used

The pattern is stateful iterator design with pointer tracking. Maintain two instance variables: a pointer idx into the encoding array, and the remaining count of the current run. For next(n):

1. While n > 0 and the sequence is not exhausted: if the remaining count of the current run ≥ n, reduce the remaining count by n and return the current value. Otherwise, subtract the remaining count from n (exhaust the current run) and advance to the next run.
2. If the sequence is exhausted before n reaches 0, return -1.

Example explanation

Encoding: [3, 8, 0, 9, 2, 5] → three 8s, zero 9s, two 5s.

Initialize: idx=0, remaining=3.

• next(2): n=2 ≤ remaining=3 → remaining becomes 1. Return 8.
• next(1): n=1 ≤ remaining=1 → remaining becomes 0. Return 8. (Advance to next run: idx=2, remaining=0 → skip (0 nines) → idx=4, remaining=2.)
• next(3): n=3 > remaining=2 → exhaust 2 fives (n=1), sequence done. Return -1.

Common mistakes candidates make

• Not skipping runs with 0 count during initialization or iteration.
• Returning the last value seen when the sequence is exhausted rather than -1.
• Not advancing the pointer correctly when a run is fully exhausted — must increment idx by 2 (skipping both count and value).
• Decoding the entire sequence upfront into a flat array, wasting memory for very large encodings.

Interview preparation tip

For the RLE Iterator coding problem, the array, design, and iterator interview pattern is key. Initialize the iterator with the encoding array and a pointer at the first count. The next(n) method should consume lazily — never expand the encoding. Databricks and Google interviewers appreciate the discussion of lazy vs. eager decoding tradeoffs. Practice drawing the state transitions (idx, remaining) for a few next() calls on paper before coding.