What the Card Remembers

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
Capital One

Problem

A card-authorization service records temporary holds as [start, end] minute offsets, and a single card can accumulate many holds that pile onto each other over a busy day. For each card, collapse the holds that overlap or touch into the continuous windows the money was actually held, earliest first.

A hold on your money is never a single moment. Rebuild the windows it actually lived in.

Example 1

Input:

holds = [{"end":30,"card":"visa","start":0},{"end":40,"card":"visa","start":20},{"end":10,"card":"amex","start":5},{"end":70,"card":"visa","start":60},{"end":25,"card":"amex","start":10}]

Output:

{"amex":[[5,25]],"visa":[[0,40],[60,70]]}

Example 2

Input:

holds = [{"end":55,"card":"visa","start":50},{"end":20,"card":"visa","start":10}]

Output:

{"visa":[[10,20],[50,55]]}

Worked solution and explanation

Why this problem exists in real interviews

This is interval merging wearing a payments costume. The real skill being probed: can you group records by a key, then collapse overlapping or touching ranges within each group in a single sorted sweep? Anyone can write the grouping dict. Two things separate candidates. First, holds arrive out of order, so a sweep in input order splits overlaps that a sort would have joined. Second, and the one that quietly fails: when a hold is fully contained inside the one before it, the running end must stay at the larger value. Take the new hold's end instead and a five-minute hold sitting inside a hundred-minute hold shrinks the window to five minutes.

Break down the requirements

Step 1: Partition holds by card before anything else

A global sort across all holds fuses windows from different cards the moment their offsets overlap. Build a dict from card to its list of (start, end) tuples with setdefault, so each card is merged in isolation. The grouping is the difference between one card's story and everyone's stories smeared together.

Step 2: Sort each card's holds by start

Overlapping holds can appear in any order in the input (see the visa example, where 50-55 is listed before 10-20). Sorting tuples orders by start, then end, which is exactly the sweep order you need. Skip the sort and two overlapping holds that arrive far apart stay separate.

Step 3: Sweep and extend, taking the max end

Walk the sorted holds. If the current hold's start is within (less than or equal to) the last merged window's end, they belong to one continuous window, so widen that window's end to max(existing_end, current_end). Using <= rather than < means a hold ending at 10 and one starting at 10 merge, which matches a continuous hold with no gap. Otherwise, open a new window.

The solution

Group, sort, sweep
def merge_holds(holds):
    by_card = {}
    for hold in holds:
        by_card.setdefault(hold["card"], []).append((hold["start"], hold["end"]))

    result = {}
    for card, windows in by_card.items():
        windows.sort()
        merged = []
        for start, end in windows:
            if merged and start <= merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
        result[card] = merged
    return result
Naive: sweep in input order
Iterate holds as given and compare each to the last window. Two overlapping holds listed far apart never meet, so one continuous hold is reported as two. On the visa example this splits 10-20 and 50-55 correctly by luck but mangles any interleaved overlap.
Correct: sort within group, then sweep
Group by card, sort each group by start so overlaps become adjacent, then a single linear sweep with a max-extended end collapses them exactly once. Deterministic and order-independent of the input.

Common follow-up questions