Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Sort meetings by start time, and track the end times of currently occupied rooms in a min-heap (a binary heap ordered so the smallest element is always at the root, giving $O(\log n)$ push and pop). For each meeting, if the room that frees earliest already ended at or before this meeting's start, reuse it; otherwise open a new room. The peak number of rooms in use at any moment is the answer, which is a fundamentally different question from merge-overlapping-intervals: that problem asks for the union of overlapping ranges, while this one asks for the maximum number of ranges alive at the same instant, which can be larger than the number of merged groups whenever more than two meetings overlap at once.

Structured elaboration

Why this differs from merging overlapping intervals

Merging intervals collapses any chain of pairwise-overlapping intervals into one output range: three meetings that overlap in a chain (A overlaps B, B overlaps C, but A and C do not) merge into a single interval. Room counting instead asks how many of them are simultaneously alive, which is a different quantity: those same three meetings only ever need 2 rooms if A and C never overlap directly, even though they all merge into one interval. Room counting is a peak concurrency question, not a union of ranges question.

Why sorting starts and ends (or a heap of active ends) gets you there

Model each meeting as a $+1$ event at its start and a $-1$ event at its end. Sorting starts and ends and sweeping through events in time order lets you track the running concurrent count directly: the answer is the maximum value that running count ever reaches. A min-heap of active end times is an equivalent formulation of the same sweep: instead of a raw counter, the heap always tells you the earliest time a room becomes free, so you know immediately whether the next meeting can reuse an existing room or needs a new one.

Algorithm (steps)

1. Sort meetings by start time.
2. Maintain a min-heap of the end times of meetings currently occupying a room.
3. For each meeting in start order: if the heap is non-empty and its minimum end time is $\le$ this meeting's start, pop that end time (that room frees up) and push this meeting's end time in its place; otherwise push this meeting's end time as a new room.
4. The final heap size is the minimum number of rooms needed.

Worked example

import heapq


def min_meeting_rooms(intervals: list[list[int]]) -> int:
    """
    Minimum concurrent rooms needed. O(n log n) time, O(n) space (heap of end times).
    """
    if not intervals:
        return 0
    ordered = sorted(intervals, key=lambda pair: pair[0])
    heap: list[int] = []  # end times of meetings currently occupying a room
    for start, end in ordered:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse the room that frees earliest
        else:
            heapq.heappush(heap, end)     # need a new room
    return len(heap)


if __name__ == "__main__":
    sample = [[0, 30], [5, 10], [15, 20]]
    print(min_meeting_rooms(sample))
    no_overlap = [[7, 10], [2, 4]]
    print(min_meeting_rooms(no_overlap))

Running this prints:

2
1

For [[0,30],[5,10],[15,20]]: room 1 opens for [0,30]; at start=5, the heap's minimum end is 30 which is not $\le$ 5, so a new room opens for [5,10]; at start=15, the minimum end is now 10 (from the just-finished [5,10]), which is $\le$ 15, so that room is reused for [15,20]; final heap size 2. For [[7,10],[2,4]] (sorted to [[2,4],[7,10]]): room 1 opens for [2,4]; at start=7, the minimum end 4 is $\le$ 7, so the same room is reused; final heap size 1.

Complexity

Time: $O(n \log n)$, dominated by the initial sort (heap operations are $O(\log n)$ each, over $n$ meetings). Space: $O(n)$ for the heap in the worst case, when every meeting overlaps every other.

Edge cases

• Empty input needs 0 rooms.
• A meeting that starts exactly when another ends is treated as not overlapping here (the room is reused): whether a meeting ending at t and one starting at t count as conflicting is a modeling choice to state up front.
• All meetings mutually overlapping (for example, everyone scheduled from 9am to 5pm) requires n rooms, the maximum possible.
• Duplicate identical meetings still each require their own room if they are genuinely simultaneous distinct bookings.

Trade-offs & pitfalls

