Skip to content
Tech Interview Prep
Technical interview guide

Intervals

Ranges with a start and end: sorting by start (or end) turns overlap and merge problems into a single linear pass.

Read
42 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with sorting and heap behaviour cited from CPython 3.14.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A booking service stores reservations as half-open intervals [start, end) in minutes since midnight, and flags two reservations as conflicting when their intervals overlap. The conflict check is written as `a.start <= b.end and b.start <= a.end`. Reservation A is [540, 600) and reservation B is [600, 660). What does the check return for A and B, and what should it return?
MCQ-2A booking service stores reservations as half-open minute ranges [start, end) from midnight, so a reservation ending at 600 and one starting at 600 are meant to be compatible. Its conflict test is `a[0] <= b[1] and b[0] <= a[1]`. Ops reports that the service keeps refusing bookings that merely abut an existing one. A developer builds a fixture of four ranges ([540, 600), [600, 700), [560, 660) and [660, 780)) and runs the deployed test over all six unordered pairs. How many pairs does it report as conflicting?
MCQ-19A service records incident intervals as half-open [start, end) in epoch seconds and evaluates them against a half-open SLO window [1000, 1300). The incidents are [900,1000), [1000,1100), [1200,1300), and [1300,1400). Which incidents count as overlapping the window?
MCQ-24A merge routine for half-open intervals `[start, end)` sorts by start and folds left to right: ```python def merge(intervals): out = [] for s, e in sorted(intervals): if out and s <= out[-1][1]: out[-1] = (out[-1][0], e) else: out.append((s, e)) return out ``` Its suite passes today and covers the empty list plus a few pairs that either overlap heavily or not at all. Which case, added to the suite, fails against this implementation?
MCQ-4A booking service materialises each room's occupancy as merged blocks. Reservations arrive in insertion order, not sorted, and each is half-open [start, end) in minutes past midnight. Room 4 holds [12,15), [1,10), [2,3), [16,18). The merge pass sorts by start, then walks the list keeping a running block: when the next start is less than the running end it extends the running block, otherwise it emits the running block and opens a new one. Which list does the pass produce, ordered by start?
MCQ-3A calendar service receives intervals [[1,10], [2,3], [4,5], [6,7]]. It must output merged busy blocks and the largest set of non-overlapping meetings. An engineer sorts by start time once and runs the merge routine and the greedy selection routine on that order. What is the result?
MCQ-5A scheduler keeps blocked time ranges as a sorted, disjoint list of [start, end) minute offsets: [[0,30],[60,90],[120,150],[200,260],[300,340]]. A new block [80,130] arrives and is inserted with overlaps merged in a single left-to-right pass. Which list results?
MCQ-11A booking service computes free slots as the complement of merged busy intervals inside a working window. The implementation is: ```python def free_slots(busy, lo, hi): out, cur = [], lo for s, e in busy: if cur < s: out.append((cur, s)) cur = max(cur, e) return out ``` It is called with `busy = [(9, 11), (13, 14), (16, 17)]`, `lo = 8`, `hi = 18`. What does it return?
MCQ-9When implementing a greedy algorithm to find the maximum number of mutually compatible non-overlapping intervals (or equivalently, the minimum number of intervals to remove to eliminate overlaps), which sorting strategy guarantees an optimal solution?
MCQ-10When computing the intersection of two sorted lists of pairwise disjoint closed intervals, how are the intersection endpoints computed and how does the two-pointer sweep decide which pointer to advance?
MCQ-14A team must report the total length covered by the union of intervals [0,10], [5,15], and [100,110]. They compress the endpoints to ranks 0–5, merge the compressed intervals to [0,3] and [4,5], and report the union length as (3−0)+(5−4) = 4. Which value should they report, and why?
MCQ-6A metrics job computes peak concurrent sessions from half-open intervals [start, end) in seconds. It emits (start, +1) and (end, -1) for each session, sorts the events, then walks them keeping a running counter and its maximum: ```python sessions = [(0, 2), (1, 3), (2, 4), (3, 5), (4, 6)] # half-open [start, end) events = [] for s, e in sessions: events.append((s, 1)) events.append((e, -1)) events.sort() cur = peak = 0 for _, d in events: cur += d peak = max(peak, cur) print(peak) ``` What does this print?
MCQ-7A booking system has six meetings: A 09:00–10:20, B 09:30–11:10, C 10:00–10:50, D 10:40–12:00, E 11:00–11:40, F 11:20–12:30. It must assign each meeting to a room so that no two meetings in the same room overlap. What is the minimum number of rooms, and which assignment achieves it?
MCQ-8Meetings are half-open intervals [start, end): a room occupied until end is free at end. Intervals arrive sorted by start time. In the min-heap greedy for Meeting Rooms II, what does the heap store for each occupied room, and when is its root popped?
MCQ-22A telemetry job must report the exact peak number of simultaneously open sessions from 2×10^9 session intervals (start, end) stored on disk as 32-byte records, 64 GB total, on a worker with 8 GB of RAM. The current code loads every interval into a list, sorts, and sweeps; it dies with MemoryError. Which change lets the job finish on that same 8 GB worker?
MCQ-13A batch job is handed all N intervals and all Q query points before it starts, and must report the coverage count at every query point. Coordinates are 64-bit timestamps whose span is far larger than N+Q. Which approach is correct, and what does it cost?
MCQ-12A telemetry service ingests intervals [l_i, r_i] online, new intervals arrive and existing ones expire at arbitrary times, and read workers issue point-stabbing count queries: for a timestamp x, return the exact number of stored intervals with l_i ≤ x ≤ r_i. Timestamps are 64-bit values, so the domain is vastly larger than the number of live intervals. Every update and every query must run in O(log N) worst case, and memory must scale with N, the number of live intervals, not with the timestamp domain. Which structure meets all three requirements?
MCQ-15An interval tree holds [2,9], [4,6] and [11,14], keyed on start and augmented with the maximum end in each subtree. The root is [11,14]; its left child is [4,6], whose left child is [2,9]. After a rebalance, the node holding [4,6] still stores max_end = 5, though the true maximum end in its subtree is 9. A query for [7,8] runs against this tree. What does it return, and why?
MCQ-17A segment tree over 8 leaves (indices 0–7), all initially 0, supports range add and range sum with lazy propagation. Three operations run in order: add 5 to [0,7]; add 3 to [0,3]; query the sum of [0,1]. Immediately after the query returns, what is the value of lazy[2,3]?
MCQ-18A metrics service keeps 1,000,000 per-minute counters and must answer `range_max(l, r)` over them. Counters change by ±1 through `add(i, delta)` (200,000 such updates). The team's Fenwick tree returns a value that is too high for some ranges after counters are decremented. Which change fixes the stale values?
MCQ-16A fleet-monitoring service keeps 200,000 sensor readings in one array. Every minute it applies about 50,000 range updates (add v to every reading in [l, r]) and answers about 50,000 queries for the minimum reading in [l, r]. Which structure should back this?
MCQ-25A service loads 4,000,000 fixed intervals once at startup, then answers 100,000 point-stabbing queries per second. A new requirement adds 2,000 interval insertions per second, interleaved with those queries. Which change should the team make?
MCQ-23A per-key limiter allows 1,000 requests per 60 s. On each request it appends the current timestamp to a per-key list, drops timestamps older than 60 s, and allows the request if fewer than 1,000 timestamps remain. One client sends 50,000 requests per second for 60 seconds; every request past the first 1,000 in each window is rejected. What does that key's list hold at the end of the 60 seconds?
MCQ-21A simulation tracks intervals on a clock that starts at 0. Interval A ends at `0.1 + 0.2`; interval B starts at the literal `0.3`. The overlap test is `a_end > b_start`, comparing raw doubles. What does the test report for these two intervals?
MCQ-20A booking service stores each booking's start and end as naive local wall-clock datetimes in Europe/London and computes the duration by subtracting them. A booking runs from 2026-10-25 00:30 to 2026-10-25 02:30 local. What duration does the service report, and what is the real elapsed time?