Waymo·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Waymo SWE interview that centered on a classic frequency counting problem, but don't let that fool you. They pushed hard on knowing multiple approaches cold and being able to reason through the tradeoffs on the spot.

Questions Asked (1)

Given an array of elements, count how many times each element appears. Walk through multiple approaches and discuss the complexity and tradeoffs of each.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Started with the hash map solution which is the obvious answer, O(n) time and O(k) space where k is distinct values.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints (e.g., data type, memory limits, whether the array is sorted) and then present multiple approaches, from naive to optimized, discussing time and space complexity for each. Emphasize the tradeoffs between simplicity, performance, and memory usage, and conclude with a recommendation based on typical scenarios.

Pro tip: Mention that for small, bounded integer ranges, a direct-address array can be more efficient than a hash map, but for general elements, a hash map is usually the go-to. Also, note that if the array is sorted, a two-pointer or single-pass counting approach can achieve O(n) time with O(1) extra space.

1. Clarify constraints and assumptions

Ask about the element type (integers, strings, etc.), array size, memory limits, and whether the array is sorted. This determines which approaches are feasible.

2. Present naive approach

For each element, scan the entire array to count occurrences. This is O(n^2) time and O(1) space, but inefficient for large n.

3. Present hash map approach

Use a hash map to store counts. Iterate through the array once, updating counts. This is O(n) time and O(k) space, where k is the number of distinct elements.

4. Present sorting-based approach

Sort the array (O(n log n)) and then count consecutive equal elements in one pass. This uses O(1) extra space if sorting in-place, but modifies the input.

5. Discuss tradeoffs and recommend

Compare time/space complexity, stability, and practical considerations (e.g., hash map overhead, sorting cost). Recommend the hash map for general unsorted data, or sorting if memory is tight and modification is allowed.

Key Points to Mention

Time and space complexity of each approach (naive O(n^2), hash map O(n) time O(k) space, sorting O(n log n) time O(1) space).
Tradeoff between time and space: hash map uses extra memory but is faster; sorting uses less memory but is slower and modifies input.
Handling of edge cases: empty array, all elements same, all distinct.
Choice of data structure: hash map vs. direct-address array for bounded integer ranges.
Stability and order preservation: hash map does not preserve order, but can use LinkedHashMap if needed.
Real-world considerations: hash map overhead, cache performance, and whether the array can be modified.

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