Algorithmic Problem-Solving and Data Structure Selection Questions

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

Reach for a hash map whenever you need the fastest average lookup, insert, and delete and do not care about the order keys come out in. Reach for an ordered structure (a balanced binary search tree, BST for short, meaning a tree kept balanced so its height stays logarithmic; or a skip list, a linked structure with multiple randomly-built "express lane" levels that gives logarithmic search without needing tree rebalancing) whenever you need range queries, sorted iteration, or predecessor/successor lookups, since a hash map fundamentally cannot answer those without scanning every entry.

Structured elaboration

Concrete case where a hash map wins: an in-memory cache keyed by an exact request signature, for example caching a computed response by its full input hash, where every lookup is "does this exact key exist" and there is no notion of "keys near this one" that would ever be queried. The $O(1)$ average lookup directly minimizes latency, and there is nothing to give up, since ordering was never needed.

Concrete case where giving up hash-map speed pays off: a scheduler that needs "the next event after this timestamp." That is a successor query, unsupported by a hash map without scanning every key, but native to an ordered structure in $O(\log n)$. Trading average-case $O(1)$ for guaranteed $O(\log n)$ is a clear win here because the operation the hash map cannot do at all is the operation the system needs on every scheduling step.

Trade-offs & pitfalls

A hash map's worst-case degrades to $O(n)$ under pathological collisions, though modern implementations mitigate this with randomized hash seeding; an ordered structure's $O(\log n)$ is a hard guarantee regardless of key distribution, which matters if an adversary can influence which keys get inserted (for example, in a public-facing API). A common mistake is reaching for an ordered structure "just in case sorted output is needed later," which pays the $O(\log n)$ tax on every single operation for a benefit that may never be used; the right trigger is a concrete, recurring range or predecessor/successor query in the actual access pattern, not a hypothetical one. It is also common to forget that some hash map implementations preserve insertion order as an incidental property (not a sorted, comparison-based order), which is a much weaker guarantee than a true ordered structure's ability to iterate or range-query by key value.

Direct answer

Reach for a self-balancing tree over a hash table specifically when ordered iteration, range queries, or a worst-case (not just average-case) time guarantee is needed; a hash table's O(1) average lookup has no built-in notion of order and can degrade to O(n) in the worst case, while a balanced tree guarantees O(log n) for every operation and keeps keys in sorted order at all times. When only point lookups are ever needed, and order, range, and worst-case behavior never matter, the balancing overhead of a tree buys nothing and a hash table is strictly cheaper.

Structured elaboration

What a hash table fundamentally cannot give you

• Ordered iteration: walking a hash table's contents comes out in whatever order the hash function and internal layout produced, not sorted order; a balanced tree's in-order traversal is always sorted.
• Range queries: "give me every key between A and B," or "find the next key after X" (predecessor/successor), requires either scanning the entire hash table or maintaining a second sorted structure; a balanced tree answers both in O(log n + m), where m is the number of results returned.
• Worst-case guarantees: a hash table's O(1) average case relies on the hash function spreading keys evenly. A pathological input, or an attacker deliberately choosing keys (a hash-flooding attack), can degrade every operation to O(n) in the worst case. A balanced tree's O(log n) bound holds for every input, not just typical ones, because it comes from the tree's structural invariant, not from statistical spread.

AVL vs red-black: two ways to bound the height

Because AVL keeps a tighter height bound, point lookups are on average slightly faster (fewer comparisons); because red-black tolerates more imbalance before rotating, insert and delete are on average cheaper. Neither difference is large in practice, and both are asymptotically O(log n); the choice matters more in workloads with extreme read/write ratios than in typical applications.

When the balancing overhead isn't worth paying

• Point-lookup-only workloads (caches, sets, deduplication) with no ordering or range needs: use a hash table.
• On-disk storage, such as database indexes: neither AVL nor red-black trees are the right structure at all. A B-tree (a tree with a much higher branching factor than a binary tree, so each node holds many keys) is preferred for on-disk indexes because it minimizes the number of disk-block reads: each node read is one I/O, and a wide branching factor means far fewer levels than a binary tree for the same key count. An in-memory red-black or AVL tree assumes uniformly cheap pointer-chasing, which doesn't hold once each node access might be a disk seek.

Worked example

For n = 1,000,000 keys, the exact minimum-node recurrence for AVL trees (the same Fibonacci-like relation used to derive the roughly 1.44 log2 n bound) gives a provable worst-case height of 27: an AVL tree needs at least 832,039 nodes to reach height 27, so 1,000,000 nodes cannot exceed height 27. The classical red-black bound, $2 \log_2(n+1)$, evaluates to about 39.86 for the same n, so at most 39. For comparison, an ideal perfectly balanced binary tree has height floor(log2(1,000,000)) = 19, and a plain unbalanced binary search tree (BST, a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys) built from sorted-order inserts degrades to height 999,999 (a straight chain).

