← Waymo Interview InsightsSoftware Engineer

Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Waymo SWE interview with a streaming algorithms problem that had a neat follow-up. The core question was well-designed and pushed into some practical engineering territory with the per-user extension.

Questions Asked (2)

Q1

You're given a chronologically ordered stream of events, each with a type and timestamp. A 'streak' is a maximal run of the same event type where consecutive events are no more than max_gap apart in time. A 'Super Streak' is any streak with at least L events and a total duration of at least D. Count the number of Super Streaks using a single forward pass.

Algorithms & Data Structures
Author's notes

The single-pass constraint is what makes this interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the definitions of streak, max_gap, L, and D, then design a single-pass algorithm that tracks the current streak's type, start time, last event time, and count. When the streak breaks, check if it qualifies as a Super Streak and increment a counter, then reset for the new streak.

Pro tip: Emphasize that the stream is chronologically ordered, so you can process events in one pass without storing the entire stream; also discuss edge cases like gaps exactly equal to max_gap and streaks that end at the stream's end.

1. Clarify requirements and edge cases

Ask clarifying questions to confirm definitions: max_gap is inclusive, duration is last_timestamp - first_timestamp, and a streak must have at least L events and duration >= D. Discuss edge cases like empty stream, single event, and gaps exactly equal to max_gap.

2. Initialize state variables

Set up variables to track the current streak: current_type, start_time, last_time, and count. Initialize a super_streak_count to 0.

3. Process each event in a single pass

For each event, check if it continues the current streak (same type and time gap <= max_gap). If yes, update last_time and count. If no, finalize the current streak (check if it's a Super Streak) and start a new streak with the current event.

4. Finalize the last streak

After the loop, check the last streak for Super Streak qualification and update the count if needed.

5. Analyze complexity and test

State that the algorithm runs in O(n) time and O(1) space. Walk through a small example to verify correctness, including cases where streaks break and qualify.

Key Points to Mention

  • Single forward pass with O(1) extra space, leveraging chronological order.
  • Inclusive comparison for max_gap (gap <= max_gap).
  • Duration calculation as last_timestamp - first_timestamp.
  • Handling streak breaks: finalize and reset state.
  • Edge cases: empty stream, single event, streak at end of stream.
  • Time and space complexity analysis.

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

Q2

Follow-up: each event now also has a user_id. How do you count Super Streaks per user?

Algorithms & Data StructuresSystem Design
Author's notes

Pretty natural extension once you've solved the base problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify the definition of a Super Streak and the data format (e.g., event stream vs. stored events). Then, propose an algorithm that groups events by user_id and computes the streak per user, discussing time/space complexity and potential optimizations for large-scale data.

Pro tip: Mention that in a real system like Waymo, you'd likely process this as a streaming problem with windowing and state management, and consider using a distributed framework like Flink or Spark Streaming for scalability.

1. Clarify requirements

Ask clarifying questions about the definition of a Super Streak (e.g., consecutive events within a time window, specific event types) and the expected data volume and latency requirements.

2. Choose data structures

Decide on appropriate data structures: a hash map to group events by user_id, and for each user, a list or sorted structure to track event timestamps for streak calculation.

3. Design algorithm

Outline an algorithm: iterate through events, group by user_id, sort each user's events by time, then scan to count consecutive events that satisfy the streak condition. Discuss time complexity (O(N log N) due to sorting) and possible optimizations (e.g., if events are already sorted).

4. Handle scale and distribution

If data is large, propose partitioning by user_id and processing in parallel, or using a streaming approach with windowed aggregations. Mention trade-offs between batch and stream processing.

5. Test and validate

Suggest edge cases to test: users with no events, single event, events out of order, and streaks that span across time boundaries. Discuss how to verify correctness.

Key Points to Mention

  • Definition of Super Streak: consecutive events within a time threshold (e.g., within 1 hour) or consecutive days with activity.
  • Grouping by user_id using a hash map for O(1) average access.
  • Sorting events per user by timestamp to identify consecutive sequences.
  • Time complexity: O(N log N) for sorting, O(N) for scanning; space complexity O(N) for storing grouped events.
  • Scalability: partitioning by user_id, parallel processing, or streaming with windowing.
  • Edge cases: empty input, single event, out-of-order events, and streaks crossing time boundaries.

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