Uber: Back-to-Back Trips Starting in the Last Drop Zone

Medium
990.

Uber: Back-to-Back Trips Starting in the Last Drop Zone

Dispatch tries to give a driver their next trip close to where the last one ended, cutting the empty kilometres. The marketplace team measures how often that works.

Take each driver's trips in order of pickup_at. A trip is chained when the driver's previous trip dropped off in the zone where this trip picks up, and this pickup came at most 15 minutes (900 seconds) after that drop-off. A driver's first trip is never chained. For every driver return driver_id, trips and chained_trips, ordered by chained_trips descending, then driver_id.

A practice scenario set at Uber: the tables and data are invented, and this is not a question from, or endorsed by, Uber.

Tables

Table: DriverTrip

ColumnType
trip_idint
driver_idint
pickup_zonevarchar
drop_zonevarchar
pickup_atdatetime
dropoff_atdatetime

Primary key: trip_id.

One row per completed trip. A driver's trips never overlap, so no two of them share a pickup_at.

Example

The rows must come back in the order shown.

DriverTrip

trip_iddriver_idpickup_zonedrop_zonepickup_atdropoff_at
11KoramangalaIndiranagar2024-09-05 08:00:002024-09-05 08:25:00
21IndiranagarMG Road2024-09-05 08:35:002024-09-05 08:55:00
31MG RoadWhitefield2024-09-05 09:10:002024-09-05 09:50:00
41HSR LayoutKoramangala2024-09-05 10:00:002024-09-05 10:20:00
52AirportWhitefield2024-09-05 06:00:002024-09-05 06:50:00
62WhitefieldAirport2024-09-05 07:06:002024-09-05 07:50:00
73MG RoadHSR Layout2024-09-05 11:00:002024-09-05 11:30:00

Output

driver_idtripschained_trips
142
220
310
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

Uber: Back-to-Back Trips Starting in the Last Drop Zone

Dispatch tries to give a driver their next trip close to where the last one ended, cutting the empty kilometres.

  • Difficulty: Medium
  • Topics: Window Functions, Dates, Conditional Logic
  • Dialect: MySQL
  • Problem: #990

Problem statement

Dispatch tries to give a driver their next trip close to where the last one ended, cutting the empty kilometres. The marketplace team measures how often that works.

Take each driver's trips in order of pickup_at. A trip is chained when the driver's previous trip dropped off in the zone where this trip picks up, and this pickup came at most 15 minutes (900 seconds) after that drop-off. A driver's first trip is never chained. For every driver return driver_id, trips and chained_trips, ordered by chained_trips descending, then driver_id.

A practice scenario set at Uber: the tables and data are invented, and this is not a question from, or endorsed by, Uber.

Tables

Table: DriverTrip

ColumnType
trip_idint
driver_idint
pickup_zonevarchar
drop_zonevarchar
pickup_atdatetime
dropoff_atdatetime

Primary key: trip_id.

One row per completed trip. A driver's trips never overlap, so no two of them share a pickup_at.

Examples

Example 1

DriverTrip

trip_iddriver_idpickup_zonedrop_zonepickup_atdropoff_at
11KoramangalaIndiranagar2024-09-05 08:00:002024-09-05 08:25:00
21IndiranagarMG Road2024-09-05 08:35:002024-09-05 08:55:00
31MG RoadWhitefield2024-09-05 09:10:002024-09-05 09:50:00
41HSR LayoutKoramangala2024-09-05 10:00:002024-09-05 10:20:00
52AirportWhitefield2024-09-05 06:00:002024-09-05 06:50:00
62WhitefieldAirport2024-09-05 07:06:002024-09-05 07:50:00
73MG RoadHSR Layout2024-09-05 11:00:002024-09-05 11:30:00

Output

driver_idtripschained_trips
142
220
310

How to solve Uber: Back-to-Back Trips Starting in the Last Drop Zone

The rule compares each trip with the previous trip of the same driver, which is what LAG is for. Partitioned by driver and ordered by pickup_at, LAG(drop_zone) and LAG(dropoff_at) put the last trip's end zone and end time on the current row.

A trip is chained when both conditions hold: its pickup zone equals the previous drop zone, and TIMESTAMPDIFF(SECOND, prev_dropoff_at, pickup_at) is at most 900. The bound is inclusive, so trip 3 — picked up exactly 15 minutes after trip 2 dropped off at MG Road — is chained, while driver 2's second trip, 16 minutes later, is not. Trip 4 is quick but starts in another zone. On a first trip both LAG values are NULL, the comparisons are unknown, and the CASE falls to 0; the trip still counts in COUNT(*).

The alternative finds the previous trip without window functions: a self join on earlier trips of the same driver, with NOT EXISTS ruling out any trip in between, plus the zone and time conditions in the ON clause; COUNT(p.trip_id) then counts the trips that found a chaining predecessor. The window version is one sort per driver; the join version is quadratic, which is why LAG is the tool of choice here.

Reference solution (MySQL)

WITH seq AS (
  SELECT driver_id, pickup_zone, pickup_at,
         LAG(drop_zone) OVER (PARTITION BY driver_id ORDER BY pickup_at) AS prev_drop_zone,
         LAG(dropoff_at) OVER (PARTITION BY driver_id ORDER BY pickup_at) AS prev_dropoff_at
  FROM DriverTrip
)
SELECT driver_id, COUNT(*) AS trips,
       SUM(CASE WHEN pickup_zone = prev_drop_zone
                 AND TIMESTAMPDIFF(SECOND, prev_dropoff_at, pickup_at) <= 900 THEN 1 ELSE 0 END) AS chained_trips
FROM seq
GROUP BY driver_id
ORDER BY chained_trips DESC, driver_id

Another way

SELECT t.driver_id, COUNT(*) AS trips, COUNT(p.trip_id) AS chained_trips
FROM DriverTrip t
LEFT JOIN DriverTrip p
  ON p.driver_id = t.driver_id
 AND p.pickup_at < t.pickup_at
 AND NOT EXISTS (SELECT 1 FROM DriverTrip m WHERE m.driver_id = t.driver_id AND m.pickup_at > p.pickup_at AND m.pickup_at < t.pickup_at)
 AND p.drop_zone = t.pickup_zone
 AND t.pickup_at <= DATE_ADD(p.dropoff_at, INTERVAL 15 MINUTE)
GROUP BY t.driver_id
ORDER BY chained_trips DESC, t.driver_id

← Uber: UberX Share Requests Matched With a Co-Rider · Uber: Fleet Vehicles on Two Drivers' Shifts at Once →