← Waymo Interview InsightsSoftware Engineer

Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Waymo software engineer interview with a coding problem that looks simple on the surface but bites you if you forget about the negative coefficient case. The two-pointer insight is the whole game here.

Questions Asked (1)

Q1

Given a sorted integer array and three coefficients a, b, c, apply the quadratic function f(x) = a*x^2 + b*x + 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

Use a two-pointer approach from both ends of the sorted array, comparing the transformed values and placing the larger one at the end of the result array. This works because the quadratic function is monotonic on either side of its vertex, so the extremes of the input array produce the extremes of the output.

Pro tip: Clarify edge cases upfront, such as when a is zero (linear function) or negative (parabola opens downward), and mention that the two-pointer method runs in O(n) time and O(n) space, which is optimal.

1. Understand the problem and edge cases

Restate the problem to ensure clarity. Identify special cases: a=0 (linear), a>0 (upward parabola), a<0 (downward parabola), and empty array.

2. Choose the right algorithm

Explain that a two-pointer approach is optimal because the input is sorted and the quadratic function is monotonic on each side of its vertex.

3. Walk through the two-pointer process

Initialize left and right pointers at the ends of the array and an output array of the same size. Compare f(nums[left]) and f(nums[right]), place the larger value at the end of the output, and move the corresponding pointer inward.

4. Analyze complexity and test

State that time complexity is O(n) and space complexity is O(n). Test with examples like a=1, b=0, c=0 on [-3,-2,-1,0,1,2,3] and edge cases like a=0 or a<0.

Key Points to Mention

  • The quadratic function is not monotonic over the entire real line; it decreases then increases (or vice versa) depending on the sign of a.
  • The two-pointer technique leverages the sorted input to achieve O(n) time, which is better than transforming and sorting (O(n log n)).
  • Handle the case when a=0 separately: the function becomes linear, and the result is already sorted if b>0 or reversed if b<0.
  • For a<0, the parabola opens downward, so the maximum values are at the extremes, and the two-pointer approach still works by placing larger values at the end.
  • The vertex of the parabola is at x = -b/(2a), which can be used to reason about monotonicity, but the two-pointer method does not require computing it.
  • Always consider integer overflow when computing a*x^2 + b*x + c, especially for large inputs.

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