Algorithmic Problem-Solving and Data Structure Selection Questions

Direct answer

Doubling the bucket array whenever the load factor (occupied slots divided by
total capacity) exceeds 0.75 gives O(1) amortized cost per insert: the
occasional expensive rehash (copying every element into a bigger array) is
paid for by all the cheap inserts since the last resize, and because capacity
doubles, resizes become exponentially rarer as the table grows. Adding a
symmetric shrink-on-deletion policy is only safe if the shrink threshold is
set well below the grow threshold; using the same threshold for both directions
lets an adversarial (or just unlucky) sequence of alternating inserts and
deletes near the boundary trigger a full resize on every single operation,
destroying the amortized guarantee entirely.

Structured elaboration

Amortized cost of grow-only doubling (aggregate method). Suppose the
table starts at capacity $c_0$ and doubles ($c_k = 2^k c_0$) each time
size exceeds $\theta \cdot \text{capacity}$ for threshold $\theta = 0.75$.
At the moment of the $k$-th resize, the table holds roughly
$\theta \cdot c_{k-1}$ live elements, and a resize rehashes (copies) all of
them into the new array:

Summing the rehash cost across all resizes up to the point where the table
has grown to serve $n$ elements is a geometric series:

So total rehashing work across all resizes is $O(n)$, not $O(n \log n)$
or worse, because a geometric series is dominated by its last term. Adding
the $O(1)$ cost of each of the $n$ individual inserts:

Why shrinking naively breaks this. The argument above works because
resize events become rarer as capacity grows (each one "pays off" a
geometrically larger batch of prior inserts). If shrinking uses the same
threshold as growing, a table can cross the grow threshold, resize, and then
land at a load factor that is already below that same threshold, so the very
next deletion immediately triggers a shrink back down, and the next insertion
after that immediately triggers a grow again. There is no batch of cheap
operations paying for each resize anymore, every operation near that boundary
pays for a full resize.

The standard fix: hysteresis. Use two different thresholds with a gap
between them, for example grow at load factor 0.75 but only shrink once load
factor drops below roughly 0.25. This guarantees that after any resize
(grow or shrink), the table must absorb a substantial number of operations
purely from the size change alone before it can cross the other threshold and
trigger another resize, restoring the same "geometric batches pay for
resizes" argument that made grow-only doubling amortized O(1).

Worked example

Simulating exact resize behavior with pinned parameters (capacity starts at
4, size starts at 3, doubling on grow, halving on shrink) demonstrates both
failure and fix:

def simulate_thrashing(n_ops, threshold=0.75):
    capacity, size, total_work, resizes = 4, 3, 0, 0
    for i in range(n_ops):
        if i % 2 == 0:
            size += 1; total_work += 1
            if size / capacity > threshold:
                capacity *= 2; total_work += size; resizes += 1
        else:
            size -= 1; total_work += 1
            if capacity > 4 and size / capacity < threshold:
                capacity //= 2; total_work += size; resizes += 1
    return total_work, resizes

def simulate_with_hysteresis(n_ops, grow_threshold=0.75, shrink_threshold=0.25):
    capacity, size, total_work, resizes = 4, 3, 0, 0
    for i in range(n_ops):
        if i % 2 == 0:
            size += 1; total_work += 1
            if size / capacity > grow_threshold:
                capacity *= 2; total_work += size; resizes += 1
        else:
            size -= 1; total_work += 1
            if capacity > 4 and size / capacity < shrink_threshold:
                capacity //= 2; total_work += size; resizes += 1
    return total_work, resizes

work_t, resizes_t = simulate_thrashing(2000)
work_h, resizes_h = simulate_with_hysteresis(2000)
print("same-threshold:", work_t, resizes_t, work_t / 2000)
print("hysteresis gap:", work_h, resizes_h, work_h / 2000)

Output (verified by running this exact code):

same-threshold: 9000 2000 4.5
hysteresis gap: 2004 1 1.002

With a single shared threshold, all 2000 alternating operations trigger a
resize (2000 resizes for 2000 operations, amortized 4.5 units of work per
operation for this small table); with a 0.75/0.25 hysteresis gap, only 1
resize happens across all 2000 operations, and amortized cost settles at
almost exactly 1.0, the O(1) result the design is supposed to guarantee. The
gap between grow and shrink thresholds is what restores amortized O(1) once
deletions are allowed to trigger shrinking.

Trade-offs & pitfalls

