262. Trips and Users
- Database
TIME
O(n log n) for the grouping (O(n) with hash joins and hash aggregation)
SPACE
O(n)
Intuition
A trip counts only if both its client and its driver are unbanned. That is two lookups into the same Users table, so join it twice under different aliases, once on client_id and once on driver_id, with banned = 'No' in each join condition. Inner joins drop every trip that fails either check, and what remains is exactly the set of requests the rate is defined over.
After that it is a per-day average. In MySQL a comparison evaluates to 1 or 0, so AVG(status <> 'completed') is the number of cancelled trips divided by the number of trips that day. There is no need for two COUNTs and a division.
Approach
- Join
TripstoUsers AS conc.users_id = client_id AND c.banned = 'No'. - Join to
Users AS dond.users_id = driver_id AND d.banned = 'No'. - Keep
request_at BETWEEN '2013-10-01' AND '2013-10-03'. The dates areYYYY-MM-DDstrings, so string comparison matches date order. GROUP BY request_atand selectROUND(AVG(status <> 'completed'), 2)as`Cancellation Rate`.
Complexity
- Time: O(n log n) for the grouping (O(n) with hash joins and hash aggregation)
- Space: O(n)
Edge Cases
- A banned driver excludes the trip just like a banned client; the example only shows banned clients
- Both cancellation statuses count:
status <> 'completed'coverscancelled_by_driverandcancelled_by_client - A day whose trips all involve a banned user has no rows after the joins, so it does not appear in the output (not as
0.00) - A day with no cancellations shows
0.00, not a missing row - Days outside
2013-10-01to2013-10-03are ignored even if they have trips - The output column name contains a space, so it needs backticks in MySQL
Code
-- 262. Trips and Users
-- Time: O(n log n) for the grouping (O(n) with hash joins and hash aggregation)
-- Space: O(n)
SELECT
t.request_at AS Day,
-- the comparison is 1 for a cancelled trip and 0 for a completed one, so
-- its average is cancelled / total for the day
ROUND(AVG(t.status <> 'completed'), 2) AS `Cancellation Rate`
FROM Trips AS t
-- both joins are inner, so a trip with either side banned drops out here
JOIN Users AS c
ON c.users_id = t.client_id AND c.banned = 'No'
JOIN Users AS d
ON d.users_id = t.driver_id AND d.banned = 'No'
WHERE t.request_at BETWEEN '2013-10-01' AND '2013-10-03'
GROUP BY t.request_at;