← Microsoft Interview Insights

Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Microsoft SWE interview with a calendar booking design problem. Pretty focused session, just the one question but they pushed on edge cases and complexity tradeoffs.

Questions Asked (1)

Q1

Design a calendar booking system that stores half-open time intervals. Implement a `book(start, end)` method that returns true and adds the event if it doesn't conflict with any existing booking, and false otherwise.

Algorithms & Data StructuresSystem Design
Author's notes

The overlap condition tripped me up for a second.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the half-open interval semantics and edge cases first, then propose a balanced binary search tree (e.g., TreeMap) to store bookings sorted by start time. For each new booking, find the immediate predecessor and successor to check for overlaps in O(log n) time, and insert if no conflict.

Pro tip: Emphasize that half-open intervals [start, end) allow adjacent bookings (e.g., [1,2) and [2,3)) to coexist, and explicitly state that you'll handle edge cases like start >= end by returning false. This shows attention to detail and practical robustness.

1. Clarify requirements and edge cases

Confirm the half-open interval semantics, discuss invalid inputs (start >= end), and whether zero-length intervals are allowed. Also clarify if bookings can be modified or cancelled.

2. Choose data structure

Select a balanced binary search tree (e.g., TreeMap in Java) keyed by start time to maintain sorted order and enable O(log n) lookups. Explain why a simple list would be O(n) per operation.

3. Design conflict detection logic

For a new interval [s, e), find the floor entry (largest start <= s) and ceiling entry (smallest start >= s). Check if the floor's end > s or the ceiling's start < e; if either, conflict exists.

4. Implement book method

If no conflict, insert the new interval into the tree and return true; otherwise return false. Ensure the insertion maintains the tree's sorted order.

5. Analyze complexity and test

State that book runs in O(log n) time and O(n) space. Walk through examples including adjacent intervals, overlapping intervals, and invalid inputs to verify correctness.

Key Points to Mention

  • Half-open interval semantics: [start, end) means start inclusive, end exclusive, so adjacent intervals do not conflict.
  • Use of a balanced BST (e.g., TreeMap) for O(log n) insertion and lookup.
  • Conflict check via predecessor and successor: floor entry's end > new start OR ceiling entry's start < new end.
  • Handling invalid inputs: if start >= end, return false immediately.
  • Time and space complexity: O(log n) per book operation, O(n) total space.
  • Edge cases: empty calendar, booking exactly adjacent to existing, booking at boundaries.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.