Trip Booking with the Earliest Free Driver
Updated
Problem statement
A travel company books trips for its drivers. Each driver is paid an hourly rate. Times are whole hours. Build a booking system that starts with no drivers and no trips, and supports four calls:
addDriver(hourlyRate): add a driver. Drivers get ids0, 1, 2, ...in the order they are added. Return the new driver's id.bookTrip(start, end): a customer asks for a trip from hourstartto hourend. A driver is free for it if every trip they already drive ends at or beforestart. Give the trip to the free driver who has been free the longest, that is, whose last trip ended earliest. A driver who has never driven counts as free since hour0. If two free drivers have been free since the same hour, pick the smaller id. Return the trip's cost, which is the driver'shourlyRate × (end - start). If no driver is free, the trip is not booked: return-1.getTotalCost(): return the total cost of all trips booked so far.getMinDrivers(time): return the fewest drivers needed to drive every trip asked for so far that is running at hourtime. Count everybookTriprequest so far, booked or not, withstart <= time < end. A trip that ends at hourtimeis not running then.
You get the calls in order: operations[i] is the call's name and args[i] holds its numbers. Return an array with one value per call, in order.
Function
runTripBookings(operations: String[], args: int[][]) → long[]Examples
Example 1
operations = ["addDriver","addDriver","bookTrip","bookTrip","bookTrip","getTotalCost","getMinDrivers"]args = [[30],[20],[1,4],[2,5],[4,6],[],[4]]return = [0,1,90,60,60,210,2]Driver 0 costs 30 per hour and driver 1 costs 20. Both are free at hour 1; neither has driven, so the smaller id, driver 0, takes trip [1, 4] for 30 × 3 = 90. At hour 2 only driver 1 is free: 20 × 3 = 60. At hour 4 driver 0 is free again (its trip ended at 4) and costs 30 × 2 = 60. The total is 210. At hour 4 the trips [2, 5] and [4, 6] are running, so 2 drivers are needed.
Example 2
operations = ["addDriver","addDriver","bookTrip","bookTrip","bookTrip","bookTrip","getTotalCost"]args = [[10],[50],[0,2],[0,1],[3,4],[3,5],[]]return = [0,1,20,50,50,20,140]Driver 0 drives [0, 2] (cost 20) and driver 1 drives [0, 1] (cost 50). At hour 3 both are free. Driver 1 has been free since hour 1 and driver 0 since hour 2, so driver 1 takes [3, 4] (cost 50), even though driver 0 is cheaper. Then driver 0 takes [3, 5] (cost 20). The total is 140.
Example 3
operations = ["addDriver","bookTrip","bookTrip","getMinDrivers","getMinDrivers","getTotalCost"]args = [[7],[5,9],[6,8],[6],[9],[]]return = [0,28,-1,2,0,28]Driver 0 takes [5, 9] for 7 × 4 = 28. At hour 6 it is still busy, so [6, 8] cannot be booked: -1. Two trips were asked for at hour 6, so 2 drivers would be needed then. At hour 9 the first trip has just ended: 0. The total stays 28.
Constraints
1 <= operations.length <= 2000andargs.length == operations.length- Each
operations[i]is"addDriver","bookTrip","getTotalCost"or"getMinDrivers", andargs[i]holds[hourlyRate],[start, end],[]or[time]to match. - Every number in
argsis between0and10^6. 1 <= hourlyRate <= 10^4andstart < end- The
starthours of thebookTripcalls never go down from one call to the next.
More Rippling Onsite Interview questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Delivery Cost TrackerPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Maximum Currency Conversion Along a Simple PathPHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Top K Frequent WordsPHONE SCREEN · ONSITE INTERVIEW · Seen Aug 2026
- Future-Effective Employee SalaryONSITE INTERVIEW · Seen Aug 2026
- Filter and Sort Scheduled TasksONSITE INTERVIEW · Seen Jul 2026
Similar questions at other companies
- Design Authentication ManagerOracle · ONSITE INTERVIEWOracle interview questions
- Delayed Job SchedulerWalmart Labs · ONSITE INTERVIEW
- Thread-Safe Task Storage and Worker DispatchNuro · ONSITE INTERVIEWNuro interview questions
- Notification Deduplication WindowGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Implement a Min-Priority QueueAmazon · ONSITE INTERVIEW
- Helpdesk Ticket ProcessingThe Walt Disney Company · ONSITE INTERVIEWThe Walt Disney Company interview questions
- Execute Tasks by PrioritySnowflake · ONSITE INTERVIEWSnowflake interview questions
- Key-Value Store with Hit CounterDatabricks · ONSITE INTERVIEWDatabricks interview questions
- Priority Job Scheduler with CooldownsGoogle · ONSITE INTERVIEWGoogle interview questions
- Reusable Number AllocatorDropbox · ONSITE INTERVIEWDropbox interview questions