The most common wrong turn is applying the merge-overlapping-intervals algorithm here and reporting the number of merged groups: that undercounts whenever three or more meetings overlap in a chain without all pairwise overlapping, since merging only tracks the union shape, not simultaneous occupancy. A second common gap is not being explicit about the boundary rule (does a meeting ending at t conflict with one starting at t), since interviewers frequently vary this to see if the candidate notices the assumption. For the streaming follow-up (meetings arriving one at a time rather than as a batch), the min-heap of active end times generalizes directly: insert the new end time, and if a room is reused, decrement the heap; there is no need to re-sort, since the heap already maintains order incrementally.

Direct answer

Keep a min-heap (a priority queue: a tree-shaped structure that keeps the smallest element accessible at the root in logarithmic time) holding one candidate element from each of the k sources, tagged with which source it came from. Repeatedly pop the smallest, emit it, then pull the next element from that same source and push it back in. This touches every element exactly once and never holds more than k elements in the heap at a time, unlike scanning all k sources for the minimum on every step, which redoes that comparison work from scratch each time.

Structured elaboration

Maintain, per source, an iterator (or a buffered read-ahead block if the source is a file or network stream) rather than loading the whole source into memory. The heap holds at most one (value, source_id) pair per still-active source:

1. Prime the heap: pull the first element from each source and push all k pairs in.
2. Loop while the heap is non-empty: pop the smallest pair, emit its value, then pull the next element from that same source; if one exists, push it back onto the heap.
3. Stop when the heap empties, meaning every source is exhausted.

Why the heap beats scanning all k sources for the minimum: a linear scan over k sources costs $O(k)$ per output element, for $O(N \cdot k)$ total across $N$ elements. The heap instead pays $O(\log k)$ per push and pop, for $O(N \log k)$ total. Once k grows past a small constant (which it does for genuinely large fan-in, like merging thousands of shards), $\log k$ is dramatically cheaper than $k$, and the heap only ever holds k items regardless of how large each individual source is, which is what makes this work under a fixed memory budget.

Worked example

import heapq
from typing import Iterable, Iterator


def k_way_merge(sources: list[Iterable[int]]) -> Iterator[int]:
    heap: list[tuple[int, int, Iterator[int]]] = []
    for i, source in enumerate(sources):
        it = iter(source)
        first = next(it, None)
        if first is not None:
            heap.append((first, i, it))
    heapq.heapify(heap)

    while heap:
        value, i, it = heapq.heappop(heap)
        yield value
        nxt = next(it, None)
        if nxt is not None:
            heapq.heappush(heap, (nxt, i, it))


stream_a = [1, 4, 9, 15]
stream_b = [2, 3, 8]
stream_c = [0, 5, 6, 7, 20]

merged = list(k_way_merge([stream_a, stream_b, stream_c]))
print(merged)
print(merged == sorted(stream_a + stream_b + stream_c))

Running this prints:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 15, 20]
True

Key points

• The heap never grows past k elements no matter how large each source is, which is exactly what makes this work when sources are too large to fit in memory together.
• Each source only needs to expose "give me the current head" and "advance to the next element," which is why the same code works whether a source is a Python list, a sorted linked list, or a buffered file reader.

Complexity

where $N$ is the total number of elements across all sources. If sources are read from disk in blocks rather than streamed one element at a time, add $O(k \cdot \text{block\_size})$ for the read-ahead buffers.

Edge cases

• An empty source: simply contributes nothing to the initial heap priming, handled by the if first is not None guard.
• Duplicate values across sources: the heap comparison ties are broken by insertion order in this implementation (via the source index in the tuple), so output remains stable and well-defined.
• All sources exhausted simultaneously: the loop ends naturally when the heap empties.

Trade-offs & pitfalls

