# What the Card Remembers > A hold on your money is never a single moment. Rebuild the windows it actually lived in. Canonical URL: Domain: Python · Difficulty: medium · Seniority: mid ## 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. ## 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. > **Trick to solving** > > Group first, sort within each group by start, then sweep keeping a running window. Extend it when the next start is within the running end, and always extend to max(running_end, next_end), never just next_end. That one max is the whole problem. --- ### 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** ```python 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 ``` > **Complexity** > > Let n be the number of holds and g the holds on the busiest card. Grouping is O(n). Each card's sort is O(g log g), and the sweep is linear, so the whole thing is O(n log n) time and O(n) space for the grouped tuples and the output. On a day's worth of authorizations per card, that is trivially fast; the cost is the sort, not the sweep. > **Common pitfall** > > Writing merged[-1][1] = end instead of max(merged[-1][1], end). It looks right on the visible examples because each later hold happens to end further out. It breaks the instant a hold is contained inside the previous one: [0, 100] then [10, 20] collapses to [0, 20], silently reporting the money as released 80 minutes early. The hidden contained-interval case exists precisely to catch this. > **Interviewers watch for** > > Whether you partition by card before sorting (a global sort is the tell that you missed the grouping), whether you reach for max on the running end, and whether you decide out loud whether touching holds (end == next start) merge. Stating that assumption before coding signals you read overlap as a range relation, not a set of equal values. **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 - The holds now arrive as an unbounded stream and you cannot hold a full card's history in memory. How do you emit merged windows? _(Tests whether the candidate can keep only the open window per card and flush it once a hold starts strictly after the running end, trading the global sort for an assumption of near-ordered arrival.)_ - Each hold also carries an amount. Report the total dollars held during each merged window. _(Tests carrying an aggregate through the sweep and reasoning about whether overlapping amounts stack or the window represents a single held sum.)_ - How would you run this across billions of holds in a distributed job? _(Tests partitioning by card as the shuffle key so each reducer merges one card independently, mirroring the grouping step here.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/authorization-hold-windows) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.