Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Push every opening bracket onto a stack. On a closing bracket, it must match whatever opener currently sits on top of the stack; if it does not, or the stack is already empty, the string is invalid. After the scan, the string is valid only if the stack is empty, meaning every opener found a partner. This runs in $O(n)$ time and $O(n)$ space.

Structured elaboration

A stack models "the most recently opened, still-unclosed bracket" exactly, because it is last-in-first-out (LIFO): whichever opener was pushed most recently is always the one that must be closed next, and that is precisely what sits on top. Checking a closer against the top of the stack is an $O(1)$ lookup through a small mapping () pairs with (, ] with [, } with {).

Counting bracket types separately (how many ( versus how many )) is not enough: a string can have perfectly equal counts of every bracket type and still be invalid because the nesting order is wrong, for example ([)]. Only a structure that remembers order, like a stack, can catch that.

Worked example

def is_valid_brackets(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack: list[str] = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack[-1] != pairs[ch]:
                return False
            stack.pop()
    return not stack


if __name__ == "__main__":
    tests = ["()[]{}", "(]", "([)]", "{[]}"]
    print([is_valid_brackets(t) for t in tests])

Running this prints [True, False, False, True]. Trace ([)]: push (, push [, then see ); the top of the stack is [, which does not pair with ), so the function returns False immediately, even though the overall bracket counts are balanced.

Complexity

Time: $O(n)$, one pass over the string doing $O(1)$ work per character.
Space: $O(n)$ worst case, since a string of all opening brackets pushes every character onto the stack before the scan ends.

Edge cases

• Empty string: the stack never receives a push, so it is empty at the end and the function correctly returns True.
• A lone unmatched opening bracket at the very end: the stack is non-empty when the scan finishes, so the final not stack check (not just the per-character comparisons) is what catches it.
• A closing bracket with nothing open: stack is empty when a closer arrives, so the code must check not stack before indexing stack[-1], or it raises instead of returning False cleanly.

Trade-offs & pitfalls

Using a single stack with a pairs mapping generalizes cleanly to any number of bracket types; writing a separate counter per bracket type cannot detect ordering violations no matter how many counters you add.

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.

Direct answer

Reverse the whole array, then reverse the first k elements and the remaining n-k elements separately; three linear passes compose into the fully rotated result with no auxiliary array. The same reversal trick generalizes directly: reversing a string in place is the identical two-pointer, swap-from-both-ends routine, and rotating a square matrix 90 degrees in place is a transpose followed by reversing each row, both built on the same in-place-swap primitive as the array rotation.

Structured elaboration

Why three reversals produce a rotation. Reversing the entire array puts every element in fully reversed order. Reversing the first k elements of that reversed array un-reverses exactly the block that should now sit at the front, restoring its original relative order; reversing the remaining n-k elements does the same for the remainder. Normalizing with k %= n handles k values larger than the array's length or equal to zero.

Generalizing to a string. The same in-place two-pointer swap from both ends is exactly what reverses a string, provided the string is held in a mutable container (a list of characters, for example, since Python's own string type is immutable and cannot be reversed truly in place without first converting it).

Generalizing to a square matrix. Transposing swaps matrix[i][j] with matrix[j][i] for every i < j, turning rows into columns. Reversing each row afterward flips left to right. Combined, what was the first column read top to bottom becomes the first row read left to right, which is exactly a 90-degree clockwise turn.

Related in-place-preprocessing techniques (with an honest space caveat). Prefix-sum preprocessing builds an auxiliary array once, in $O(n)$ time, so that any later range-sum query answers in $O(1)$; this trades $O(n)$ extra space for fast queries, so it is not itself an O(1)-extra-space technique, even though it shares this family's "one linear pass, reuse the result" character. Product-except-self, by contrast, genuinely can be done with O(1) extra space beyond the required output array: a first pass fills the output with the running product of everything to each index's left, and a second pass multiplies in the running product of everything to that index's right, needing no separate auxiliary array at all.

Worked example

def rotate_array(nums: list[int], k: int) -> None:
    n = len(nums)
    if n <= 1:
        return
    k %= n
    if k == 0:
        return

    def reverse(i, j):
        while i < j:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
            j -= 1

    reverse(0, n - 1)
    reverse(0, k - 1)
    reverse(k, n - 1)


def reverse_string_inplace(chars: list[str]) -> None:
    i, j = 0, len(chars) - 1
    while i < j:
        chars[i], chars[j] = chars[j], chars[i]
        i += 1
        j -= 1


def rotate_matrix_90_cw_inplace(matrix: list[list[int]]) -> None:
    n = len(matrix)
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    for row in matrix:
        row.reverse()


if __name__ == "__main__":
    arr = [1, 2, 3, 4, 5, 6, 7]
    rotate_array(arr, 3)
    print(arr)

    chars = list("hello")
    reverse_string_inplace(chars)
    print("".join(chars))

    m = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    rotate_matrix_90_cw_inplace(m)
    print(m)

Running this prints [5, 6, 7, 1, 2, 3, 4], then olleh, then [[7, 4, 1], [8, 5, 2], [9, 6, 3]].

Complexity

rotate_array: time $O(n)$ for the three reversal passes, since they compose additively into a single linear scan rather than multiplying; space $O(1)$ extra, using only the two index pointers inside each reversal call.
reverse_string_inplace: time $O(n)$, one pass with two pointers closing in from both ends; space $O(1)$ extra beyond the mutable character list itself.
rotate_matrix_90_cw_inplace: time $O(n^2)$ for an n-by-n matrix, since the transpose visits each of the $n^2$ cells once; space $O(1)$ extra, since both the transpose and the row reversals swap in place with no auxiliary matrix.

Edge cases

• k = 0, or k a multiple of the array's length once normalized via k %= n: rotate_array detects this and returns immediately without performing any reversals, since the array is already in its correct rotated position.
• Empty or single-element array or string: both rotate_array (via its n <= 1 guard) and reverse_string_inplace (via while i < j never firing) return immediately with nothing to do.
• A non-square matrix passed to rotate_matrix_90_cw_inplace: this implementation assumes a square matrix, and a non-square transpose changes the matrix's dimensions, so it cannot be rotated true in place this way.

Trade-offs & pitfalls

Forgetting k %= n for a k larger than the array's length either wastes work or, in a careless implementation, indexes out of range. The transpose-then-reverse-rows trick only works for a square matrix: transposing a non-square matrix changes its dimensions, so a genuinely non-square rotation needs a separate output buffer rather than a true in-place transform. Python's string immutability means a real in-place string reversal needs a mutable container (a list of characters, or a bytearray) first; there is no way to mutate a str object's characters directly.

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

Use binary (fast) exponentiation: repeatedly square the base and, on each bit of n that is set, multiply that squared value into the running result. This computes $x^n$ in O(log|n|) multiplications instead of O(n). A negative exponent is handled by inverting the base once up front (1/x) and treating the exponent as positive from then on.

Structured elaboration

Core idea: writing n in binary decomposes the power into a product of the base raised to each power-of-two position where n has a set bit:
$x^n = \prod_{i \,:\, \text{bit}_i(n)=1} x^{2^i}$
Squaring the base once per bit position produces exactly the $x^{2^i}$ terms needed, in the same single pass that reads the bits of n.

def my_pow(x: float, n: int) -> float:
    """
    Compute x**n via binary (fast) exponentiation in O(log|n|) time, O(1) space.
    Handles negative exponents and the 32-bit min-int edge case (in fixed-width languages).
    """
    if x == 0.0:
        if n > 0:
            return 0.0
        if n == 0:
            return 1.0
        raise ZeroDivisionError("0 cannot be raised to a negative power")

    exponent = n
    base = x
    if exponent < 0:
        base = 1.0 / base
        exponent = -exponent

    result = 1.0
    while exponent:
        if exponent & 1:
            result *= base
        base *= base
        exponent >>= 1
    return result


print(my_pow(2.0, 10))
print(my_pow(2.0, -3))
print(my_pow(3.0, 0))
print(my_pow(-2.0, 5))

Output:

1024.0
0.125
1.0
-32.0

Negative-exponent handling: invert x once, negate n, and reuse the same positive-exponent loop; in Python this negation is always safe since ints are arbitrary precision, but in a fixed-width 32-bit language, the most negative representable exponent must first be widened to a 64-bit type before negating it, since negating it directly overflows.

Worked example

Tracing $x=2, n=10$ (binary 1010) bit by bit:

The two set bits (positions 1 and 3) contribute $x^{2^1} \cdot x^{2^3} = 4 \cdot 256 = 1024 = 2^{10}$, matching the printed result exactly.

Complexity

$O(\log|n|)$ time, $O(1)$ space for the iterative version above (a recursive version instead
uses $O(\log|n|)$ call-stack space).

Edge cases

• n = 0: the while exponent loop never executes (exponent starts at 0), returning
  result = 1.0, matching my_pow(3.0, 0) -> 1.0.
• x = 0, n > 0: explicitly special-cased to return 0.0 before the main loop.
• x = 0, n = 0: explicitly special-cased to return 1.0 by convention.
• x = 0, n < 0: explicitly raises ZeroDivisionError, since 0 to a negative power is
  mathematically undefined; this must be special-cased rather than silently returning infinity
  or crashing with an unclear error.
• Negative base: sign is preserved correctly through repeated squaring and multiplication,
  e.g. my_pow(-2.0, 5) = -32.0.
• Most-negative fixed-width exponent (e.g. INT32_MIN): not an issue for Python's
  arbitrary-precision ints, but in a fixed-width 32-bit language the most negative representable
  exponent must be widened to a 64-bit type before negating it, since negating it directly
  overflows.

Trade-offs & pitfalls

• Floating-point precision: repeated squaring compounds rounding error faster than repeated multiplication in some regimes; for |x| very close to 1 raised to a huge power, or extreme |n| combined with |x| far from 1, relative error can grow. Computing via exp(n * log(x)) is an alternative when raw precision matters more than speed, but that requires x > 0 (log is undefined otherwise) and introduces its own rounding from the exp/log calls.
• Modular exponentiation: if the actual need is $x^n \bmod m$ (as in cryptographic-sized exponents), the accumulation step becomes (result * base) % m at every multiply, keeping every intermediate value bounded to a fixed size instead of letting a plain big-integer power grow unboundedly large.