For disk-resident or over-the-network sources, reading one element at a time is usually the wrong granularity: buffering a block per source amortizes I/O overhead, at the cost of O(k * block_size) memory instead of O(k). This is the same "k-way-merge" primitive whether the k inputs are k sorted arrays, k sorted linked lists (pop the head node instead of an array iterator), or k disk-resident sorted files too large to hold together, and it generalizes further to an external top-K query across those files by simply stopping the loop after K pops instead of draining the heap. A common mistake is reaching for a full sort of the concatenated data instead of a merge: since each source is already sorted, a merge is $O(N \log k)$ while re-sorting everything from scratch is $O(N \log N)$, strictly worse whenever $k \ll N$, which is the normal case.

Direct answer

Start with two pointers at the far-left and far-right lines and compute the area between them as the width times the shorter of the two heights, since the shorter line is what actually limits how much water the pair can hold. Then repeatedly move whichever pointer marks the shorter line one step inward, tracking the best area seen. This is safe because keeping the shorter line fixed and moving the taller one inward can only shrink the width while the limiting height stays the same or gets worse, so that move can never beat the current area; moving the shorter line is the only move that has any chance of finding a taller line and thus a larger limiting height.

Approach

• Initialize left = 0 and right = len(height) - 1.
• At each step, compute area = min(height[left], height[right]) * (right - left) and update the best area seen.
• Move the pointer at the shorter height inward (left += 1 or right -= 1); if the two heights are equal, either pointer can move.
• Stop when left == right.

from typing import List


def max_area(height: List[int]) -> int:
    """Two-pointer O(n) time, O(1) space solution."""
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best


if __name__ == "__main__":
    print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7]))  # 49
    print(max_area([1, 1]))                        # 1
    print(max_area([4, 3, 2, 1, 4]))               # 16

Running this prints 49, 1, 16. For [1, 8, 6, 2, 5, 4, 8, 3, 7], the best area of 49 comes from index 1 (height 8) and index 8 (height 7): width $8 - 1 = 7$ times limiting height $\min(8, 7) = 7$ gives $49$, and no other pair in that array beats it.

Key points

• The greedy step only works because the pointer you leave behind (the taller one) was never the bottleneck for the current pair, so discarding it costs nothing you could have used; discarding the shorter one instead would throw away the only pointer that could have found something taller.
• Equal heights at both pointers: either pointer can move; the tie means both sides are equally the "shorter" one for that comparison.
• In a fixed-width-integer language (Java, C++), height * width can overflow a 32-bit integer for very large inputs; use a 64-bit accumulator for the area. Python integers don't have this issue, but it's a real production concern in typed languages.

Complexity

Time: $O(n)$, a single pass with the two pointers converging. Space: $O(1)$, only the two pointers and a running best value.

Edge cases

• Fewer than two lines: no container is possible, so the answer is 0.
• All heights equal: every pair's limiting height is the same, so the widest pair (the two endpoints) wins.
• A height of 0 at some position contributes an area of 0 whenever it's one of the two chosen lines, which is harmless, just never optimal.
• This two-pointer approach only finds the best area between two chosen lines; it does not generalize directly to the harder "water trapped above every bar" version of this problem (where interior bars can also trap water above them), since that variant needs to track a running maximum height from the left and from the right at every position, not just a single global best between two outer lines. It's a natural harder extension of the same converging-pointer idea, but with per-position bookkeeping added on top.

Direct answer

Model the courses as a directed graph where an edge from a prerequisite $B$ to a course $A$ means "$B$ must come before $A$", then run Kahn's algorithm: repeatedly take any course whose remaining prerequisite count (its indegree) is zero, add it to the order, and decrement the indegree of everything it unlocks. If every course gets processed this way, the resulting order is valid. If the queue empties while courses still have a nonzero indegree, those courses form a cycle, a prerequisite loop that can never be satisfied, and finishing all courses is impossible.

Approach

