Medium

Google-styleMicrosoft-style

Merge Overlapping Room Bookings DSA Interview

Given a list of room booking intervals, each with a start and end time, merge all overlapping or touching intervals into the minimal set of consolidated bookings.

Mock Interview with AI

1. Problem Statement

You are given a list of room booking intervals, each as [start, end]. Merge all overlapping or touching intervals and return the minimal consolidated list, sorted by start time.

2. Live Coding Format

Choose Python, JavaScript, Java, or C++, then solve while explaining your reasoning to the live interviewer.

Validation uses handwritten tests only. The MVP does not compile or run code, and it does not provide AI algorithm completion.

3. Key Focus Areas

1
Problem clarification and contract
2
Approach exploration and optimality
3
Think-aloud communication and pacing
4
Implementation correctness
5
Code quality and language fluency
6
Handwritten tests and dry run
7
Debugging and self-correction
8
Complexity analysis
9
Follow-up performance

4. What Strong Candidates Should Demonstrate

✓Clarify whether touching endpoints count as overlapping and whether input is pre-sorted.
✓Explain a pairwise-merge baseline and improve to a sort-then-single-pass merge.
✓Think aloud while implementing readable, correct merge logic.
✓Validate with explicit expected outputs and a top-to-bottom handwritten dry run.
✓Analyze time and space complexity and handle a bounded follow-up modification.

Evaluation Guide

This is an evaluation framework, not a single model answer. Strong designs may make different choices when their assumptions and trade-offs are explicit.

Problem clarification and contract

10%

Senior signals

✓Clarifies whether an interval ending exactly when another begins should be merged, whether input is sorted, and whether intervals can be malformed (start after end).
✓Confirms output ordering requirements and whether the original list may be mutated.

Staff-level signals

◆Raises whether this feeds a system where bookings arrive incrementally rather than as one batch.

Common red flags

×Codes immediately while assuming input is already sorted without confirming.

Approach exploration and optimality

20%

Senior signals

✓Explains a pairwise comparison approach that repeatedly rescans for overlaps, identifies its repeated-work bottleneck, and improves to sorting by start time followed by a single linear pass.
✓Explains the merge invariant: compare the current interval's start against the running merged interval's end.

Staff-level signals

◆Discusses how the approach would change if bookings needed to be merged incrementally as new ones arrive.

Common red flags

×Starts implementation without explaining an approach even after one interviewer prompt.

Think-aloud communication and pacing

10%

Senior signals

✓Explains the plan before coding and narrates the sort-then-merge invariant while implementing.
✓Paces the core solution to leave time for validation and the follow-up.

Common red flags

×Writes substantial code silently and cannot explain what the code is doing.

Implementation correctness

25%

Senior signals

✓Implements a correct sort-by-start-time followed by a single pass that merges overlapping or touching intervals, per the confirmed touching-endpoint contract.
✓Handles an empty list, a single interval, fully nested intervals, and intervals that only touch at endpoints.
✓Provides a convincing invariant argument for why a single sorted pass suffices.

Common red flags

×Fails to update the running interval's end to the maximum of overlapping ends.
×Final code contains a material correctness bug that the candidate does not identify.

Code quality and language fluency

15%

Senior signals

✓Produces readable, language-appropriate code with clear names and a well-defined comparator or sort key.

Common red flags

×Contains sort-comparator errors or syntax-level incoherence that prevents credible reasoning.

Handwritten validation, dry run, and debugging

10%

Senior signals

✓Provides explicit inputs and expected outputs before tracing the code from top to bottom.
✓Covers empty input, single interval, nested intervals, and touching-endpoint intervals.
✓Finds and fixes an error independently, then re-validates the affected path.

Common red flags

×Claims the code works without a representative trace.

Complexity analysis and follow-up

10%

Senior signals

✓States O(n log n) time dominated by sorting and O(n) auxiliary space for the result, comparing it with the quadratic pairwise baseline.

Staff-level signals

◆Discusses the cost of merging incrementally versus re-sorting the full set on every new booking.

Common red flags

×Cannot state the complexity of the implemented solution.
×Fails a reasonable follow-up despite having at least five minutes and receiving bounded clarification.

Trade-offs to articulate

Pairwise rescanning avoids an upfront sort but costs quadratic time in the number of intervals.
Sorting by start time costs O(n log n) but enables a single linear merge pass.
Merging incrementally as bookings arrive avoids re-sorting but requires an ordered structure to find the insertion point efficiently.

Practice follow-up questions

1.Coding follow-up: given the already-merged list and a new booking request, determine whether it can be inserted without creating an overlap, and if so, return the updated merged list.
2.Verbal extension: how would the approach change if bookings arrived one at a time and the merged list needed to stay current after each arrival?

Want interactive feedback?

Practice this problem in the live coding workspace while the interviewer probes your clarification, algorithm, implementation, complexity, and handwritten tests.

Start Interview

Core Concepts

IntervalsSortingGreedyComplexity Analysis