The Disputed Fare

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
mid
Asked in
Lyft

Problem

A disputed charge on our books was assembled from two separate ride legs, and when several pairs of legs could explain the total we credit the pair whose second leg was billed earliest. Given fares, the leg charges in billing order, and the disputed target, return the positions of those two legs, or None if no two legs add up to it.

One charge, two legs. Finance needs to know which two.

Example 1

Input:

fares = [500,1200,800,300], target = 1100

Output:

[2,3]

Example 2

Input:

fares = [300,300,500], target = 800

Output:

[0,2]

Worked solution and explanation

Why this problem exists in real interviews

This is Two Sum wearing a fare-reconciliation badge. The real question: can you find the pair that sums to target in a single pass instead of testing every leg against every other? Anyone can write the double loop; it just quietly becomes O(n^2) on a driver's multi-year billing history. The move that separates candidates is recording each fare's index in a dict as you scan, so the instant you meet a leg whose complement (target - fare) is already on file, you have both positions in O(1). Reach for sorting plus two pointers instead and you throw away the very indices finance asked for.

Break down the requirements

Step 1: Remember each fare's first position

Walk fares once with enumerate and store fare value to its index in a dict. Keep the FIRST index you saw for a value: that is what makes the earlier leg come first and keeps duplicate charges from clobbering each other.

Step 2: Look for the complement BEFORE inserting

For each leg, compute complement = target - fare and check whether it is already in the dict. Checking before you insert the current fare is what stops a single leg from pairing with itself when target is exactly twice that fare.

Step 3: Return on the first hit, None at the end

The first j whose complement is on file is by construction the earliest-completing pair, so return [seen[complement], j] immediately. If the scan finishes with no hit, no two legs account for the total, so return None.

The solution

One pass, value-to-index dict
def find_fare_pair(fares, target):
    seen = {}
    for j, fare in enumerate(fares):
        complement = target - fare
        if complement in seen:
            return [seen[complement], j]
        if fare not in seen:
            seen[fare] = j
    return None
Nested loop (rejected)
Two loops over the legs, O(n^2). Correct on the toy input, but a driver with tens of thousands of billed legs turns this into a visible latency spike, and it still has to be careful to report the earlier index first.
Hash lookup (shipped)
Single pass, O(n). The dict answers 'have I already seen the complement, and where?' in O(1), and because you scan left to right the first match is automatically the earliest-completing pair.

Common follow-up questions