import math

def max_avl_height_for_n(n):
    min_nodes = {-1: 0, 0: 1}
    h = 0
    while min_nodes[h] <= n:
        h += 1
        min_nodes[h] = min_nodes[h - 1] + min_nodes[h - 2] + 1
    return h - 1, min_nodes[h - 1]

n = 1_000_000
avl_h, avl_min_nodes = max_avl_height_for_n(n)
rb_bound = 2 * math.log2(n + 1)
print(f"ideal height: {math.floor(math.log2(n))}")
print(f"AVL worst-case height: {avl_h} (needs >= {avl_min_nodes:,} nodes)")
print(f"red-black worst-case height bound: {rb_bound:.2f} -> at most {math.floor(rb_bound)}")
print(f"unbalanced BST worst case: {n - 1:,}")

prints:

ideal height: 19
AVL worst-case height: 27 (needs >= 832,039 nodes)
red-black worst-case height bound: 39.86 -> at most 39
unbalanced BST worst case: 999,999

All four numbers describe worst-case comparisons for a single lookup on the same one million keys; the practical takeaway is that both AVL and red-black stay within roughly 2x of the theoretical minimum even in their worst case, while an unbalanced BST has no such guarantee at all.

Trade-offs & pitfalls

A hash table with open addressing or chaining still needs periodic resizing to keep its average O(1) guarantee, and a resize is an O(n) operation, though amortized (its cost spread evenly across the many O(1) inserts that led to it) over the sequence of inserts that triggered it, similar in spirit to how a dynamic array's occasional resize is amortized across its appends.

Concurrent access: red-black trees are generally easier to adapt to concurrent or lock-free implementations than AVL trees, because their rebalancing needs fewer structural changes per insert.

A common mistake is defaulting to a balanced tree "for safety" when a hash table would do, paying O(log n) for every operation when O(1) average was available and ordering was never actually needed. The opposite mistake is relying on a hash table's average-case guarantee in a context where an adversary controls the keys, for example a public API accepting arbitrary user-supplied strings as hash keys, where the worst case is a real risk rather than a theoretical one.

Direct answer

Quickselect adapts quicksort's partitioning to find just the k-th largest element without fully sorting: after one partition step around a pivot, the pivot's final position tells you whether the answer lies to its left or right, so you only ever recurse into one side instead of both. That halves (in expectation) the work at each level rather than branching into two recursive calls, which is what brings the expected time down from sorting's $O(n \log n)$ to $O(n)$. A heap of size k is the better choice instead when you cannot, or do not want to, mutate the input in place, or when the data arrives as a stream and you need the running top-k as you go rather than a single final answer.

Structured elaboration

Why quickselect is expected O(n)

A single partition around a random pivot costs $O(n)$ and places the pivot at its correct sorted position, with everything smaller to its left and everything larger to its right. If that position is the one you are looking for, you are done; otherwise you recurse into only the one side that must contain the target index, discarding the other side's work entirely. With a reasonably balanced pivot (true on average for a random pivot), the total expected work follows the recurrence $T(n) = T\!\left(\frac{n}{2}\right) + O(n) = O(n)$ (expected), the same halving-geometric-series pattern that makes binary search $O(\log n)$, except here the per-level cost is $O(n)$ rather than $O(1)$, and only one recursive branch is taken rather than a binary search's implicit single branch. This is the key difference from quicksort, which must recurse into both sides to sort everything, giving $O(n \log n)$.

Why a heap of size k instead

• Streaming input: if elements arrive one at a time and you must always be able to report the current top k, quickselect does not apply directly, since it needs the whole array in hand to partition; a size-k min-heap updates in $O(\log k)$ per new element and always reflects the current top k.
• Avoiding in-place mutation: quickselect partitions the input array in place; if the caller cannot have their array reordered, a heap that only reads elements avoids that side effect (at the cost of $O(k)$ extra space).
• Worst-case guarantee: a naive quickselect has a worst case of $O(n^2)$ on an adversarial or unlucky pivot sequence (randomizing the pivot choice makes this astronomically unlikely, not impossible); a heap of size k guarantees $O(n \log k)$ in every case.
• k close to n: when k is large relative to n, a heap of size k approaches $O(k)$ extra space that is not much smaller than the array itself, and quickselect's in-place approach becomes the more memory-efficient option; when k is small, the heap's small extra space is a non-issue and its worst-case guarantee is attractive.

