Character at a Position in a Run-Length Encoded String Without Decoding
Company: Waymo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
A sequence of characters has been stored with run-length encoding: each maximal run of one repeated character is written as the character followed by the run length. For example, the sequence `B, A, A, E, E, E, C` is stored as `"B1A2E3C1"`.
Implement a lookup that, working from the encoded data, returns the character at position `p` of the original (decoded) sequence. The runs can be very long, so decoding the whole sequence is not an option. The console version answers a batch of positions in one call.
### Function Signature
```python
def char_at_positions(encoded: str, positions: list[int]) -> list[str]:
```
### Rules
- `encoded` is a concatenation of runs. Each run is one uppercase English letter followed by its length written in decimal with no leading zeros.
- Positions are 0-indexed into the decoded sequence.
- Return one single-character string per query, in the same order as `positions`.
### Constraints
- `1 <=` number of runs `<= 10^5`
- Each run length is an integer in `[1, 10^9]`.
- The decoded length (the sum of all run lengths) is at most `10^14`, which is below `2^53`.
- `1 <= len(positions) <= 10^5`
- `0 <= positions[j] <` decoded length.
### Examples
**Example 1**
- Input: `encoded = "B1A2E3C1"`, `positions = [0, 1, 2, 3, 5, 6]`
- Output: `["B", "A", "A", "E", "E", "C"]`
- Explanation: The decoded sequence is `B A A E E E C`, with positions 0 through 6.
**Example 2**
- Input: `encoded = "X1000000000Y1Z25"`, `positions = [999999999, 1000000000, 1000000001, 1000000025]`
- Output: `["X", "Y", "Z", "Z"]`
- Explanation: Positions 0 to 999999999 hold `X`, position 1000000000 holds `Y`, and positions 1000000001 to 1000000025 hold `Z`.
Overview: Given a run-length encoded string such as B1A2E3C1, return the character at each queried position of the decoded sequence without decoding it. Runs can be very long, so the task tests prefix sums over run lengths and fast lookup per query.
A sequence of uppercase letters has been stored with run-length encoding: every maximal run of one repeated letter is written as the letter followed by the run length in decimal. For example, the sequence `B, A, A, E, E, E, C` is stored as `"B1A2E3C1"`.
Given the encoded string and a batch of 0-indexed positions into the **decoded** sequence, return the letter found at each position. Runs can be up to a billion characters long, so expanding the sequence is not an option — answer every query directly from the encoded data.
### Function Signature
```python
def char_at_positions(encoded: str, positions: list[int]) -> list[str]:
```
### Rules
- `encoded` is a concatenation of runs. Each run is one uppercase English letter (`A`-`Z`) followed by its length written in decimal with no leading zeros.
- Runs are maximal: two adjacent runs never use the same letter (the same letter may reappear in non-adjacent runs).
- Positions are 0-indexed into the decoded sequence. They may repeat and need not be sorted.
- Return a list with exactly one single-character string per query, in the **same order as `positions`** (not sorted order).
### Constraints
- `1 <=` number of runs `<= 10^5`
- Each run length is an integer in `[1, 10^9]`.
- The decoded length (the sum of all run lengths) is at most `10^14`, which is below `2^53`.
- `1 <= len(positions) <= 10^5`
- `0 <= positions[j] <` decoded length.
- Positions and running totals of run lengths can exceed `2^31 - 1`: use 64-bit integers (`long` in Java, `long long` in C++). Every value stays below `2^53`, so JavaScript numbers represent them exactly.
### Examples
**Example 1**
- Input: `encoded = "B1A2E3C1"`, `positions = [0, 1, 2, 3, 5, 6]`
- Output: `["B", "A", "A", "E", "E", "C"]`
- Explanation: The decoded sequence is `B A A E E E C`, with positions 0 through 6.
**Example 2**
- Input: `encoded = "X1000000000Y1Z25"`, `positions = [999999999, 1000000000, 1000000001, 1000000025]`
- Output: `["X", "Y", "Z", "Z"]`
- Explanation: Positions 0 to 999999999 hold `X`, position 1000000000 holds `Y`, and positions 1000000001 to 1000000025 hold `Z`.
Constraints
- 1 <= number of runs <= 10^5
- 1 <= each run length <= 10^9
- decoded length (sum of all run lengths) <= 10^14 (below 2^53)
- 1 <= len(positions) <= 10^5
- 0 <= positions[j] < decoded length
- encoded uses uppercase letters A-Z; lengths are decimal with no leading zeros; adjacent runs use different letters
- positions and prefix sums can exceed 2^31 - 1: use 64-bit integers (long / long long)
Examples
Input: ('B1A2E3C1', [0, 1, 2, 3, 5, 6])
Expected Output: ['B', 'A', 'A', 'E', 'E', 'C']
Input: ('X1000000000Y1Z25', [999999999, 1000000000, 1000000001, 1000000025])
Expected Output: ['X', 'Y', 'Z', 'Z']
Hints
- You never need the decoded sequence itself — only where each run starts and ends inside it.
- Parse the string once, recording the cumulative length after each run. That list is strictly increasing.
- For a position p, which run's cumulative end is the first one greater than p? A sorted list lets you find it in logarithmic time.