Waymo·Software Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

Waymo SWE interview with a binary search problem that looked straightforward until the edge cases started stacking up. The encoded string constraint was the interesting part.

Questions Asked (1)

You're given a run-length encoded string as (character, count) pairs where the characters are guaranteed to be in non-decreasing sorted order. Implement a function FindByValue(target, left, right) that, within the decoded string's index range [left, right], returns the index of the first character strictly greater than the target. Return -1 if none exists in that range.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The sorted-characters guarantee is what makes this tractable.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search over the run-length encoded blocks to locate the first block whose character exceeds the target, then check if its start index falls within [left, right]. Handle edge cases by first finding the block containing left and adjusting the search range accordingly.

Pro tip: Clarify whether the target is guaranteed to be present and whether left/right are inclusive; also discuss the trade-off between O(log n) binary search and O(n) linear scan for small ranges.

1. Understand the problem and constraints

Confirm that the decoded string is sorted, indices are inclusive, and the function should return the first index > target within [left, right]. Discuss edge cases like empty range or target larger than all characters.

2. Preprocess the run-length encoding

Compute prefix sums of counts to map each block to its starting index in the decoded string. This allows O(1) conversion between block index and decoded index.

3. Binary search for the first block with character > target

Use binary search on the block characters to find the smallest block index where the character is strictly greater than target. If no such block exists, return -1.

4. Adjust for the left boundary

If the found block's start index is less than left, find the block containing left and check if its character > target. If so, return left; otherwise, continue from the next block.

5. Validate against right boundary and return result

Ensure the candidate index is ≤ right. If it is, return it; otherwise, return -1. Also handle the case where the target is greater than or equal to all characters in the range.

Key Points to Mention

Binary search over blocks using the sorted property of characters
Prefix sums to map block indices to decoded string indices
Handling inclusive range [left, right] and edge cases (empty range, target out of bounds)
Time complexity: O(log n) for binary search, O(1) extra space
Trade-offs: linear scan might be simpler for small ranges or when left/right are close
Clarifying questions: whether target is guaranteed to exist, if left/right are inclusive, and if the encoded string is static or dynamic

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