A related, absorbed framing: this is a selection-algorithm family, not a one-off trick

The same "avoid a full sort" idea generalizes. Finding the k-th smallest value in a matrix whose rows and columns are each sorted uses a min-heap over the smallest untried cell in each row (or a binary search directly over the value range, counting how many matrix entries are $\le$ a candidate value in $O(n)$ per probe) rather than flattening and sorting the whole matrix. And when memory, not just time, is the binding constraint (as in a memory-constrained k-smallest-elements variant), quickselect's in-place partitioning is preferable to a heap precisely because it needs no auxiliary structure beyond the input array itself.

Worked example

import heapq
import random


def kth_largest_quickselect(nums: list[int], k: int) -> int:
    """
    Return the k-th largest value (k=1 is the maximum).
    Expected O(n) time, O(1) extra space (in-place partition, iterative).
    Worst case O(n^2) on adversarial pivots; randomized pivot makes that
    astronomically unlikely rather than eliminating it.
    """
    if not (1 <= k <= len(nums)):
        raise ValueError("k out of range")
    target = len(nums) - k  # index of the k-th largest in sorted-ascending order
    lo, hi = 0, len(nums) - 1
    while True:
        pivot_idx = random.randint(lo, hi)
        nums[pivot_idx], nums[hi] = nums[hi], nums[pivot_idx]
        pivot = nums[hi]
        store = lo
        for i in range(lo, hi):
            if nums[i] < pivot:
                nums[i], nums[store] = nums[store], nums[i]
                store += 1
        nums[store], nums[hi] = nums[hi], nums[store]
        if store == target:
            return nums[store]
        elif store < target:
            lo = store + 1
        else:
            hi = store - 1


def kth_largest_heap(nums: list[int], k: int) -> int:
    """Min-heap of size k. O(n log k) time, O(k) space."""
    heap: list[int] = []
    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)
    return heap[0]


if __name__ == "__main__":
    random.seed(0)
    data = [3, 2, 1, 5, 6, 4]
    print("quickselect k=2:", kth_largest_quickselect(data.copy(), 2))
    print("heap k=2:", kth_largest_heap(data, 2))
    bigger = [7, 10, 4, 3, 20, 15]
    print("quickselect k=3:", kth_largest_quickselect(bigger.copy(), 3))
    print("heap k=3:", kth_largest_heap(bigger, 3))

Running this prints:

quickselect k=2: 5
heap k=2: 5
quickselect k=3: 10
heap k=3: 10

For [3, 2, 1, 5, 6, 4] sorted descending (6, 5, 4, 3, 2, 1), the 2nd largest is 5, and both methods agree. For [7, 10, 4, 3, 20, 15] sorted descending (20, 15, 10, 7, 4, 3), the 3rd largest is 10, and again both methods agree. The pivot choices inside quickselect are randomized but seeded (random.seed(0)), so this exact sequence of calls reproduces this exact output every time it is run.

Complexity

• Quickselect: expected time $O(n)$, worst case $O(n^2)$; space $O(1)$ extra (partitions in place, iteratively rather than recursively here).
• Heap of size k: time $O(n \log k)$ in every case; space $O(k)$ for the heap.

Edge cases

• k outside the range [1, len(nums)] is invalid input and should raise rather than silently returning a wrong value.
• Duplicate values are handled correctly by both methods, since partitioning and heap comparisons work on values, not identity.
• k equal to 1 (the maximum) or k equal to n (the minimum) are valid boundary cases worth checking by hand.
• An already-sorted or reverse-sorted array is exactly the input that most threatens a non-randomized quickselect's worst case; randomizing the pivot is what defends against it.

Trade-offs & pitfalls

The most common wrong turn is presenting quickselect as strictly superior because of its better expected time, without naming its $O(n^2)$ worst case or its requirement to mutate the input array in place; both are real costs that the heap approach avoids. A second common gap is forgetting that quickselect only gives you the k-th value itself, not the k values above it in order: if you also need the actual top-k list, you still need one more pass (or a heap) to collect everything on the correct side of the final partition. A third pitfall, specific to this absorbed question family, is treating "kth largest in an array" and "kth smallest in a sorted matrix" as needing the same algorithm: the matrix's extra structure (both rows and columns already sorted) is exactly what makes a heap-over-candidate-cells or binary-search-over-values approach effective there, and quickselect's partitioning does not directly apply to a two-dimensional sorted structure the same way.

Direct answer

