Lab 01 — Problem Statement Reading

Goal

Train the discipline of reading a problem statement deliberately — extracting structure, constraints, examples, and ambiguity — before any solving begins. Most candidate failures begin in the first 60 seconds when the candidate reads superficially and locks in a wrong mental model.

Background Concepts

• Active reading vs passive reading
• Structural parsing of a problem (input shape, output shape, constraints, examples, follow-ups)
• Identifying ambiguity vs underspecification
• Restating in your own words as a comprehension test

Interview Context

In a real interview, the prompt is often delivered verbally with a brief written version. You have ~3 minutes to load the entire problem into working memory before you start engaging. If you misunderstand something here, every subsequent step is wasted. Strong candidates always restate the problem out loud and ask 2–4 clarifying questions before touching anything.

Problem Statement

Given the problem statement below, in 5 minutes:

1. Read it twice.
2. Restate it in your own words.
3. List all constraints (explicit + implicit).
4. List 3 ambiguities you’d ask the interviewer about.
5. Construct 3 examples beyond the one given.

The problem (use as a fixed text for this lab):

“Given a list of meeting time intervals, determine if a single person could attend all meetings.”

Example: [[0,30],[5,10],[15,20]] → false.

Constraints

The problem deliberately omits constraint specification. That’s the point.

Clarifying Questions (you should generate)

Examples of good questions to surface from the prompt above:

• Are intervals inclusive on both ends, or [start, end)?
• Can intervals be zero-duration ([5,5])?
• Is the input pre-sorted?
• Are negative times possible?
• What are the realistic bounds on N and on the time values?
• Can two meetings sharing an endpoint be attended (e.g. one ends at 10, next starts at 10)?
• Are there any null or invalid intervals to validate?

Examples (you should generate)

Beyond the given:

• [] → true (empty)
• [[1,5]] → true (single)
• [[1,5],[5,10]] → endpoint-sharing case (depends on inclusivity)
• [[1,5],[2,3]] → fully nested overlap
• [[10,20],[1,5]] → unsorted, non-overlapping
• [[1,1],[1,1]] → zero-duration duplicates

Initial Brute Force

Compare every pair: O(N^2). For each pair, check if intervals overlap (max(a.start, b.start) < min(a.end, b.end) for half-open).

Brute Force Complexity

Time O(N^2), space O(1).

Optimization Path

Sort by start time, then walk through and check intervals[i].start >= intervals[i-1].end. Two thoughts emerge during sorting: ties on start, and the inclusivity semantics — both surface back to the clarifying questions. Optimal after the clarification.

Final Expected Approach

Sort + linear scan. O(N log N) time, O(1) extra space (or O(N) if sorting requires a copy).

Data Structures Used

• The interval array (input)
• Sort comparator on start time

Correctness Argument

After sorting by start, two meetings overlap ↔ some adjacent pair overlaps. Proof: if intervals i < j overlap, then for all k with i ≤ k < j, since intervals[k].start ≤ intervals[j].start < intervals[i].end ≤ intervals[k].end (after sort), k and k+1 overlap somewhere too. By induction, adjacent pairs cover all overlap detection.

Complexity

• Time: O(N log N) (sort dominates)
• Space: O(1) auxiliary if in-place sort, else O(N)

Implementation Requirements

For this lab, do NOT implement. Instead produce a written deliverable (described below).

Tests

Not applicable for this lab — written exercise only.

Follow-up Questions

• “What if instead of yes/no, we wanted the number of conflicts?”
• “What if we had to schedule N people across M rooms?” (becomes Meeting Rooms II)
• “What if the meetings stream in one at a time and we want online detection?”

Product Extension

This is “calendar conflict detection” — a real product feature. Ask yourself: what would Google Calendar do for 10,000 events? (Hint: indexed by day → small per-day scan, or interval tree for general queries.)

Language/Runtime Follow-ups

• In Python, sort is O(N log N) Timsort, stable. Beware of key=lambda x: x[0] — closure overhead vs operator.itemgetter(0).
• In Java, sort uses dual-pivot quicksort for primitives, Timsort for objects. Comparator allocation can dominate small inputs.
• In Go, sort.Slice is reflection-based and slow; prefer sort.Slice only when convenient or use sort.Sort with a typed slice.
• In C++, std::sort is introsort; comparator must be strict-weak-order or behavior is UB.

Common Bugs

• Using <= instead of < (or vice versa) due to misreading inclusivity
• Mutating input when interviewer expects pure function
• Off-by-one on boundary cases ([1,5] and [5,9])
• Not handling empty input

Debugging Strategy

If a test fails:

1. Print pairs where the algorithm decided “overlap” or “no overlap”
2. Walk through the smallest failing case by hand
3. Check inclusivity assumption — single source of most bugs here

Deliverable For This Lab

In your notebook (or a markdown file beside this lab), write:

1. Restatement. A 1–2 sentence paraphrase of the problem in your own words.
2. Clarifying questions list. 6+ questions, prioritized.
3. Implicit constraints list. What did the prompt fail to specify? (Inclusivity, sortedness, N bounds, etc.)
4. Examples list. 8+ examples covering: trivial, boundary, adversarial, multi-answer.
5. Brute force pseudocode. O(N^2) approach.
6. Optimization sketch. Just one paragraph.
7. Self-critique. Where in your reading did you make assumptions that the prompt didn’t justify?

Mastery Criteria

You complete this lab to mastery when:

• You restated the problem without re-reading the prompt
• You produced 6+ clarifying questions, none of which were answered by the prompt
• You found 3+ implicit constraints
• You produced 8+ examples spanning all category types
• You can articulate which of your assumptions were wrong (everyone makes some — the skill is noticing)

Repeat this lab with 3 different problem statements (pick any from LeetCode Easy) before declaring mastery.