Coding interview: Implement an interval tree for overlap queries

Prompt and use cases

Interval trees fit dynamic time ranges, bookings, and resource occupancy. The core idea is a balanced tree ordered by lower endpoint, augmented with each subtree's maximum upper endpoint to skip impossible branches.

What the interviewer evaluates

• Whether closed-interval boundaries and overlap are correct.
• Whether maxEnd is defined and maintained precisely.
• Whether augmentation prunes work instead of scanning every node.
• Whether insertion, deletion, and rotations update the augmentation.
• Whether duplicates, an empty tree, and missing deletions are handled.
• Whether complexity accounts for the number of reported intervals.

Clarifications before answering

• Are intervals closed, open, or half-open?
• Are endpoints integers, floating point, or timestamps?
• Are duplicate intervals allowed, and does deletion use an ID or endpoints?
• Must a query return every overlap or only one?
• Are online insertion, deletion, and self-balancing required?
• Must results be sorted by lower endpoint?

30-second answer framework

“I would key a balanced tree by the lower endpoint and store the upper endpoint plus subtree maximum maxEnd. A query reports the current overlap, enters the left subtree only when its maxEnd can reach the query's lower bound, and enters the right side only while the current lower endpoint is within the query's upper bound. Insert and delete use balanced-tree operations and update maxEnd along the path, recomputing affected nodes after rotations.”

Step-by-step deep dive

Step 1: Define overlap. Closed [a,b] and [c,d] overlap exactly when a <= d and c <= b; reject a > b first.

Step 2: Define a node. Store low, high, a unique ID, children, and maxEnd; order by (low, id) so equal endpoints remain distinct.

Step 3: Prune queries. Report the current node when it overlaps. Recurse left only when left.maxEnd >= query.low, and recurse right only when current low <= query.high.

Step 4: Maintain augmentation. maxEnd is the maximum of the node's high and both child values. Recompute only affected paths after updates and rotations.

Step 5: Delete safely. Locate by ID, perform balanced-tree deletion, and update maxEnd upward from the replacement path; return an explicit result for a missing ID.

Step 6: Test boundaries. Cover touching endpoints, containment, duplicates, negatives, point intervals, an empty tree, and an output containing every interval.

Step 7: State complexity. A balanced tree has logarithmic height; a query is O(log n + k) for k reported intervals, an update is O(log n), and space is O(n).

Model high-quality answer

“I would use a red-black tree ordered by (low, id), with each node storing high and subtree maxEnd. For [q1,q2], report when low <= q2 and high >= q1; enter the left child only when left.maxEnd >= q1, and the right child only when current low <= q2. Insert and delete update maxima on the path, and rotations recompute the rotated nodes and parent. IDs distinguish duplicates. I test closed endpoints and all-hit output. Query is O(log n + k) and update is O(log n).”

Common mistakes

• Use low < q2 for overlap → touching endpoints disappear → match the chosen interval type.
• Store only each node's high → pruning is impossible → maintain subtree maxEnd.
• Skip augmentation after rotation → later queries become wrong → recompute affected nodes.
• Claim O(log n) query → output cost is missing → state O(log n + k).
• Overwrite equal endpoints → deletion and output become unstable → use a unique ID or composite key.

Follow-up questions and responses

Follow-up 1: What if queries are points only?

Use [x,x] and the same maxEnd pruning. If endpoints are small integers and static, evaluate a specialized discrete structure.

Follow-up 2: Why not scan a list?

With many intervals and interleaved updates, a scan touches all nodes. The tree limits search to a logarithmic path plus reported output.

Follow-up 3: Why do rotations preserve maxEnd?

They change only local subtrees; recomputing affected nodes bottom-up restores the field definition.

Follow-up 4: How do you delete duplicate intervals?

Assign an ID on insertion, key by (low, ID), and delete by ID so other equal-endpoint intervals remain.

Follow-up 5: What about floating-point endpoints?

Define NaN, precision, and equality semantics. When possible, convert to integer ticks or time units.

Follow-up 6: How do you guarantee sorted output?

In-order traversal provides lower-endpoint order; if pruning changes visit order, collect and sort, stating the extra cost.

Follow-up 7: Why is the pruning safe?

If a left subtree's maximum endpoint is below the query's lower bound, every interval there ends too early to overlap, so skipping it is safe.