## Problem N cars start at position 0 on a one-lane road and drive at constant speeds. A "passing event" occurs the instant a faster car catches a slower car ahead of it. Count the total number of passing events. ```python def count_passes(speeds: list[int]) -> int: # speeds[i] = speed of car i; cars start at positions 0..N-1 # car i starts ahead of car i+1 (i.e., position i) # returns total number of times a car overtakes the car directly ahead pass ``` **Example:** ``` speeds = [3, 4, 2, 5] # Car 1 (speed 4) passes Car 0 (speed 3) # Car 3 (speed 5) passes Car 2 (speed 2), then Car 1, then Car 0 count_passes([3, 4, 2, 5]) -> 4 ``` ## Follow-ups 1. Is this equivalent to counting inversions? If so, can you solve it in O(n log n) using merge sort? 2. What changes if the road has finite length and cars exit when they reach the end? 3. How would you extend this to return the exact times each passing occurs? 4. What if cars start at distinct initial positions instead of 0, 1, 2, ..., N-1?

InterviewDB Experience

Car Passing: Count the Number of Times Cars Overtake Each Other on a One-Lane Road

phone

Interview Experience

Problem N cars start at position 0 on a one-lane road and drive at constant speeds. A "passing event" occurs the instant a faster car catches a slower car ahead of it. Count the total number of passing events. Example: Follow-ups Is this equivalent to counting inversions? If so, can you solve it in O(n log n) using merge sort? What changes if the road has finite length and cars exit when they reach the end? How would you extend this to return the exact times each passing occurs? What if cars sta…

Full Details

🔒

Unlock all Waymo questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a candidate experience report from a waymo interview during the phone round.

It covers the following topics: Sorting, Coding, Phone .

Topics

Sorting Coding Phone

Car Passing: Count the Number of Times Cars Overtake Each Other on a One-Lane Road

Interview Experience

Full Details

About This Question

Topics

More Waymo Interview Questions