• The failure mode above gets worse, not better, at scale: the per-resize
  cost is proportional to the table's current size, so the same
  shared-threshold thrashing pattern on a table with 100,000 capacity and
  75,000 elements turns every operation into a resize costing roughly 75,000
  units of work, an amortized cost of $O(n)$ per operation instead of
  $O(1)$, which is the whole point of the doubling scheme defeated.
• Hysteresis is not free: keeping the shrink threshold well below the grow
  threshold means the table tolerates more "wasted" empty capacity before
  shrinking (at a 0.25 shrink threshold, the table can be using as little as
  a quarter of its capacity before it shrinks), a deliberate memory-versus-
  resize-frequency trade-off, not a way to avoid the trade-off entirely.
• A related but distinct pitfall is choosing a shrink factor that is too
  aggressive relative to the grow factor (for example, growing by 2x but
  shrinking all the way back to the smallest possible size instead of by a
  matching factor); this can reintroduce the same thrashing risk in a
  different shape if the shrunk table is immediately close to its own grow
  threshold again.

Direct answer

A stack is last-in-first-out (LIFO): the most recently added item comes out first. A queue is first-in-first-out (FIFO): items come out in the order they arrived. Use a stack when you need to undo or backtrack in reverse arrival order, such as a browser's back button or a function call stack; use a queue when arrival order must be preserved, such as a task scheduler or a print spooler. You can build a queue out of two stacks: push is $O(1)$ worst case, and pop is amortized (averaged over a sequence of operations) $O(1)$ because each element only ever moves between the two stacks once over its lifetime.

Structured elaboration

Queue from two stacks. Keep an in_stack that absorbs pushes and an out_stack that serves pops. Pushing always goes to in_stack in $O(1)$. When a pop or peek is requested and out_stack is empty, drain all of in_stack into out_stack; this reverses the order, so the oldest element (which was at the bottom of in_stack) ends up on top of out_stack, ready to be returned first.

Why the amortized argument holds. Use the aggregate method: over any sequence of n operations, each element is pushed onto in_stack exactly once (cost 1), moved from in_stack to out_stack at most once in its lifetime (cost 1), and popped from out_stack exactly once (cost 1). No element is ever moved more than that, so the total work across the whole sequence is bounded by a constant multiple of n, which is what "amortized $O(1)$ per operation" means, even though any single pop that triggers the drain costs $O(n)$ by itself.

Worked example

class QueueFromStacks:
    def __init__(self):
        self.in_stack: list[int] = []
        self.out_stack: list[int] = []

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _transfer(self) -> None:
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]


if __name__ == "__main__":
    q = QueueFromStacks()
    q.push(1)
    q.push(2)
    q.push(3)
    seq = [q.pop(), q.peek()]
    q.push(4)
    seq += [q.pop(), q.pop(), q.pop()]
    print(seq)

Running this prints [1, 2, 2, 3, 4]. The first pop() triggers a drain (in_stack [1,2,3] becomes out_stack [3,2,1], top popped is 1); peek() then reads 2 for free from the already-drained out_stack; pushing 4 goes straight to in_stack without disturbing out_stack; the remaining pops (2, 3) come from out_stack, and the last pop (4) triggers a second drain since out_stack had emptied.

Complexity

Space: $O(n)$ total across the two internal stacks, since every pushed element lives in exactly one of them at any time (no extra space is used beyond storing the n elements themselves).

Edge cases

• Calling pop() or peek() on an empty two-stack queue: in the reference implementation, _transfer() leaves out_stack empty when both stacks are empty, so pop()'s self.out_stack.pop() and peek()'s self.out_stack[-1] both raise an unhandled IndexError instead of failing cleanly. Guard this explicitly, for example if not self.in_stack and not self.out_stack: raise IndexError("pop from empty queue") before touching out_stack, so the caller gets a clear, intentional signal rather than an incidental one.
• A single push followed immediately by a pop: the drain moves that one element from in_stack to out_stack and it is returned, leaving both stacks empty again, which is the state the empty-queue guard above must handle correctly on the next call.

Trade-offs & pitfalls

The most common confusion is treating "amortized" as "always fast": a single pop can still cost $O(n)$ when it triggers the drain. Note the asymmetry with building a stack out of a single queue by rotating on every push (dequeue-then-requeue the previous elements so the newest sits at the front): that rotation happens on every single push, not just occasionally, so it is genuinely $O(n)$ per push with no amortization to appeal to, unlike the two-stack construction above where the expensive transfer is rare and each element only ever pays for it once.

Direct answer