• Build an adjacency list (prerequisite to course) and an indegree array (how many unprocessed prerequisites each course still has).
• Seed a queue with every course that already has indegree zero.
• Repeatedly pop a course, append it to the output order, and for every course it unlocks, decrement that course's indegree; if it hits zero, enqueue it.
• If the final order's length equals the number of courses, it's a valid full order; otherwise the remaining, never-enqueued courses are exactly the ones stuck in a cycle.

from collections import deque
from typing import List, Tuple


def find_order(num_courses: int, prerequisites: List[Tuple[int, int]]) -> List[int]:
    """prerequisites: list of (course, prereq) pairs meaning 'course'
    depends on 'prereq'. Returns a valid order, or [] if a cycle makes
    finishing all courses impossible."""
    adj: list[list[int]] = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for course, prereq in prerequisites:
        adj[prereq].append(course)
        indeg[course] += 1

    queue = deque(c for c in range(num_courses) if indeg[c] == 0)
    order: list[int] = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in adj[node]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)

    return order if len(order) == num_courses else []


if __name__ == "__main__":
    # course 1 needs 0, course 2 needs 0, course 3 needs 1 and 2
    print(find_order(4, [(1, 0), (2, 0), (3, 1), (3, 2)]))
    # cycle: 0 needs 1, 1 needs 0
    print(find_order(2, [(0, 1), (1, 0)]))

Running this prints [0, 1, 2, 3] for the first case (course 0 has no prerequisites, unlocks 1 and 2, which both unlock 3) and [] for the second (a two-course cycle where neither course ever reaches indegree zero).

Key points

• The indegree count is exactly "how many prerequisites this course is still waiting on"; a course only becomes eligible once that count hits zero.
• Multiple valid orders can exist whenever more than one course is simultaneously eligible; if a canonical, reproducible order matters (for example a deterministic build or test replay), swap the queue for a min-heap to always take the smallest eligible course id next, which costs $O(\log k)$ per pop instead of $O(1)$, where $k$ is the number of currently eligible courses.
• A directed acyclic graph (DAG) is the name for the acyclic case that always has at least one valid topological order; the moment a cycle exists, no such order can exist for the courses on that cycle.

Complexity

Time: $O(V + E)$ where $V$ is the number of courses and $E$ is the number of prerequisite pairs (each course and each edge is processed exactly once). Space: $O(V + E)$ for the adjacency list and indegree array.

Edge cases

• Disconnected components or isolated courses (no prerequisites and nothing depends on them) are scheduled immediately, since their indegree starts at zero.
• A course listed as its own prerequisite is a one-node cycle and is caught by the same length check.
• Duplicate prerequisite pairs inflate the indegree count but don't change correctness, since the count still reaches zero at the same logical point (one extra decrement per duplicate, which the duplicate edge itself supplies).
• An empty prerequisite list means every order of the courses is valid.
• Checking only "did the queue run empty" without also checking that the output length equals the course count is the most common bug: a graph can have one small cycle alongside many unrelated, fully resolvable courses, and skipping the length check silently returns an incomplete, invalid order.

Direct answer

Count frequencies first, then either maintain a min-heap of size k as you scan the counted items (evicting the smallest whenever the heap grows past k), or bucket the items by frequency and read off the top k directly. The heap approach costs $O(n \log k)$ time; the bucket approach costs $O(n)$ time but needs frequency values that are bounded by the input size. When k is very small relative to the number of distinct items, the heap wins because $\log k$ is tiny; when k is not small (approaching the number of distinct items), bucket sort's flat $O(n)$ bound stops paying a per-item $\log k$ penalty at all.

Structured elaboration

Heap of size k

Count every item's frequency (a single pass, $O(n)$). Then walk the distinct items, pushing each (frequency, value) pair onto a min-heap; once the heap holds k pairs, only push a new one if its frequency beats the current minimum, evicting that minimum first. The heap never holds more than k pairs at once, so each push or evict is $O(\log k)$, and there are at most one distinct-items-count many of them.

Bucket sort by frequency

