This question evaluates understanding of interval overlap and resource allocation for meeting-room scheduling alongside recognition of binary tree structure and completeness properties.
1) Given a list of closed-open time intervals [start, end) representing meetings on a single calendar, compute the minimum number of rooms required so that no meetings in the same room overlap. Implement an algorithm, justify its time and space complexity, and discuss how you would handle very large inputs.
2) Given the root of a binary tree, determine whether it is a complete binary tree (all levels filled except possibly the last, which is filled from left to right). Provide an algorithm, analyze complexity, and describe edge cases and test cases.
Overview: This question evaluates understanding of interval overlap and resource allocation for meeting-room scheduling alongside recognition of binary tree structure and completeness properties.
This question has two independent algorithm problems on a single calendar/tree theme. Treat each Part as a self-contained coding exercise: implement a correct algorithm, justify its time and space complexity, and walk through edge cases.
Constraints & Assumptions
Part 1 (Meeting Rooms):
Intervals are closed-open
[start, end)
, so a meeting ending at time
t
and another starting at
t
do
not
conflict. Inputs may be unsorted. Times may be integers or floats. Assume up to
n≤106
intervals on a single calendar.
Part 2 (Complete Binary Tree):
The tree is given by its root node with
left
/
right
child pointers. "Complete" means every level except possibly the last is fully filled, and the last level is filled left-to-right with no gaps. Node count can be up to
∼105
; the tree may be deeply unbalanced.
Both parts should run in a standard single-threaded environment unless you explicitly call out a distributed approach for very large inputs.
Clarifying Questions to Ask Guidance
Part 1:
Are intervals half-open
[start, end)
or fully closed? (This decides whether equal endpoints conflict.) Can
start == end
(zero-length meetings) occur? Are start/end guaranteed
start < end
? Can times be negative or non-integer?
Part 1:
Do I need to return only the minimum room count, or also the assignment of meetings to rooms? Is the input already sorted?
Part 2:
Is the tree a standard binary tree (each node ≤ 2 children) with explicit
null
children? Could the root itself be
null
(empty tree)? Do values matter, or only structure?
Scale:
What is the upper bound on input size, and is memory constrained? Should I optimize for streaming / out-of-core inputs?
Part 1
Given a list of half-open time intervals [start, end) representing meetings on a single calendar, compute the minimum number of rooms required so that no two meetings assigned to the same room overlap. Implement the algorithm, justify its time and space complexity, and discuss how you would handle very large inputs (e.g. tens of millions of intervals, or a stream that does not fit in memory).
What This Part Should Cover Guidance
Recognizing that the answer is
peak concurrent intervals
, not a greedy room-assignment.
A correct
O(nlogn)
algorithm (sweep-line or two-pointer) with the half-open tie-break handled correctly.
Accurate time/space complexity justification.
A credible plan for inputs that exceed memory (external sort, streaming sweep, or bucketing on a bounded time domain).
Part 2
Given the root of a binary tree, determine whether it is a complete binary tree: all levels are completely filled except possibly the last, and the last level is filled from left to right with no gaps. Provide an algorithm, analyze its complexity, and describe the edge cases and test cases you would use.
What This Part Should Cover Guidance
A correct definition of "complete" (distinguish from
full
and
perfect
trees).
A clean BFS-with-null-sentinel or index-based algorithm.
O(n)
time and
O(w)
space (max width) analysis, with the unbalanced/skewed worst case noted.
A concrete edge-case and test-case list: empty tree, single node, perfect tree, last level partially filled left-to-right (complete) vs. a right gap (not complete), left-skewed and right-skewed trees.
What a Strong Answer Covers Guidance
Across both parts, a strong candidate demonstrates the same disciplined process: restate the precise definition, pick the cleanest algorithm, justify complexity in O(⋅) terms, and proactively enumerate edge cases rather than waiting to be prompted. They handle the half-open vs. closed-interval subtlety in Part 1, correctly distinguish complete from full/perfect in Part 2, and discuss how each solution degrades or scales (memory pressure, skewed trees, streaming). Clean, bug-free reference code with sensible variable names and a dry-run on a small example rounds out the answer.
Follow-up Questions Guidance
Part 1:
Beyond the room
count
, return an actual assignment of each meeting to a specific room (e.g. using a min-heap of room-free-times). What changes in complexity?
Part 1:
How would you answer many concurrency queries ("how many meetings overlap time
t
?") after preprocessing, rather than a single max? (Hint: prefix sums / a sorted event array with binary search.)
Part 2:
How would you check completeness
without
materializing the whole queue — e.g. using
O(log2n)
work via the perfect-subtree / binary-search-on-last-level trick that computes node count?
Part 2:
If the tree is given as a serialized array with
null
markers, how does the completeness check simplify or change?