Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

For this kind of general, range-unknown input, I would implement randomized in-place quicksort: pick a uniformly random pivot at each partition step (to defeat adversarial or already-sorted inputs), partition with Lomuto's scheme, and always continue on the smaller of the two resulting partitions while deferring the larger one, which bounds recursion/stack depth to O(log n). Quicksort is the right default here over merge sort (which needs O(n) extra space) or counting sort (which needs a small, known key range).

Structured elaboration

Why quicksort for this input: it sorts in place (O(log n) extra memory instead of merge sort's O(n)), its sequential partition scan is cache-friendly and typically fastest in practice, and it makes no assumption about the range of the keys, unlike counting sort.

Partition step (Lomuto): move the pivot to the end, then walk the range once, swapping any element smaller than the pivot into a growing "less-than" prefix; finally swap the pivot into its correct final position.

Random pivot selection removes the classic O(n^2) worst case that a fixed first/last-element pivot suffers on already-sorted or reverse-sorted input.

import random

def quicksort_inplace(a: list[int], seed: int = 0) -> None:
    """
    Randomized in-place quicksort with Lomuto partitioning.
    Always recurses on the smaller side and loops on the larger side
    (via an explicit stack) to bound auxiliary depth at O(log n).
    """
    rng = random.Random(seed)

    def partition(lo: int, hi: int) -> int:
        pivot_idx = rng.randint(lo, hi)
        a[pivot_idx], a[hi] = a[hi], a[pivot_idx]
        pivot = a[hi]
        store = lo
        for i in range(lo, hi):
            if a[i] < pivot:
                a[store], a[i] = a[i], a[store]
                store += 1
        a[store], a[hi] = a[hi], a[store]
        return store

    lo, hi = 0, len(a) - 1
    stack = [(lo, hi)]
    while stack:
        lo, hi = stack.pop()
        while lo < hi:
            p = partition(lo, hi)
            left_size = p - lo
            right_size = hi - p
            if left_size < right_size:
                stack.append((p + 1, hi))
                hi = p - 1
            else:
                stack.append((lo, p - 1))
                lo = p + 1


data = [5, 2, 9, 1, 5, 6, 3, 8, 2, 0, -4, 7]
quicksort_inplace(data, seed=42)
print(data)

data2 = []
quicksort_inplace(data2, seed=42)
print(data2)

data3 = [1]
quicksort_inplace(data3, seed=42)
print(data3)

Output:

[-4, 0, 1, 2, 2, 3, 5, 5, 6, 7, 8, 9]
[]
[1]

Key points: continuing inline on the smaller partition (via the loop) while pushing only the larger one onto the explicit stack is what bounds the stack's maximum size to O(log n), since each level you push at least halves relative to its parent range.

Worked example

The input [5, 2, 9, 1, 5, 6, 3, 8, 2, 0, -4, 7] (note the repeated values 5 and 2) sorts correctly to [-4, 0, 1, 2, 2, 3, 5, 5, 6, 7, 8, 9] with seed 42, as shown in the run above; the duplicate values are handled fine by Lomuto's plain "<" comparison, since equal elements simply land in the "not less than pivot" partition without needing any special casing.

Complexity

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.

Direct answer

Walk the list once, and at each node redirect its next reference back to the previous node before advancing, using three tracking references: previous, current, and a temporary save of current's original next. This is $O(n)$ time and $O(1)$ space. A recursive version expresses the identical rewiring, handling everything after the current node first and then flipping the one link back, but it pays for that with $O(n)$ call-stack space that the iterative version does not need.

Structured elaboration

The iterative three-pointer dance. Before overwriting curr.next, save it in a temporary variable, or the rest of the list is lost permanently. Then point curr.next back at prev, advance prev to curr, and advance curr to the saved temporary. Repeat until curr is empty.

The recursive version. The base case is an empty list or a single remaining node, which is already "reversed" as-is. Otherwise, recursively reverse everything after the head first; that recursive call returns the new head of the whole reversed list. Then head.next.next = head flips the one link connecting the old head back into the newly-reversed remainder, and head.next = None prevents the old head from accidentally pointing at itself in a two-node cycle.

What language a solution is written in does not change any of this. The reskin into Python, JavaScript, Swift, or Kotlin, or building the linked-list node class from scratch first, is the same pointer-rewiring skill underneath; only the syntax for holding and dereferencing a reference changes, not the three-step relinking logic itself.

Worked example

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def reverse_iterative(head):
    prev = None
    curr = head
    while curr:
        next_tmp = curr.next  # save before overwriting
        curr.next = prev
        prev = curr
        curr = next_tmp
    return prev


def reverse_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def build_list(vals):
    dummy = Node(0)
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


if __name__ == "__main__":
    print(to_list(reverse_iterative(build_list([1, 2, 3, 4]))))
    print(to_list(reverse_recursive(build_list([1, 2, 3, 4]))))

Running this prints [4, 3, 2, 1] twice, once from each implementation.

Complexity

Time: $O(n)$ for both the iterative and recursive versions, since each one visits every node exactly once.
Space: $O(1)$ extra for the iterative version (three pointer variables regardless of list length); $O(n)$ for the recursive version, from the call stack, since the recursion descends one frame per node before any relinking happens.

Edge cases

• Empty list (head is None): both versions return None immediately without any relinking.
• Single-node list: both versions return that same node unchanged as the new head, since there is nothing to reverse.
• Very long list: the recursive version risks an actual stack overflow, since typical call-stack depth limits are far smaller than what a linked list can otherwise hold in memory.

Trade-offs & pitfalls

The recursive version risks an actual stack overflow on a very long list in production, not just an academic concern, since typical call-stack depth limits are far smaller than what a linked list or array can otherwise hold in memory. The single most common bug in the iterative version is forgetting to save curr.next before overwriting it, which permanently disconnects the rest of the list from anything still reachable.

Direct answer

A single depth-first search (DFS), augmented with a discovery-time array disc (when each vertex was first visited) and a low-link array low (the earliest discovery time reachable from that vertex's subtree using at most one edge that isn't a tree edge), finds articulation points and bridges in an undirected graph in $O(V + E)$. A structurally similar DFS, but with an explicit stack of "in-progress" vertices and using directed edges, finds strongly connected components (SCCs, maximal clusters where every node can reach every other node in the cluster) in a directed graph, also in $O(V + E)$. Both share the low-link idea and both do exactly one DFS, but they are not literally the same pass on the same graph: articulation points and bridges are an undirected-graph question, and strongly connected components is a directed-graph question, so which one applies depends on whether you're treating your edges as two-way or one-way.

Structured elaboration

Undirected graphs: articulation points and bridges

disc[v] is v's DFS visit order. low[v] is defined as:

$\text{low}[u] = \min\big(\text{disc}[u],\ \min_{w:(u,w)\text{ back-edge}} \text{disc}[w],\ \min_{v:(u,v)\text{ tree-edge}} \text{low}[v]\big)$

that is, the earliest thing u's own subtree can reach, either directly (a back edge straight to an ancestor) or through one of its DFS-tree children.

• Articulation point rule. The DFS root is an articulation point if and only if it has two or more DFS-tree children (removing it splits those children's subtrees apart). A non-root vertex u is an articulation point if it has a tree-edge child v with $\text{low}[v] \ge \text{disc}[u]$: that child's whole subtree cannot reach anything above u without passing through u itself.
• Bridge rule, same low-link values, a stricter comparison: a tree edge (u, v) is a bridge if $\text{low}[v] > \text{disc}[u]$ (strict): v's subtree cannot reach u or anything above u at all without that one edge, not even u itself.

Directed graphs: strongly connected components

Maintain an explicit stack of vertices currently on the current DFS path, plus an on_stack flag per vertex. The low-link rule changes in one important way: when considering an edge to an already-visited vertex w, you only fold in disc[w] if w is currently on the stack, not merely visited, since a visited-but-popped vertex belongs to an already-finished, unrelated component. When $\text{low}[u] = \text{disc}[u]$ after all of u's edges are explored, u is the root of a complete SCC: pop the stack down through and including u, and everyone popped is that component.

The "module dependency graph" framing maps onto this directly: if nodes are modules and edges are "depends on" relationships, an SCC with more than one node is a circular dependency cluster (module A eventually depends back on itself through some chain); a singleton SCC with no self-loop is a module with no circular dependency at all.

def articulation_points(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v); g[v].append(u)
    disc, low, is_ap, timer = [-1]*n, [0]*n, [False]*n, [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        children = 0
        for v in g[u]:
            if v == parent:
                continue
            if disc[v] == -1:
                children += 1
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if parent != -1 and low[v] >= disc[u]:
                    is_ap[u] = True
            else:
                low[u] = min(low[u], disc[v])
        if parent == -1 and children > 1:
            is_ap[u] = True

    for i in range(n):
        if disc[i] == -1:
            dfs(i, -1)
    return sorted(i for i in range(n) if is_ap[i])


def tarjan_scc(n, edges):
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v)
    disc, low, on_stack, stack, timer, sccs = [-1]*n, [0]*n, [False]*n, [], [0], []

    def dfs(u):
        disc[u] = low[u] = timer[0]; timer[0] += 1
        stack.append(u); on_stack[u] = True
        for v in g[u]:
            if disc[v] == -1:
                dfs(v)
                low[u] = min(low[u], low[v])
            elif on_stack[v]:
                low[u] = min(low[u], disc[v])
        if low[u] == disc[u]:
            comp = []
            while True:
                w = stack.pop(); on_stack[w] = False; comp.append(w)
                if w == u:
                    break
            sccs.append(sorted(comp))

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return sccs


bowtie_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 2)]
print(articulation_points(5, bowtie_edges))

