Uber: Split Fare Shares to the Paisa — SQL Problem
With Split Fare, a rider invites friends to share a trip's cost.
- Difficulty: Hard
- Topics: Window Functions, Conditional Logic, Strings
- Dialect: MySQL
- Problem: #994
Problem statement
With Split Fare, a rider invites friends to share a trip's cost. Payments must add up to the fare exactly, so the amount is shared out in paise (1 rupee = 100 paise): each of the n riders who accepted pays fare_paise DIV n, and the remaining fare_paise MOD n paise are charged one each to the riders who accepted first (earliest responded_at; on a tie, the smaller rider_id goes first). Riders who declined or never answered pay nothing.
Return trip_id, rider_id, share_paise and share_rupees — the share written as rupees with exactly two decimals, such as '83.34' or '45.00' — for every rider who accepted, ordered by trip_id, then rider_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: FareSplit
| Column | Type |
|---|---|
| trip_id | int |
| fare_paise | int |
Primary key: trip_id.
One row per trip whose fare is being split, with the final fare in paise.
Table: SplitMember
| Column | Type |
|---|---|
| trip_id | int |
| rider_id | int |
| status | enum(accepted, declined, pending) |
| responded_at | datetime |
Primary key: trip_id, rider_id.
One row per rider in a split, including the rider who started it (always accepted). trip_id always names a row of FareSplit.
Examples
Example 1
FareSplit
| trip_id | fare_paise |
|---|---|
| 1 | 25001 |
| 2 | 10001 |
| 3 | 4500 |
| 4 | 8000 |
SplitMember
| trip_id | rider_id | status | responded_at |
|---|---|---|---|
| 1 | 11 | accepted | 2024-09-20 10:00:00 |
| 1 | 13 | accepted | 2024-09-20 10:01:00 |
| 1 | 12 | accepted | 2024-09-20 10:01:00 |
| 2 | 21 | accepted | 2024-09-20 11:00:00 |
| 2 | 22 | declined | 2024-09-20 10:59:00 |
| 2 | 23 | accepted | 2024-09-20 11:02:00 |
| 2 | 24 | pending | 2024-09-20 11:03:00 |
| 3 | 31 | accepted | 2024-09-20 12:00:00 |
| 4 | 41 | declined | 2024-09-20 13:00:00 |
Output
| trip_id | rider_id | share_paise | share_rupees |
|---|---|---|---|
| 1 | 11 | 8334 | 83.34 |
| 1 | 12 | 8334 | 83.34 |
| 1 | 13 | 8333 | 83.33 |
| 2 | 21 | 5001 | 50.01 |
| 2 | 23 | 5000 | 50.00 |
| 3 | 31 | 4500 | 45.00 |
How to solve Uber: Split Fare Shares to the Paisa
Splitting money exactly is a classic largest-remainder problem: divide in the smallest unit, then hand out the leftover units one at a time in a fixed order. Here the unit is the paisa and the order is acceptance time with rider_id as the tie-breaker, which makes every result deterministic.
The first CTE keeps accepted riders only and attaches two window values per row: seat, the rider's position in acceptance order within the trip, and riders, the number of accepted riders. Each share is then fare_paise DIV riders, plus one paisa when seat <= fare_paise MOD riders. Because the remainder is smaller than the number of riders, exactly the remainder's worth of riders get the extra paisa, and the shares add back to the fare. On trip 1, 25,001 paise among three riders leaves 2 paise: rider 11 accepted first, and of the tied riders 12 and 13 the smaller id takes the second paisa.
Formatting stays in integers too: share_paise DIV 100 is the rupee part and LPAD(share_paise MOD 100, 2, '0') the paise, so 4,500 becomes 45.00 without any floating-point rounding. Trip 4, where nobody accepted, produces no rows.
The alternative computes the seat with a correlated count of riders who accepted earlier (or at the same moment with a smaller id) and the rider count with a grouped derived table, using FLOOR, MOD and RIGHT for the same arithmetic.
Reference solution (MySQL)
WITH accepted AS (
SELECT m.trip_id, m.rider_id, f.fare_paise,
ROW_NUMBER() OVER (PARTITION BY m.trip_id ORDER BY m.responded_at, m.rider_id) AS seat,
COUNT(*) OVER (PARTITION BY m.trip_id) AS riders
FROM SplitMember m
JOIN FareSplit f ON f.trip_id = m.trip_id
WHERE m.status = 'accepted'
), shares AS (
SELECT trip_id, rider_id,
fare_paise DIV riders + CASE WHEN seat <= fare_paise MOD riders THEN 1 ELSE 0 END AS share_paise
FROM accepted
)
SELECT trip_id, rider_id, share_paise,
CONCAT(share_paise DIV 100, '.', LPAD(share_paise MOD 100, 2, '0')) AS share_rupees
FROM shares
ORDER BY trip_id, rider_idAnother way
SELECT trip_id, rider_id, share_paise,
CONCAT(FLOOR(share_paise / 100), '.', RIGHT(CONCAT('0', MOD(share_paise, 100)), 2)) AS share_rupees
FROM (
SELECT m.trip_id, m.rider_id,
FLOOR(f.fare_paise / c.n) + IF(
1 + (SELECT COUNT(*) FROM SplitMember e
WHERE e.trip_id = m.trip_id AND e.status = 'accepted'
AND (e.responded_at < m.responded_at OR (e.responded_at = m.responded_at AND e.rider_id < m.rider_id)))
<= MOD(f.fare_paise, c.n), 1, 0) AS share_paise
FROM SplitMember m
JOIN FareSplit f ON f.trip_id = m.trip_id
JOIN (SELECT trip_id, COUNT(*) AS n FROM SplitMember WHERE status = 'accepted' GROUP BY trip_id) c ON c.trip_id = m.trip_id
WHERE m.status = 'accepted'
) s
ORDER BY trip_id, rider_id← Uber: Longest Surge Episode in Each Zone · Uber: Freight Lane Rates Spiking Over the 28-Day Average →