Group strings that are anagrams of each other by mapping each string to a canonical key that is identical for all its anagrams and different otherwise, then bucket by that key in a hash map. A sorted-characters key ("eat" -> "aet") is simple but costs $O(k \log k)$ per string of length k; a fixed-alphabet character-frequency key (a 26-length count tuple for lowercase letters) costs only $O(k)$ per string, so it scales better as strings get longer.

Structured elaboration

Approach 1: sorted-string key, $O(n \cdot k \log k)$ total for n strings of average length k.

from collections import defaultdict

def group_anagrams_sorted(strs):
    """Group anagrams using sorted-characters string as key. O(N*K log K) time."""
    buckets = defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        buckets[key].append(s)
    return list(buckets.values())

Approach 2: character-frequency key, $O(n \cdot k)$ total, avoiding the sort entirely by counting occurrences directly into a fixed-size tuple.

def group_anagrams_count(strs):
    """Group anagrams using a 26-length character-count tuple as key (lowercase a-z). O(N*K) time."""
    buckets = {}
    for s in strs:
        counts = [0] * 26
        for ch in s:
            counts[ord(ch) - 97] += 1
        key = tuple(counts)
        buckets.setdefault(key, []).append(s)
    return list(buckets.values())

The same technique applies at smaller and larger granularities than "group a whole list":

• Pairwise check ("are these two strings anagrams of each other"): compare the frequency keys of just the two strings directly, with no bucketing map needed at all, using collections.Counter as the frequency map.
• Anagram-substring start indices ("find all anagram-substring start indices" of a pattern p inside a longer string s): instead of computing one static key per whole string, slide a fixed-width window of length len(p) across s and maintain a running frequency counter for the window, comparing it against the target frequency counter for p at every position. This is the identical character-frequency-key idea, just recomputed incrementally as the window shifts by one character (add the entering character, remove the leaving character) instead of being built once per string.

from collections import Counter

def are_anagrams(a, b):
    """Pairwise anagram check using the same frequency-key technique."""
    return Counter(a) == Counter(b)

def find_anagram_starts(s, p):
    """
    Return start indices in s where a length-len(p) substring is an anagram
    of p, via a sliding window over frequency counters. O(len(s)) time.
    """
    n, k = len(s), len(p)
    if k > n:
        return []
    target = Counter(p)
    window = Counter(s[:k])
    result = []
    if window == target:
        result.append(0)
    for i in range(k, n):
        window[s[i]] += 1
        left = s[i - k]
        window[left] -= 1
        if window[left] == 0:
            del window[left]
        if window == target:
            result.append(i - k + 1)
    return result

Worked example

words = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams_sorted(words))
print(group_anagrams_count(words))
print(are_anagrams("listen", "silent"))
print(are_anagrams("listen", "silence"))
print(find_anagram_starts("cbaebabacd", "abc"))

Output:

[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
True
False
[0, 6]

Both grouping approaches produce the same three buckets. The pairwise check confirms "listen"/"silent" share a frequency key but "listen"/"silence" do not (different lengths, so different key). The sliding-window scan over "cbaebabacd" finds two anagram-of-"abc" windows, starting at index 0 ("cba") and index 6 ("bac").

Trade-offs & pitfalls

Key points

• Sorting is simple and works for any character set (Unicode included) without modification, but its $O(k \log k)$ per-string cost dominates once k grows large.
• The count-key avoids sorting entirely, dropping the per-string cost to $O(k)$, but as written it assumes a small fixed alphabet (lowercase a-z); for full Unicode you would key on a dictionary or Counter-derived frozen structure instead of a fixed 26-length tuple, which adds some hashing overhead per distinct character but keeps the linear-in-k scaling.
• Both approaches store $O(n \cdot k)$ total data across all buckets and keys.

Complexity

• Sorted-key grouping: time $O(n \cdot k \log k)$, space $O(n \cdot k)$.
• Count-key grouping: time $O(n \cdot k)$, space $O(n \cdot k)$.
• Sliding-window substring search: time $O(n)$ where n is the length of the longer string (constant-size alphabet keeps each window comparison O(1) amortized), space $O(1)$ for the counters (bounded by alphabet size).

Edge cases

• Empty strings: sorted("") is "" and an all-zero count tuple, both hash consistently, so empty strings correctly bucket with other empty strings.
• Case sensitivity and Unicode: decide up front whether "Eat" and "eat" should be treated as anagrams; normalize case before keying if not, and switch the count-key from a fixed 26-slot array to a Counter/dict for non-ASCII input.
• Pattern longer than the source string in the substring-search variant: return an empty result immediately rather than sliding a window that cannot fit.