skip to content

At a shuttle stop where riders both alight and board, which delta event must the sweep process first?

level: middleimportance: must knowfreq 58%

answer

  1. the count only changes at boundaries
  2. two events share one coordinate
  3. does touching at a point mean overlapping?
  4. half-open versus closed flips the answer
  5. put the rule in the sort key

basics

~20 s

Process the alighting event first. Riders leaving at that stop free their seats before riders boarding there take them, so applying the negative delta before the positive one is what stops the running count from reporting a phantom overflow.

solid answer

~50 s

Ties on the same coordinate are decided by the interval semantics, not by taste. Riders occupy `[pickup, dropoff)` — half-open — so a rider who gets off at stop 5 and one who gets on at stop 5 are never aboard together, and the `-` event must be applied before the `+`. Encode that in the sort key itself: sort by `(coordinate, delta)` ascending, since `-c < +c` puts every alight ahead of every board at the same stop. If the spec were closed `[start, end]` — a licence held through its final second, say — touching ranges genuinely overlap and the tie must flip to starts-first, `(coordinate, -delta)`. Leaving ties to whatever order the sort happens to produce is the bug: it is invisible until two boundaries coincide, and then the count is off by one exactly at the moment you care about.

code

pseudocode · 13 lines
pseudocode
k = 0
for i in 0..n-1
    E[k] = (pickup[i], +riders[i])
    k = k + 1
    E[k] = (dropoff[i], -riders[i])
    k = k + 1
sort E ascending by coordinate, ties broken by smaller delta first
onboard = 0
for j in 0..k-1
    onboard = onboard + delta(E[j])
    if onboard > capacity
        return INFEASIBLE
return FEASIBLE

go deeper

for a junior

Recall that two boundary events can land on the same coordinate, and that you must decide which one is applied first rather than leaving it to the sort. Say the direction out loud for half-open ranges: the ending goes first.

for a middle

Derive the rule from the interval convention instead of quoting it, and show it living in the sort key as (coordinate, delta). Be ready to flip it on demand when the ranges are closed.

for a senior

Diagnose from the symptom: an intermittent off-by-one that appears only on quantised coordinates. Explain why random high-resolution test data hides it and what test you would add to force coincident boundaries.

for a principal

Frame it as a specification gap, not a coding slip: the closed-versus-half-open convention must be pinned down once, written down, and enforced across every interval routine a team owns, or each new sweep re-invents the same off-by-one.

## Where the off-by-one lives A delta sweep has two moving parts: the sort key and the running sum. The running sum is trivially correct. Essentially every real bug in this pattern lives in the sort key, and specifically in what happens when two events land on the *same* coordinate. Take a shuttle whose route is a line of numbered stops, with each trip described as "`c` riders board at stop `p`, alight at stop `d`". You want to know whether the vehicle ever exceeds `capacity`. Flatten to `(p, +c)` and `(d, -c)`, sort, run the sum, compare against the ceiling. Now consider a stop where one trip ends and another begins. Board-first briefly holds both groups aboard and can report an overflow that never physically happens; alight-first frees the seats first and reports the truth. ## The rule, stated properly The tie order is not a convention you memorise — it is derived from the interval convention: - **Half-open `[start, end)`** — the overwhelmingly common choice for time ranges and for positions along a route. An interval ending at `x` and one starting at `x` do *not* overlap, so at coordinate `x` the ending must be applied first. **End before start.** - **Closed `[start, end]`** — the range includes its final coordinate, so two intervals touching at `x` *do* overlap there, and the count must reflect both. **Start before end.** Asking the interviewer which convention the problem uses is a genuinely good move: it shows you know the answer flips, and half the interval problems in circulation are ambiguous about it. ## Encoding it in the sort The cleanest implementation puts the rule in the comparison key so the scan stays a dumb loop: | Semantics | Sort key (ascending) | Effect at a tie | |---|---|---| | `[start, end)` | `(coordinate, delta)` | negative deltas first — ends before starts | | `[start, end]` | `(coordinate, -delta)` | positive deltas first — starts before ends | Because a departure carries a negative delta and an arrival a positive one, ordering by the delta value itself gets half-open semantics for free, with no special-case branch anywhere in the scan. This is worth saying explicitly in an interview: the tie rule is a property of the key, not an `if` inside the loop. ## Why a stable sort does not save you A frequent wrong answer is "use a stable sort". Stability preserves the *input* order among equal keys — but the input order of your flattened events is an artefact of how you built the list (all pickups then all dropoffs, or interleaved per trip), which has nothing to do with the semantics you need. Stability makes the bug deterministic and reproducible; it does not make it correct. The fix is a total order on the key, not a property of the sorting algorithm. ## Why it hides in testing The defect only fires when two boundaries share a coordinate. With high-resolution timestamps and randomly generated test data, exact ties are rare, so the sweep passes its tests and then fails on production data where boundaries are quantised: shuttle stops are integers, calendar bookings snap to the half hour, batch jobs start on the minute. Deliberately test back-to-back ranges that share an endpoint, and generate random tests over a *coarse* coordinate domain so ties are common rather than exotic. ## Symptom-to-cause mapping - Count is exactly one (or exactly one group) too high, only sometimes → ties resolved start-first under half-open semantics. - A capacity check reports infeasible only when the load is exactly at the limit → the same tie bug, surfacing only where the extra unit crosses the threshold. - The result changes when you rebuild the event list in a different order → ties are being decided by the sort's arbitrary handling of equal keys; the key is under-specified. - Off-by-one everywhere, ties or not → not a tie bug; suspect an inclusive/exclusive mistake in how the events were generated in the first place. ## The generalisation Any sweep with more than one event type needs a total order over event kinds at a coordinate, not just over coordinates. Concurrency counting happens to have exactly two kinds, which is why the whole rule collapses into "sort by the delta as the secondary key". The moment you add a third kind — a query event asking "how many are active here?" alongside the starts and ends — you must decide where it sits in the tie order too, and that decision is again dictated by the semantics of the question, not by convenience.

  • How do you express the tie rule without an if-branch inside the scan?
    Make it part of the sort key. Ordering by `(coordinate, delta)` ascending puts negative deltas first, which is exactly end-before-start for half-open ranges; ordering by `(coordinate, -delta)` flips it for closed ranges. The scan then stays a plain accumulate-and-compare loop with no special cases.
  • How would you write a test that actually catches this bug?
    Force coincident boundaries: one range ending exactly where the next begins, chained a few times. Then fuzz over a deliberately coarse coordinate domain — a dozen possible values — so ties are frequent, and compare against a brute-force count at each distinct coordinate.
  • Someone suggests a stable sort will fix the ordering. Are they right?
    No. Stability preserves the order the events happened to be built in, which reflects your flattening loop rather than the interval semantics. It makes the wrong answer reproducible instead of intermittent. The fix is a total order on the key that encodes end-before-start or start-before-end deliberately.

saying these in an interview costs you the question

  • Says ties never matter, it is only one element
  • Uses one tie rule regardless of closed or half-open ranges
  • Sorts by coordinate alone and lets equal keys fall anywhere
  • Claims a stable sort makes the tie order correct
  • Adds a special case inside the scan instead of fixing the key

context

resolving links…