Frequencies in a collection of n items are themselves bounded by n (an item can appear at most n times), so you can allocate n+1 buckets indexed directly by frequency and drop each distinct item into buckets[its frequency]. Reading buckets from the highest index down and collecting values until you have k of them is $O(n)$ total: no comparisons, no heap, just direct indexing.

When to prefer which

• k very small relative to distinct-item count: the heap's $O(n \log k)$ is close to $O(n)$ since $\log k$ is small, and it avoids allocating an array sized to the full item count the way the bucket approach does.
• k not small (comparable to the number of distinct items): the bucket approach's flat $O(n)$ bound no longer pays any per-item logarithmic penalty, while the heap's $\log k$ factor grows along with k; bucket sort becomes the clearly faster choice.
• Frequencies not naturally bounded by n (for example, if you were instead ranking by an unbounded external weight rather than a count derived from the input itself), bucket sort's indexing assumption breaks down and the heap approach generalizes more directly.

Worked example

import heapq
from collections import Counter


def top_k_frequent_heap(items: list[str], k: int) -> list[str]:
    """
    Min-heap of size k keyed by frequency. O(n log k) time, O(n) space
    for the frequency table plus O(k) for the heap.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    heap: list[tuple[int, str]] = []
    for value, freq in counts.items():
        if len(heap) < k:
            heapq.heappush(heap, (freq, value))
        elif freq > heap[0][0]:
            heapq.heapreplace(heap, (freq, value))
    heap.sort(reverse=True)
    return [value for _, value in heap]


def top_k_frequent_bucket(items: list[str], k: int) -> list[str]:
    """
    Bucket sort by frequency. O(n) time, O(n) space.
    Bucket index = frequency (bounded by len(items)), so no comparison sort
    is needed once counts are known.
    """
    if k <= 0:
        return []
    counts = Counter(items)
    buckets: list[list[str]] = [[] for _ in range(len(items) + 1)]
    for value, freq in counts.items():
        buckets[freq].append(value)
    result: list[str] = []
    for freq in range(len(buckets) - 1, 0, -1):
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result


if __name__ == "__main__":
    data = ["a", "b", "a", "c", "b", "a", "d"]
    print("heap:", top_k_frequent_heap(data, 2))
    print("bucket:", top_k_frequent_bucket(data, 2))

Running this prints:

heap: ['a', 'b']
bucket: ['a', 'b']

For ["a","b","a","c","b","a","d"], the frequencies are a:3, b:2, c:1, d:1. Both the size-2 min-heap and the bucket-sort approach correctly identify a and b as the two most frequent items, agreeing with each other as they must, since both are computing the same top-k set from the same frequency counts.

Complexity

• Heap of size k: time $O(n \log k)$ (counting is $O(n)$, each of up to n distinct-item heap operations is $O(\log k)$); space $O(n)$ for the frequency table plus $O(k)$ for the heap.
• Bucket sort: time $O(n)$ (counting plus a single pass over buckets); space $O(n)$ for the frequency table plus the bucket array.

Edge cases

• k equal to the number of distinct items should return all of them.
• Ties in frequency mean the "top k" set is well-defined but the specific order among tied items is not, unless a tie-break rule (for example, lower value first) is specified.
• k=0 should return an empty result rather than erroring or returning one item.
• An empty input collection should return an empty result for any k.

Trade-offs & pitfalls

A common wrong turn is defaulting to a full sort of all distinct items by frequency ($O(n \log n)$ on the number of distinct items) instead of recognizing that only the top k are needed, which is exactly what both the heap-of-size-k and bucket-sort approaches avoid paying for. A second common gap is not noticing that bucket sort's efficiency depends on frequencies being bounded by a value proportional to n; presenting it as a universal replacement for the heap approach without that caveat overstates its applicability. For the streaming follow-up this question absorbs, only the heap approach adapts directly: a size-k heap can be updated incrementally as frequencies change, while bucket sort assumes all counts are known before you build the buckets and does not update as cheaply if counts keep shifting.