← Waymo Interview Insights

Waymo·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Apr 2026

Summary

Waymo SWE interview with a streaming algorithms problem that had a neat follow-up. The core question was more involved than it looked at first glance, and the extension to per-user tracking was a good test of whether you'd actually thought through the data structures.

Questions Asked (2)

Q1

Given a chronologically ordered stream of events where each event has a type and timestamp, define a 'streak' as a maximal run of the same event type where consecutive events are no more than max_gap apart in time. A 'Super Streak' is a streak with at least L events and a total duration of at least D. Count how many Super Streaks exist in the stream, solving it in a single forward pass.

Algorithms & Data Structures
Author's notes

I got the single-pass part right pretty quickly.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the problem constraints and edge cases, then design a single-pass algorithm that tracks the current streak's type, start time, last event time, and count. When the streak breaks (type change or gap > max_gap), check if the completed streak qualifies as a Super Streak and increment the count. Finally, handle the last streak after the loop and analyze time/space complexity.

Pro tip: Explicitly discuss how you handle the final streak after the loop ends, as many candidates forget this and miss counting a valid Super Streak. Also, mention that you would test with edge cases like empty stream, single event, and streaks exactly meeting the thresholds.

1. Clarify requirements and edge cases

Ask about input format, constraints (e.g., max_gap, L, D), and edge cases such as empty stream, single event, or streaks exactly meeting thresholds. Confirm that timestamps are non-decreasing and that duration is inclusive.

2. Define streak tracking variables

Initialize variables for current streak type, start time, last event time, and event count. Also initialize a counter for Super Streaks.

3. Iterate through events in one pass

For each event, check if it continues the current streak (same type and gap <= max_gap). If yes, update last time and count; if no, evaluate the completed streak and reset variables for the new streak.

4. Evaluate streak completion and count Super Streaks

When a streak ends, check if its count >= L and duration >= D. If so, increment the Super Streak counter. After the loop, evaluate the final streak similarly.

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 edge cases.

Key Points to Mention

  • Single-pass O(n) time and O(1) space complexity.
  • Handling streak breaks due to type change or gap > max_gap.
  • Evaluating the final streak after the loop ends.
  • Using inclusive duration (last_time - start_time >= D).
  • Edge cases: empty stream, single event, streaks exactly meeting L and D.
  • Clarifying that timestamps are non-decreasing and events are chronologically ordered.

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 carries a user_id. Extend your solution to count Super Streaks per user.

Algorithms & Data StructuresSystem Design
Author's notes

Pretty much immediate once you see it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Extend the existing solution by partitioning events by user_id and computing Super Streaks independently for each user. Use a hash map to group events per user, then apply the same streak-counting logic to each user's sorted event list. Return a mapping from user_id to their Super Streak count.

Pro tip: Clarify the definition of a Super Streak (e.g., consecutive events within a time window) and confirm whether events are sorted; if not, sort them per user. Also discuss trade-offs between processing all users in one pass versus per-user batches for scalability.

1. Clarify requirements and assumptions

Confirm the definition of a Super Streak, the event schema (timestamp, user_id), and whether events are sorted. Ask about expected data size and distribution of users.

2. Group events by user_id

Use a hash map to bucket events by user_id. If events are not sorted, sort each user's events by timestamp.

3. Compute Super Streaks per user

For each user, apply the existing streak-counting algorithm (e.g., sliding window or two-pointer) to count Super Streaks. Store results in a map keyed by user_id.

4. Optimize for scale and discuss trade-offs

Consider memory and time complexity. For large datasets, discuss streaming or batch processing per user, and whether to use distributed processing (e.g., MapReduce) if needed.

5. Test and validate

Walk through edge cases: users with no events, single event, multiple streaks, and events out of order. Verify correctness with small examples.

Key Points to Mention

  • Hash map for grouping events by user_id
  • Sorting events per user if not already sorted
  • Reusing the existing streak-counting logic per user
  • Time and space complexity analysis (e.g., O(N log N) due to sorting)
  • Handling edge cases: empty users, single event, non-consecutive events
  • Scalability considerations for large numbers of users or events

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