Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Waymo software engineering interview with a coding problem centered on run-length encoded strings. Pretty algorithmic, felt like a classic phone screen but with enough depth to keep you on your toes if you only prepped the naive solution.

Questions Asked (1)

Given a run-length encoded string like 'B1A2E3C1' (which decodes to 'BAAEEEC'), implement a Find(int p) function that returns the character at position p in the decoded string without actually decoding the whole thing. Then discuss both an O(n) and an O(log n) approach, and handle edge cases like p being out of range or counts being multi-digit.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I started with the linear scan pretty naturally, just walk the pairs and track a running total until you hit the segment containing p.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, parse the encoded string into a list of (character, count) pairs, handling multi-digit counts. Then, for the O(n) approach, iterate through the pairs, subtracting counts from p until you find the character; for O(log n), precompute prefix sums of counts and use binary search to locate the character. Discuss trade-offs: O(n) is simple and uses O(1) extra space if parsing on the fly, while O(log n) requires O(n) preprocessing but enables faster queries.

Pro tip: Clarify upfront whether the encoded string is static or dynamic, and whether multiple queries will be made—this determines if preprocessing for O(log n) is worth it. Also, explicitly handle edge cases like p out of range and multi-digit counts to show attention to detail.

1. Clarify requirements and assumptions

Ask if the encoded string is fixed, if multiple queries will be made, and if p is 0-indexed or 1-indexed. Confirm that counts can be multi-digit and that the decoded string may be very large.

2. Parse the encoded string

Write a parser that extracts character and count pairs, correctly handling multi-digit numbers (e.g., 'A12' means 12 'A's). Store pairs in a list for further processing.

3. Implement O(n) approach

Iterate through the pairs, maintaining a running total of characters. When the running total exceeds p, return the current character. This is simple and uses O(1) extra space if parsing on the fly.

4. Implement O(log n) approach

Precompute an array of cumulative counts (prefix sums) for each pair. Use binary search to find the smallest index where the cumulative count > p, then return the character at that index.

5. Discuss trade-offs and edge cases

Compare time/space complexity: O(n) query with O(1) space vs O(log n) query with O(n) preprocessing. Handle edge cases: p out of range (return null or throw exception), empty string, and multi-digit counts.

Key Points to Mention

Parsing multi-digit counts correctly (e.g., 'A12' not 'A1' and '2').
Time and space complexity of both approaches: O(n) vs O(log n) query time, and preprocessing cost.
Binary search on prefix sums for O(log n) lookup.
Edge cases: p out of bounds, empty encoded string, zero counts (if allowed), and very large counts causing integer overflow.
Whether to preprocess for multiple queries or handle single query efficiently.
Indexing convention (0-indexed vs 1-indexed) and how it affects the algorithm.

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