directed_edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)]
print(tarjan_scc(6, directed_edges))

Worked example

For an undirected "bowtie" (two triangles sharing one vertex): edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,2), articulation_points(5, edges) returns [2], the shared vertex, since removing it disconnects the two triangles from each other.

For a directed graph modeling module dependencies with two independent cyclic clusters bridged by one one-way dependency: edges (0,1),(1,2),(2,0),(2,3),(3,4),(4,5),(5,3), tarjan_scc(6, edges) returns [[3, 4, 5], [0, 1, 2]]: two separate circular-dependency clusters (modules 0-1-2 and modules 3-4-5), connected only by the one-way edge from module 2 into module 3, so they are two SCCs, not one.

Complexity

Both articulation_points and tarjan_scc do a single DFS: the disc[i] == -1 guard means
each vertex is visited, and gets its dfs call, exactly once, so the outer loop plus all dfs
calls together do $O(V)$ work setting up and finishing each vertex. Inside dfs, the for v in g[u] loop examines each entry of each vertex's adjacency list exactly once; summed over
every vertex, that is $O(E)$ total (an undirected edge appears in two adjacency lists, still
$O(E)$ with a constant factor of 2). So total time is $O(V + E)$. Space is $O(V)$ for
disc/low/is_ap (or on_stack), plus $O(V)$ for the explicit stack (Tarjan's SCC) or the
recursion call stack (both algorithms), plus $O(V + E)$ for the adjacency-list representation
itself.

Edge cases

• Disconnected graph: the outer for i in range(n): if disc[i] == -1: dfs(i, -1) restarts
  DFS from every unvisited vertex, so each component gets its own DFS tree and its own
  root-special-case check.
• Self-loop ((u, u)) in articulation_points: g[u] gets u appended to it (from both
  sides of the edge); when dfs scans that entry, disc[u] is already set (to u's own
  discovery time) before the loop starts, so it falls into the else branch
  (low[u] = min(low[u], disc[u])), a harmless no-op since disc[u] can never be smaller than
  the low[u] it was initialized to.
• Single-vertex graph (n=1, no edges): dfs(0, -1) has no neighbors, children=0, so the
  root special case (children > 1) is false; articulation_points returns [] and
  tarjan_scc returns the single component [[0]].
• Empty graph (n=0): both outer loops run zero times, so both functions return [].
• Parallel edges between the same undirected pair: also flagged in Trade-offs below as
  breaking the naive "skip the parent by vertex id" rule, since it wrongly treats one of the
  parallel edges as a back edge to an ancestor.

Trade-offs & pitfalls

• The root special case is the most common articulation-point bug: the DFS root needs two or more tree-edge children, not just "has a child," to count as an articulation point.
• Bridge vs. articulation-point comparisons are easy to swap: bridges use the strict low[v] > disc[u], articulation points use the non-strict low[v] >= disc[u]. Mixing the two up silently misclassifies edges as bridges (or vertices as articulation points) that aren't.
• Parallel edges break the naive "skip the parent" rule for undirected graphs: if there are two edges between the same pair of vertices, skipping any edge back to parent by vertex id alone will wrongly treat one of the parallel edges as a back edge to an ancestor; tracking edge identity (not just the parent vertex) fixes this.
• For SCCs, checking disc[w] for any visited w instead of only vertices currently on_stack is a bug that silently merges vertices from different, already-finished DFS branches into the same low-link value, producing wrong components.
• Kosaraju's algorithm is the classic alternative for SCCs: two full DFS passes, one over the graph and one over its transpose, which is easier to reason about but costs an explicit graph transpose and a second full traversal, versus Tarjan's single pass with a stack.

Direct answer

A sorting algorithm is stable if it preserves the relative order of elements
that compare equal on the sort key. If two records tie on the key you sorted
by, a stable algorithm guarantees the one that came first in the input still
comes first in the output. This matters for multi-key sorts: if you sort by a
secondary key after already sorting by a primary one, stability is what lets
the primary ordering survive as a tiebreaker inside each secondary-key group.
Merge sort and Python's Timsort (the algorithm behind sorted() and list.sort())
are stable; classic in-place selection sort and a typical quicksort are not.

Structured elaboration

Why stability matters for multi-key sorts. The standard trick for sorting
by (primary key, secondary key) without writing a composite comparator is:
sort once by the primary key, then sort the result by the secondary key. This
only produces the correct combined order if the second sort is stable: a
stable sort only reorders elements that actually differ on the secondary key,
so within any group of equal secondary-key values, the primary-key order from
step one is left untouched. An unstable sort makes no such promise: it may
reorder equal-secondary-key elements arbitrarily while grouping them, silently
destroying the primary ordering you already paid to establish.

A stable sort: merge sort, and Timsort (the hybrid merge/insertion sort
used by Python and Java's Collections.sort for objects). Both work by
merging or shifting elements without ever swapping two elements past an equal
one, so ties keep their input order.

An unstable sort: classic in-place selection sort (repeatedly swap the
current position with the position of the next-smallest remaining element).
The swap step moves elements across long distances in the array, including
past other elements with the same key, which is exactly what breaks ties.
Typical in-place quicksort implementations are unstable for the same reason
(the partition step swaps non-adjacent elements).

If you only have an unstable sort available, you can force stability by
attaching the original index to each record and sorting by (key, original_index)
instead of key alone. Ties on key are then broken by index, which exactly
reproduces stable behavior, at the cost of allocating one extra field per record.

Worked example

Take four employee records, already sorted by name (the primary key):

Now sort by department (the secondary key). A stable sort must produce:

Eng: Chen, Ito       (name order preserved)
Sales: Alvarez, Diallo  (name order preserved)

Running this in Python, where sorted() is stable, versus a hand-rolled
unstable selection sort, on the exact same input:

records = [
    {"name": "Alvarez", "dept": "Sales"},
    {"name": "Chen", "dept": "Eng"},
    {"name": "Diallo", "dept": "Sales"},
    {"name": "Ito", "dept": "Eng"},
]

stable_result = sorted(records, key=lambda r: r["dept"])

def unstable_selection_sort_by_dept(items):
    items = list(items)
    n = len(items)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if items[j]["dept"] < items[min_idx]["dept"]:
                min_idx = j
        items[i], items[min_idx] = items[min_idx], items[i]
    return items

unstable_result = unstable_selection_sort_by_dept(records)

print([(r["dept"], r["name"]) for r in stable_result])
print([(r["dept"], r["name"]) for r in unstable_result])

Output (verified by running this exact code):

[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Alvarez'), ('Sales', 'Diallo')]
[('Eng', 'Chen'), ('Eng', 'Ito'), ('Sales', 'Diallo'), ('Sales', 'Alvarez')]

The Eng group comes out identical either way, but the Sales group is
reversed under the unstable sort: Diallo now precedes Alvarez, even though
Alvarez came first alphabetically. That reversal is the bug: any downstream
code relying on "same department, alphabetical order" is now silently wrong,
and the failure is data-dependent, so it will not show up on every input.

Trade-offs & pitfalls

• Stability is a property of the algorithm's specification, not just a given
  implementation detail: "quicksort" is not stable by definition, but a
  particular library's sort might document stability as a guarantee (check
  the docs rather than assuming from the algorithm's name).
• The index-as-tiebreaker trick works with any comparison sort, stable or not,
  but costs O(n) extra memory for the index field and slightly more comparison
  overhead per element; it is the right choice when the language's built-in
  sort is unstable by contract (e.g. a raw quicksort library call) and you
  cannot swap in a stable one.
• A common wrong turn is assuming "the final order looks right on my test
  data" is proof of stability; instability is a tie-breaking behavior that
  only shows up when there are actual ties, so it hides in datasets with few
  duplicate keys and surfaces later at a different data distribution.
• Do not confuse stability with sort correctness on the primary sort key
  itself: an unstable sort still produces a fully correct order on the key it
  was told to sort by, it only fails to preserve unrelated prior ordering
  among equal elements.