Pick based on two properties of the graph and one property of the query: if every edge has the same weight, breadth-first search (BFS) alone gives shortest paths in linear time; if weights differ but are never negative, Dijkstra's algorithm is the standard single-source choice; if a negative weight is possible (but no negative cycle), Dijkstra can give a wrong answer and Bellman-Ford is required instead; and if you need distances between every pair rather than from one source, Floyd-Warshall (a dynamic-programming algorithm that considers every node in turn as a possible shortcut between every pair) is the natural fit for all-pairs, or equivalently running Dijkstra from every node. A* only changes single-source, non-negative-weight search: it adds a heuristic estimate of remaining distance to prioritize expansion toward a specific goal, and it only helps, versus plain Dijkstra, when that heuristic is admissible (it never overestimates the true remaining cost), since an inadmissible heuristic can cause A* to return a path that is not actually shortest.

Structured elaboration

Decision order:

1. Are all edge weights equal (or is the graph unweighted)? Use BFS: $O(V + E)$, no priority queue needed at all.
2. Do you need distances between every pair of nodes, not just from one source? Use Floyd-Warshall, $O(V^3)$, or repeat Dijkstra from every source if the graph is sparse and there are no negative weights.
3. Otherwise, single-source with weights: are negative edge weights possible? If yes, use Bellman-Ford, $O(V \cdot E)$, which also detects a negative cycle if one exists (a cycle whose total weight is negative, which makes "shortest path" undefined, since you could loop it forever to keep decreasing the cost). If no, use Dijkstra, $O((V+E) \log V)$ with a binary heap.
4. If you additionally have a single, known goal node (not "distances to everywhere"), and a decent estimate of remaining distance, layer A* on top of Dijkstra's non-negative-weight assumption to reduce how much of the graph gets explored.

Why Dijkstra breaks under negative weights: once Dijkstra pops a node off its priority queue, it treats that node's distance as final and never revisits it, on the assumption that nothing already queued could possibly offer a shorter path, since all remaining edges only add non-negative weight. A negative edge violates that assumption directly: a longer-looking path discovered later can still turn out shorter once a negative edge is added to it.

What A's heuristic must guarantee*: admissibility, never overestimating the true remaining cost to the goal. Given an admissible heuristic, A* is guaranteed to still find a shortest path, exactly like Dijkstra, but it explores fewer nodes when the heuristic is informative, because it prioritizes nodes that look closer to the goal rather than merely closer to the start. (A stronger property, consistency, additionally guarantees a node is never re-expanded after being finalized, which is what lets A* implementations skip the "revisit and relax an already-closed node" bookkeeping that a merely admissible-but-inconsistent heuristic would otherwise require.) A straight-line (Euclidean) distance heuristic on a road network or grid is a classic admissible choice, since no real route can be shorter than the straight line.

Worked example

Bellman-Ford correctness under a negative edge, where Dijkstra gets it wrong:

import math

