Katkat
Back

Design a Ride Scheduler

WaymoSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

This problem tests your ability to design a robust scheduling system that handles dynamic task insertion, state transitions, and time-based prioritization using object-oriented principles.

Problem Statement

Design a Ride Scheduler system for an autonomous vehicle fleet. The scheduler must manage ride requests that occur at specific timestamps and ensure vehicles are assigned to them efficiently.

Your task is to design a RideScheduler class that supports the following operations:

  1. add_ride(ride_id, pickup_time, location): Registers a new ride request.
  2. cancel_ride(ride_id): Removes a pending request. If the ride is already in progress or completed, ignore the request.
  3. process_events(current_time): Updates the system state up to the provided timestamp, triggering any rides that are due or overdue.
  4. get_pending_rides(): Returns a list of ride IDs that are scheduled but not yet started, sorted by pickup_time.

Constraints

  • pickup_time is a non-negative integer representing seconds from a start epoch.
  • The system should efficiently handle thousands of ride requests.
  • Assume process_events can be called with a time smaller than the previous call (time-skipping).

Example

# Initialization
scheduler = RideScheduler()

# Adding rides
scheduler.add_ride("ride_1", 100, "Point A")
scheduler.add_ride("ride_2", 50, "Point B")

# Pending rides should be sorted by time
# get_pending_rides() -> ["ride_2", "ride_1"]

# Processing events up to time 75
scheduler.process_events(75)
# "ride_2" is processed, "ride_1" remains pending.

Edge Cases

  • Multiple rides scheduled for the exact same pickup_time.
  • Canceling a ride that is currently being processed.
  • Large time jumps in process_events.

Hints

Hint 1

Consider using a min-priority queue (min-heap) to keep pending rides sorted by their pickup time.

Hint 2

Use a hash map to maintain a mapping from ride_id to its metadata, allowing for O(1) lookups and cancellations.

Hint 3

To handle cancellations in a priority queue, you might use a 'lazy removal' strategy where you flag the ride as cancelled rather than removing it from the heap immediately.

Follow-up questions

  • How would you modify this system to support ride priorities (e.g., VIP vs. Standard) instead of just time-based scheduling?
  • If the scheduler needs to be thread-safe for concurrent ride additions and cancellations, which synchronization primitives would you use and where?
  • How would you persist this state so that if the service crashes, the schedule is recovered correctly?