Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jun 2026

Summary

Waymo SWE interview with a math-heavy coding problem that looks straightforward until you remember parabolas aren't monotonic. The two-pointer insight is the whole key and if you don't see it fast you're basically stuck.

Questions Asked (1)

Given a sorted integer array and three coefficients a, b, c, apply the quadratic function f(x) = ax^2 + bx + c to every element and return the results in sorted order.

Algorithms & Data Structures

Author's notes

My first instinct was to just map and sort, which is O(n log n) and they clearly wanted better.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that applying a quadratic to a sorted array produces a sequence that is either monotonic or has a single minimum/maximum, depending on the sign of 'a'. Use a two-pointer technique from both ends of the array, comparing the transformed values and building the result in sorted order in O(n) time.

Pro tip: Clarify edge cases upfront, such as a=0 (linear function) or negative 'a' (maximum instead of minimum), and mention that you can avoid recomputing f(x) by comparing based on the vertex and monotonicity. This shows attention to detail and efficiency.

1. Analyze the function's behavior

Determine the shape of f(x) based on the sign of 'a': if a > 0, it's a parabola opening upwards (minimum); if a < 0, opening downwards (maximum); if a = 0, it's linear. This dictates whether the transformed array will have a minimum or maximum in the middle.

2. Choose the appropriate algorithm

For a ≠ 0, use a two-pointer approach: start with pointers at the beginning and end of the sorted array, compare the transformed values at these pointers, and place the larger (or smaller, depending on 'a') at the end of the result array. For a = 0, simply apply the linear function and the array remains sorted if b > 0, or reverse if b < 0.

3. Implement the two-pointer traversal

Initialize left = 0, right = n-1, and an output array of size n. While left <= right, compute f(arr[left]) and f(arr[right]), compare them, and fill the output from the end to the beginning. Move the pointer that gave the more extreme value inward.

4. Handle edge cases and verify

Test with a = 0, negative 'a', empty array, and single-element array. Ensure the output is correctly sorted and that integer overflow is considered (use long integers if necessary).

Key Points to Mention

Time complexity: O(n) with two pointers, which is optimal since we must process each element.
Space complexity: O(n) for the output array (or O(1) extra if modifying in place, but typically O(n) is acceptable).
Monotonicity of the quadratic function: the derivative f'(x) = 2ax + b is linear, so the function is decreasing then increasing (or vice versa) around the vertex.
Two-pointer technique: leveraging the sorted input to merge from both ends based on the transformed values.
Edge cases: a = 0 (linear), negative 'a' (maximum), empty array, and potential integer overflow.
Alternative approaches: using a priority queue or sorting after transformation (O(n log n)) is less efficient, but worth mentioning as a baseline.

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