Coding interview: How do you implement a calendar that rejects overlaps?

Prompt and context

Implement a calendar where book(start, end) returns true and stores the interval only when it does not overlap an existing one. Intervals are half-open and require start < end; [10, 20) and [20, 30) are adjacent. The problem tests ordered structures, boundaries, insertion timing, and complexity.

What the interviewer tests

The key is a provable overlap condition: with starts sorted, only the immediate predecessor and successor need checking. A strong answer compares a scan, balanced tree, and sorted array, then notes that multi-threaded or persistent services add atomicity and locking requirements.

Questions to clarify

• Are times integers or timestamps, and can they be negative?
• Must start < end be validated, and what happens on invalid input?
• Are intervals strictly half-open, allowing equal endpoints to touch?
• How many bookings and what range; are cancellation or queries needed?
• Is this single-threaded in memory or a persistent multi-process service?

30-second answer

I would use a map ordered by start. For [s, e), find the first successor with start at least s; if its start is below e, the intervals overlap. Then inspect the predecessor; if its end is above s, they overlap. Insert only when both checks pass. Half-open semantics allow predecessor end equal to s and successor start equal to e. A balanced tree gives O(log n) lookup and insertion with O(n) space.

Step-by-step deep answer

Step 1: Define overlap

Half-open [a, b) and [c, d) overlap exactly when a < d && c < b. Once starts are ordered, the direct predecessor and successor suffice because farther intervals end earlier or start later.

Step 2: Choose an ordered structure

A balanced tree or Java TreeMap provides predecessor and successor lookup. A sorted array has O(log n) search but O(n) insertion; a scan is O(n). Match the choice to booking volume and operation mix.

Step 3: Check before inserting

Inspect successor, then predecessor, and write only after both pass. Inserting and rolling back later can expose an invalid intermediate state.

boolean book(int start, int end) {
  if (start >= end) return false;
  var next = events.ceilingEntry(start);
  if (next != null && next.getKey() < end) return false;
  var prev = events.floorEntry(start);
  if (prev != null && prev.getValue() > start) return false;
  events.put(start, end);
  return true;
}

Step 4: Prove boundary behavior

next.start == end and prev.end == start do not overlap. Equal starts cannot replace an intersecting old interval because the successor check rejects it. Use safe numeric types if timestamps can overflow.

Step 5: State complexity

Balanced-tree predecessor, successor, and insertion are O(log n), with O(n) space. A sorted array searches in O(log n) but inserts in O(n); a scan is simple but scales poorly. Include rejected calls in the complexity discussion.

Step 6: Extend to concurrency and persistence

On one machine, lock the check and insert together. Across processes, use a transaction, unique constraint, or range lock; a cache cannot be the final conflict authority.

Trade-offs and boundaries

Half-open versus closed intervals

Half-open intervals express adjacent slots naturally, have length end - start, and avoid boundary duplication. A closed-interval business must redefine granularity consistently.

TreeMap versus an interval tree

Predecessor and successor are enough when every overlap is rejected. Overlap queries, cancellation, or range statistics may justify an interval tree or database range index.

Rollout plan and evidence

Test matrix

Cover the first interval, containment, partial overlap, touching endpoints, equal starts, empty input, large values, and duplicate requests. After each accepted booking, assert the sorted invariant.

Production boundary

For multiple instances define transaction isolation, conflict errors, retry idempotency keys, and timezone rules. Load-test the persistent constraint under concurrent bookings.

Common mistakes and follow-ups

Mistake: checking only the successor

The new interval can overlap the predecessor’s tail, so predecessor end must also be checked.

Mistake: treating equal endpoints as overlap

Half-open semantics allow [10, 20) and [20, 30) to touch; keep strict comparisons.

Mistake: inserting before detecting conflict

Checking and writing must be one logical atomic step to preserve the invariant.

Follow-up: allowing two overlaps

Maintain active-interval counts or a sweep line; the constraint becomes a maximum-overlap problem.

Follow-up: concurrent bookings

Lock on one machine; use transactions, range locks, or serializable writes across instances rather than process-local memory.