def dijkstra(adj, src):
    import heapq
    dist = {src: 0}
    finalized = set()
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in finalized:
            continue
        finalized.add(u)
        for v, w in adj.get(u, []):
            if v in finalized:
                continue
            nd = d + w
            if nd < dist.get(v, math.inf):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def bellman_ford(edges, nodes, src):
    dist = {n: math.inf for n in nodes}
    dist[src] = 0
    for _ in range(len(nodes) - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("negative cycle detected")
    return dist

# True shortest A->B is via C: 1 -> 4 + (-10) = -6, but Dijkstra finalizes
# B at distance 1 (direct edge) before C is even processed.
adj = {"A": [("B", 1), ("C", 4)], "C": [("B", -10)]}
edges = [("A", "B", 1), ("A", "C", 4), ("C", "B", -10)]
nodes = ["A", "B", "C"]

print("dijkstra:", dijkstra(adj, "A"))
print("bellman_ford:", bellman_ford(edges, nodes, "A"))

Running this prints:

dijkstra: {'A': 0, 'B': 1, 'C': 4}
bellman_ford: {'A': 0, 'B': -6, 'C': 4}

Dijkstra reports B at distance 1 (wrong: it finalized B via the direct edge before discovering the cheaper route through C), while Bellman-Ford correctly finds -6 via A to C to B.

A exploring fewer nodes than Dijkstra given an admissible heuristic*, on an open 20x20 grid from (0,0) to (5,5), using Manhattan distance as the heuristic:

import heapq

def neighbors(pos, size):
    x, y = pos
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        nx, ny = x + dx, y + dy
        if 0 <= nx < size and 0 <= ny < size:
            yield (nx, ny)

def manhattan(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def search(start, goal, size, use_heuristic):
    h = (lambda n: manhattan(n, goal)) if use_heuristic else (lambda n: 0)
    g = {start: 0}
    pq = [(h(start), start)]
    visited = set()
    expansions = 0
    while pq:
        _, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        expansions += 1
        if node == goal:
            break
        for nb in neighbors(node, size):
            ng = g[node] + 1
            if ng < g.get(nb, float("inf")):
                g[nb] = ng
                heapq.heappush(pq, (ng + h(nb), nb))
    return g[goal], expansions

size = 20
start, goal = (0, 0), (5, 5)
dist_astar, exp_astar = search(start, goal, size, use_heuristic=True)
dist_dij, exp_dij = search(start, goal, size, use_heuristic=False)
print("A* distance:", dist_astar, "nodes expanded:", exp_astar)
print("Dijkstra distance:", dist_dij, "nodes expanded:", exp_dij)

Running this prints:

A* distance: 10 nodes expanded: 36
Dijkstra distance: 10 nodes expanded: 61

Both find the same correct shortest distance (10), but A* reaches it having expanded 36 nodes against Dijkstra's 61, because the heuristic steered expansion toward the goal instead of outward in every direction equally.

Trade-offs & pitfalls

A common mistake is treating A* as "a different algorithm" from Dijkstra rather than as Dijkstra with a heuristic added to the priority; with a heuristic of zero everywhere (as in the comparison above), A* degenerates to exactly Dijkstra, which is a good way to check an A* implementation for bugs. A second pitfall is picking a heuristic that overestimates in some region "because it prunes more nodes": an inadmissible heuristic can make A* return a path that is not actually shortest, so any heuristic must be checked against the admissibility property, not just judged by how much it speeds things up. Practically, Dijkstra's own implementation constant matters too: with a binary heap, each edge relaxation that improves a distance costs $O(\log V)$ to sift, which under many decrease-key-style relaxations is the dominant cost; the common fix is not switching to a Fibonacci or pairing heap (both have amortized $O(1)$ or near-$O(1)$ decrease-key but carry higher constant factors and more complex implementations) but instead allowing duplicate, stale entries in a plain binary heap and lazily discarding them on pop, which is what the Dijkstra implementation above already does and is the standard practical choice.

Direct answer

An array gives $O(1)$ index-based random access and is cache-friendly, because its elements sit in one contiguous block of memory that the CPU can pull into cache together. A singly linked list gives $O(1)$ insertion or deletion once you already hold a reference to the splice point, at the cost of $O(n)$ traversal to reach any given position and extra per-node memory overhead. For a workload that is mostly random reads, pick an array (or dynamic array); for a workload that is mostly insertions and deletions in the middle where you already hold the relevant node reference, a linked list wins.

Structured elaboration

The contiguous-versus-non-contiguous memory allocation framing is exactly this same dimension stated differently: contiguous storage is what gives arrays both their cache locality and their index arithmetic; non-contiguous, per-node allocation is what gives linked lists their cheap local splicing at the cost of locality. In a garbage-collected (GC) language, this also affects collector pressure: many small linked-list node objects mean more individual objects for the garbage collector to track and scan, compared to one contiguous array allocation holding the same data.

Worked example

Consider inserting a new element in the middle of a ten-item collection, repeatedly, as items are typed into an editable list. With an array, each insertion must shift every element after the insertion point one slot over, an $O(n)$ cost per insertion regardless of whether you know exactly where to insert. With a singly linked list, if the editing position is tracked by an existing reference to the node just before it (as a cursor would be in a text-editing context), each insertion is a pure $O(1)$ relink; but if you only know the position as an index and must first walk from the head to reach it, the linked list gains nothing over the array for that access, since both now cost $O(n)$ overall. This is why the deciding factor is not "array versus linked list" in the abstract, but whether the workload naturally hands you a reference to the splice point or only an index.

Trade-offs & pitfalls

Assuming "$O(1)$ insertion" for a linked list means fast in absolute terms is a common mistake: reaching the splice point is usually the dominant cost unless a reference to it is already in hand from a prior traversal or an auxiliary index. Ignoring the per-element memory overhead ratio is another: a linked list of single integers can use several times the memory of the equivalent array, because the pointer overhead per node is fixed regardless of how small the stored value is. Modern hybrid structures such as a deque (double-ended queue) or a rope address parts of this trade-off by chunking data into contiguous blocks rather than choosing purely one extreme or the other.

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.