Google Software Engineer Entry Level (L3) Interview Preparation Guide

A partial hotfix, restoring some functionality but not all, needs careful handling so the working state isn't accidentally lost and the remaining gap is clearly tracked, not silently forgotten.

Approach

1. Preserve the working state explicitly: commit the partial fix on its own clearly-labeled branch/commit rather than mixing it with further in-progress changes, so it can be safely deployed or rolled back to independently.
2. Document exactly what's fixed and what isn't, in the commit message and in a tracked follow-up item, including which specific scenarios remain broken, so the gap doesn't get discovered again from scratch by whoever picks it up next.
3. Capture logs/diagnostics before finalizing the partial fix, since once deployed, the remaining broken scenarios may become harder to reproduce (the environment has changed).
4. Decide deploy versus rollback based on net impact: does the partial fix genuinely reduce customer impact for a real majority of cases, or does it introduce a confusing half-fixed state that's harder to reason about than either the original bug or a full rollback? If unsure, a clean rollback while completing the fix properly is usually safer than shipping a partial state that stakeholders might mistake for "done."

Writing the follow-up plan

State precisely what remains broken, why the partial fix doesn't cover it yet, and a concrete next step with an owner, rather than a vague "will investigate further" that has no forcing function to actually get finished.

Trade-offs and pitfalls

The main risk of shipping a partial fix is stakeholders treating "mostly fixed" as "fixed," closing out attention on the issue before the remaining gap is actually addressed; being explicit and specific about what's still broken in every status update is what prevents that.

The idea in plain words

A has m real values followed by n empty slots, and B has n values. The finished result must live in A. The trick is the direction: fill A from the back. The largest remaining value overall is the larger of A's last real value and B's last value, and the last slot of A is free, so you can write it there without destroying anything you still need. Then the second largest goes in the second-to-last slot, and so on. Three indices do the job: i (last unread real value of A), j (last unread value of B), k (next slot to write).

Why the obvious direction fails

Merging from the front would write the smallest value into A[0], which still holds an unread value of A. To avoid overwriting you would have to shift A right first (O(m) per insertion, O(m * n) in total) or copy A somewhere (O(m) extra space). Writing from the back needs neither, because the free slots sit exactly where the biggest values belong.

The approach

1. Set i = m - 1, j = n - 1, k = m + n - 1.
2. While B still has unread values: if A has an unread value and it is strictly greater than B[j], move A[i] to A[k] and decrement i; otherwise move B[j] to A[k] and decrement j. Decrement k.
3. When B is used up you stop. Any values of A that are still unread are already sitting in their final slots (slots 0..i), so they need no copying. If A runs out first, the loop keeps copying the rest of B into the front slots.

On a tie the B value is written first (to the later slot), so equal values from A stay before equal values from B. That makes the merge stable: values that compare equal keep the order they had before the merge, with A's copies ahead of B's copies.

import random


def merge_into_first(A, m, B, n, key=lambda x: x, trace=False):
    """A holds m sorted values followed by n spare slots; B holds n sorted values.
    Fill A from the back so no unread value of A is overwritten. Returns comparisons."""
    i, j, k = m - 1, n - 1, m + n - 1
    comparisons = 0
    while j >= 0:                       # when B is used up, A's remaining values are already in place
        if i >= 0:
            comparisons += 1
        if i >= 0 and key(A[i]) > key(B[j]):      # tie: take B first, so B ends up after the equal A values
            A[k] = A[i]
            i -= 1
        else:
            A[k] = B[j]
            j -= 1
        k -= 1
        if trace:
            print(f"  i={i:2d} j={j:2d} k={k:2d}  A={A}")
    return comparisons


if __name__ == "__main__":
    A = [2, 5, 8, 0, 0, 0]
    B = [1, 5, 9]
    print("A =", A, " B =", B)
    c = merge_into_first(A, 3, B, 3, trace=True)
    print("result:", A, "comparisons:", c)

    # Edge cases: m = 0, n = 0, both zero, B entirely smaller / larger, very different sizes.
    cases = [([], 0, []), ([4, 7], 2, []), ([0, 0], 0, [3, 6]),
             ([5, 6, 0, 0], 2, [1, 2]), ([1, 2, 0, 0], 2, [8, 9]),
             ([7, 0], 1, [3]), ([7, 7, 0, 0], 2, [7, 7])]
    for A, m, B in cases:
        n = len(B)
        expected = sorted(A[:m] + B)
        merge_into_first(A, m, B, n)
        assert A == expected, (A, expected)
    print("edge cases: ok")

    # Sizes that differ greatly: comparisons never exceed m + n and the work is O(m + n).
    for m, n in ((1, 1000), (1000, 1), (500, 500)):
        rnd = random.Random(m * 7 + n)
        a_vals = sorted(rnd.randint(0, 10**6) for _ in range(m))
        b_vals = sorted(rnd.randint(0, 10**6) for _ in range(n))
        A = a_vals + [0] * n
        c = merge_into_first(A, m, b_vals, n)
        assert A == sorted(a_vals + b_vals)
        print(f"m={m:4d} n={n:4d}  comparisons={c:4d}  (limit m+n={m + n})")
        if m == 1:
            print(f"   B values at or above the lone A value: {sum(v >= a_vals[0] for v in b_vals)}")
        if n == 1:
            print(f"   A values above the lone B value: {sum(v > b_vals[0] for v in a_vals)}")

    # Stability: tagged equal keys, A's copies stay before B's copies.
    A = [(3, "A0"), (3, "A1"), (6, "A2"), None, None, None]
    B = [(3, "B0"), (6, "B1"), (6, "B2")]
    merge_into_first(A, 3, B, 3, key=lambda r: r[0])
    print([t[1] for t in A])

    # 500 random trials against sorted().
    rnd = random.Random(2)
    for _ in range(500):
        m, n = rnd.randint(0, 8), rnd.randint(0, 8)
        a_vals = sorted(rnd.randint(0, 5) for _ in range(m))
        b_vals = sorted(rnd.randint(0, 5) for _ in range(n))
        A = a_vals + [None] * n
        merge_into_first(A, m, b_vals, n)
        assert A == sorted(a_vals + b_vals)
    print("500 random pairs: ok")

Run in a python:3.12 container (Python 3.12), it prints:

A = [2, 5, 8, 0, 0, 0]  B = [1, 5, 9]
  i= 2 j= 1 k= 4  A=[2, 5, 8, 0, 0, 9]
  i= 1 j= 1 k= 3  A=[2, 5, 8, 0, 8, 9]
  i= 1 j= 0 k= 2  A=[2, 5, 8, 5, 8, 9]
  i= 0 j= 0 k= 1  A=[2, 5, 5, 5, 8, 9]
  i=-1 j= 0 k= 0  A=[2, 2, 5, 5, 8, 9]
  i=-1 j=-1 k=-1  A=[1, 2, 5, 5, 8, 9]
result: [1, 2, 5, 5, 8, 9] comparisons: 5
edge cases: ok
m=   1 n=1000  comparisons= 100  (limit m+n=1001)
   B values at or above the lone A value: 99
m=1000 n=   1  comparisons= 769  (limit m+n=1001)
   A values above the lone B value: 768
m= 500 n= 500  comparisons= 997  (limit m+n=1000)
['A0', 'A1', 'B0', 'A2', 'B1', 'B2']
500 random pairs: ok

Reading the trace

Each trace line shows the three indices after the step and the list after the write. Start: A = [2, 5, 8, 0, 0, 0] (the zeros are free slots), B = [1, 5, 9].

1. 8 is not greater than 9, so 9 from B goes to the last slot.
2. 8 beats B's 5, so 8 goes to slot 4.
3. A's 5 equals B's 5, which is not "strictly greater", so B's 5 goes to slot 3 (the tie rule).
4. A's 5 beats B's 1, so A's 5 moves to slot 2.
5. A's 2 beats B's 1, so 2 moves to slot 1.
6. A has no unread values (i = -1), so B's last value, 1, goes to slot 0. Both j and k end at -1.

The final list is [1, 2, 5, 5, 8, 9] with 5 comparisons.

The stability line. The tagged test merges A = [(3, 'A0'), (3, 'A1'), (6, 'A2')] with B = [(3, 'B0'), (6, 'B1'), (6, 'B2')], comparing only the number in each pair, and prints the tags in the order they end up in A. Three values tie at 3 and three tie at 6. The printed order ['A0', 'A1', 'B0', 'A2', 'B1', 'B2'] has A0, A1, B0 for the 3s and A2, B1, B2 for the 6s: within each tie, A's copies come first, and A's and B's copies each keep their own order. That is what the tie rule (write B first, into the later slot) produces.

Complexity

• Time: O(m + n). Each loop step writes one slot and moves one index, and there are at most m + n writes.
• Space: O(1) extra: three integers and no copies.
• Different sizes: the program fills each array with values from a seeded random generator (random.Random(m * 7 + n), values 0 to 1,000,000), so the exact counts below are reproducible by running the listing, and they depend on where the lone value falls among the other array's values. With m = 1 and n = 1000 the loop made 100 comparisons: 99 values of B were at or above the single A value and were written first, one more comparison moved the A value, after which A was used up and the remaining B values were copied with no comparisons. With m = 1000 and n = 1 it made 769 comparisons: 768 values of A were above B's single value and moved right by one slot, one more comparison wrote B's value, and the loop stopped, leaving the 232 smallest values of A untouched. Only the bound is guaranteed: the count never exceeds m + n, the limit printed beside each line.

Edge cases and common mistakes

• m = 0: A has only free slots, i starts at -1, and the loop copies all of B. n = 0: the while j >= 0 loop never runs and A is already the answer. Both zero is an empty list and works. The edge-case block in the driver asserts all of these plus all-equal values, B entirely smaller than A, and B entirely larger.
• Write i >= 0 before reading A[i]. A negative index in Python wraps around to the end of the list instead of stopping the loop, so without the guard the code compares against, and moves, slots that are not values of A. Deleting the guard from this program and trying every small pair of arrays gave either a correct result (when B ran out first) or an IndexError a few steps later, never a clean stop, so the guard is what makes the case where A runs out first well defined.
• The loop condition is j >= 0, not "while both have values". Looping until i reaches 0 as well wastes work on values that are already in place.
• Do not infer m from len(A); the number of real values is a separate argument.
• Merging front to back, or using A.insert inside the loop, both turn this into O(m * n).

Running the code

Save the program as merge_into_first.py and run:
python merge_into_first.py

Standard library only (random); no install or config needed.

The idea

A binary search tree (BST: left subtree keys smaller, right subtree keys larger) built from a sorted array is only fast if it is height-balanced, meaning that at every node the heights of the two subtrees differ by at most 1. (Height here counts nodes: an empty tree is 0, a single node is 1. The other common convention counts edges, with an empty tree -1 and a single node 0; subtract 1 from every height below to convert.) Since the array is already sorted, make the middle element the root: everything left of it is smaller and goes in the left subtree, everything right of it is larger and goes in the right subtree. Then do the same to each half.

Recursion invariant: build(lo, hi) returns a height-balanced BST containing exactly nums[lo..hi], or None when lo > hi. Picking the middle makes the two halves differ in size by at most 1: a range of m elements leaves m - 1 for the two sides, so the sides get floor((m - 1) / 2) and ceil((m - 1) / 2). Sizes that differ by at most 1 give heights that differ by at most 1, because a tree built this way on s elements has height equal to the number of binary digits of s (see Height below), and s and s + 1 never differ by more than one digit (3 = 11 and 4 = 100 differ by one digit; 4 = 100 and 5 = 101 have the same number). So the balance condition holds at every node. "By induction" means: the two halves are smaller instances of the same claim, a range of 0 or 1 elements is trivially balanced, and so if each half is balanced, joining them under the middle keeps the whole balanced.

The brute force of inserting the keys one by one in sorted order produces a chain of height n. Building from the middle avoids that. Pass indices, not slices: nums[:mid] copies the array at every level and turns O(n) into O(n log n).

Code

For 7 elements the result is perfect:

        4
      /   \
     2     6
    / \   / \
   1   3 5   7

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


def sorted_array_to_bst(nums, trace=None, upper=False):
    def build(lo, hi, depth):
        """Build a BST from nums[lo..hi] inclusive. Empty range -> None."""
        if lo > hi:
            return None
        mid = (lo + hi + 1) // 2 if upper else (lo + hi) // 2   # lower or upper middle
        if trace is not None:
            trace.append(f"{'  ' * depth}build[{lo}..{hi}] -> root {nums[mid]}")
        node = Node(nums[mid])
        node.left = build(lo, mid - 1, depth + 1)
        node.right = build(mid + 1, hi, depth + 1)
        return node
    return build(0, len(nums) - 1, 0)


def height(node):
    """Height in nodes: empty tree 0, single node 1."""
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def is_height_balanced(node):
    """Returns the height, or -1 as soon as some node's subtrees differ by more than 1."""
    if node is None:
        return 0
    left = is_height_balanced(node.left)
    right = is_height_balanced(node.right)
    if left < 0 or right < 0 or abs(left - right) > 1:
        return -1
    return 1 + max(left, right)


def inorder(node):
    return [] if node is None else inorder(node.left) + [node.key] + inorder(node.right)


#          4
#        /   \
#       2     6
#      / \   / \
#     1   3 5   7
nums = [1, 2, 3, 4, 5, 6, 7]
trace = []
root = sorted_array_to_bst(nums, trace)
print("\n".join(trace))
print("inorder:", inorder(root), "height:", height(root))

print()
trace = []
root = sorted_array_to_bst([10, 20, 30, 40, 50, 60], trace)
print("\n".join(trace))
print("inorder:", inorder(root), "height:", height(root))

print()
trace = []
root = sorted_array_to_bst([10, 20, 30, 40, 50, 60], trace, upper=True)
print("\n".join(trace))
print("upper middle: inorder:", inorder(root), "height:", height(root))
print()

# n versus height: height must equal the number of bits in n, i.e. floor(log2 n) + 1
for n in range(0, 3000):
    arr = list(range(n))
    tree = sorted_array_to_bst(arr)
    assert inorder(tree) == arr
    assert height(tree) == n.bit_length()
    assert is_height_balanced(tree) >= 0
print("n = 0..2999: inorder matches, balanced, height == n.bit_length()")
for n in (1, 2, 3, 7, 8, 1000, 1_000_000):
    tree = sorted_array_to_bst(list(range(n)))
    print(f"n = {n:>9}  height = {height(tree):>2}")


def build_with_mid_mistake(nums, lo, hi):
    """The mistake: the left call reuses mid instead of mid - 1."""
    if lo > hi:
        return None
    mid = (lo + hi) // 2
    node = Node(nums[mid])
    node.left = build_with_mid_mistake(nums, lo, mid)
    node.right = build_with_mid_mistake(nums, mid + 1, hi)
    return node


try:
    build_with_mid_mistake([1, 2, 3], 0, 2)
except RecursionError:
    print("mid instead of mid - 1 in the left call: RecursionError")

Run in a python:3.12 container, it prints:

build[0..6] -> root 4
  build[0..2] -> root 2
    build[0..0] -> root 1
    build[2..2] -> root 3
  build[4..6] -> root 6
    build[4..4] -> root 5
    build[6..6] -> root 7
inorder: [1, 2, 3, 4, 5, 6, 7] height: 3

build[0..5] -> root 30
  build[0..1] -> root 10
    build[1..1] -> root 20
  build[3..5] -> root 50
    build[3..3] -> root 40
    build[5..5] -> root 60
inorder: [10, 20, 30, 40, 50, 60] height: 3

build[0..5] -> root 40
  build[0..2] -> root 20
    build[0..0] -> root 10
    build[2..2] -> root 30
  build[4..5] -> root 60
    build[4..4] -> root 50
upper middle: inorder: [10, 20, 30, 40, 50, 60] height: 3

n = 0..2999: inorder matches, balanced, height == n.bit_length()
n =         1  height =  1
n =         2  height =  2
n =         3  height =  2
n =         7  height =  3
n =         8  height =  4
n =      1000  height = 10
n =   1000000  height = 20
mid instead of mid - 1 in the left call: RecursionError

Worked trace

For [1..7]: the range 0..6 has middle index 3, root 4. The left range 0..2 has middle 1, root 2, with single-element ranges 0..0 (root 1) and 2..2 (root 3). The right range 4..6 mirrors it with roots 6, 5, 7. For six elements [10..60] the middle index is (0 + 5) // 2 = 2, so root 30. The left range 0..1 has middle 0, so root 10 with its right child 20; the right range 3..5 has root 50 with children 40 and 60. With an even count there are two middles, and the code uses the lower one ((lo + hi) // 2). The upper middle, (lo + hi + 1) // 2, gives a different but equally valid tree, printed by the third trace: root 40, left subtree 20 with children 10 and 30, right subtree 60 with the single left child 50. Its in-order list is the same and its height is 3 either way.

Height, time and space

• Height: the printed check confirms that the height equals the number of bits of n, floor(log2 n) + 1, which equals the smallest h with 2^h - 1 >= n. To see why, note that a number with b binary digits satisfies 2^(b-1) <= n <= 2^b - 1, so b is the smallest h for which n fits under 2^h - 1. Check: for n = 7, 2^2 - 1 = 3 is too small and 2^3 - 1 = 7 fits, so h = 3, and 7 is 111 in binary (3 digits). For n = 8, 2^3 - 1 = 7 is too small and 2^4 - 1 = 15 fits, so h = 4, and 8 is 1000 (4 digits). So n = 7 gives 3, n = 8 gives 4 (a perfect tree of 3 levels holds only 7), n = 1,000 gives 10, and n = 1,000,000 gives 20 (all printed). Each level halves the range, which is why the height is logarithmic. In edge counting these heights are 2, 3, 9 and 19 for n = 7, 8, 1,000 and 1,000,000.
• Time O(n): every element becomes exactly one node, each call does O(1) work, and there are n real calls plus at most n + 1 calls on empty ranges.
• Space: O(n) for the n nodes that are the output, plus O(log n) for the recursion stack, whose depth equals the tree height. A million elements recurse only 20 levels deep, so CPython's 1000-frame limit is never an issue here, unlike when inserting sorted keys into a plain BST.

Edge cases and common mistakes

• Empty array returns None; one element returns a single node.
• Computing the middle as (lo + hi) // 2 is safe in Python (integers do not overflow); in a fixed-width language use lo + (hi - lo) // 2.
• Using mid instead of mid - 1 in the left call (or instead of mid + 1 in the right call): a one-element range then recurses on the very same range and never reaches the empty-range base case, so Python stops it with a RecursionError (the last printed line of the program shows the left-call version).
• Slicing the list at each level, adding a hidden O(n log n) copy cost.
• The answer is not unique; do not assume an interviewer expects a specific shape.
• Checked for every n from 0 to 2999: inorder traversal returns the input, every node's subtree heights differ by at most 1, and the height equals n.bit_length().

Running the code

Save as sorted_array_to_bst.py and run python sorted_array_to_bst.py with Python 3.12. Standard library only.

The difference in plain words

Depth-first search (DFS) is a way of walking a structure that already exists: go as deep as you can along one route, then come back and try the next. Its job is to visit things, and each thing is visited once.

Backtracking uses the same go-deep-then-come-back shape, but the thing being walked is a search space of partial solutions (the set of all the half-built answers you could ever reach) that is built as you go: make a choice, explore what follows, then undo the choice so the next sibling starts from a clean state. Its job is to find or list solutions, and the same item can be used again in different partial solutions.

So backtracking is DFS over an implicit tree of choices (a tree nobody stores: its nodes are partial answers, and each node's children are the ways to extend it by one more choice), plus two extras: an explicit undo step and (usually) pruning, meaning abandoning a branch the moment it cannot succeed.

One graph, both behaviours

A directed graph with a cycle (D -> A) is used for both. The listing contains DFS used for traversal, backtracking that constructs and undoes a partial path, and the two ways to get cycles wrong (a permanent visited mark, and no check at all). A simple path is a route that never repeats a node.

import sys

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["B", "D"],
    "D": ["A", "E"],     # D -> A closes a cycle; E is a dead end
    "E": [],
}


def dfs_reachable(start):
    """Traversal: visit each node once; 'visited' is never undone."""
    visited, order = set(), []

    def visit(node):
        visited.add(node)
        order.append(node)
        for nxt in graph[node]:
            if nxt not in visited:
                visit(nxt)

    visit(start)
    return order


def all_simple_paths(start, goal):
    """Backtracking: 'on_path' is added on the way down and removed on the way back."""
    paths, path, on_path = [], [start], {start}
    calls = 0

    def explore(node):
        nonlocal calls
        calls += 1
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in on_path:
                continue
            path.append(nxt); on_path.add(nxt)        # choose
            explore(nxt)                              # explore
            path.pop(); on_path.discard(nxt)          # undo

    explore(start)
    return paths, calls


def paths_with_permanent_visited(start, goal):
    """The same search with the traversal habit: visited is never undone."""
    paths, path, visited = [], [start], {start}

    def explore(node):
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in visited:
                continue
            visited.add(nxt); path.append(nxt)
            explore(nxt)
            path.pop()                                # path undone, visited is not

    explore(start)
    return paths


def paths_with_no_cycle_check(start, goal):
    if start == goal:
        return 1
    return sum(paths_with_no_cycle_check(n, goal) for n in graph[start])


print("DFS order from A:", dfs_reachable("A"))
paths, calls = all_simple_paths("A", "E")
print("simple paths A to E:", paths, "calls:", calls)
print("permanent visited:  ", paths_with_permanent_visited("A", "E"))

sys.setrecursionlimit(200)
try:
    paths_with_no_cycle_check("A", "E")
except RecursionError:
    print("no cycle check: RecursionError")


# Growth: k diamonds in a row. Each diamond has two routes, so there are 2**k simple paths.
def diamond_chain(k):
    g = {}
    for i in range(k):
        g[f"j{i}"] = [f"u{i}", f"d{i}"]
        g[f"u{i}"] = [f"j{i + 1}"]
        g[f"d{i}"] = [f"j{i + 1}"]
    g[f"j{k}"] = []
    return g


print("diamonds  dfs_visits  backtracking_calls")
for k in (2, 4, 8, 12):
    graph = diamond_chain(k)
    visited_count = len(dfs_reachable("j0"))
    _, call_count = all_simple_paths("j0", f"j{k}")
    print(f"{k:<9} {visited_count:<11} {call_count}")

Output:

DFS order from A: ['A', 'B', 'D', 'E', 'C']
simple paths A to E: [['A', 'B', 'D', 'E'], ['A', 'C', 'B', 'D', 'E'], ['A', 'C', 'D', 'E']] calls: 10
permanent visited:   [['A', 'B', 'D', 'E']]
no cycle check: RecursionError
diamonds  dfs_visits  backtracking_calls
2         7           13
4         13          61
8         25          1021
12        37          16381

Walking all_simple_paths("A", "E") call by call

The graph: A goes to B and C, B goes to D, C goes to B and D, D goes to A and E. This instrumented copy of the same function prints one line per call (the number is the call count, indentation is the depth, on_path is the set of marked nodes) and a skip line when a neighbour is already marked:

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["B", "D"],
    "D": ["A", "E"],
    "E": [],
}


def all_simple_paths_traced(start, goal):
    paths, path, on_path = [], [start], {start}
    calls = 0

    def explore(node):
        nonlocal calls
        calls += 1
        note = "  <- goal, record a copy" if node == goal else ""
        print(f"{calls:2}  {'  ' * (len(path) - 1)}at {node}  path={''.join(path)}  on_path={sorted(on_path)}{note}")
        if node == goal:
            paths.append(path[:])
            return
        for nxt in graph[node]:
            if nxt in on_path:
                print(f"    {'  ' * (len(path) - 1)}skip {nxt}: already on the path")
                continue
            path.append(nxt); on_path.add(nxt)
            explore(nxt)
            path.pop(); on_path.discard(nxt)

    explore(start)
    return paths, calls


paths, calls = all_simple_paths_traced("A", "E")
print(["".join(p) for p in paths], "calls:", calls)

Output:

 1  at A  path=A  on_path=['A']
 2    at B  path=AB  on_path=['A', 'B']
 3      at D  path=ABD  on_path=['A', 'B', 'D']
        skip A: already on the path
 4        at E  path=ABDE  on_path=['A', 'B', 'D', 'E']  <- goal, record a copy
 5    at C  path=AC  on_path=['A', 'C']
 6      at B  path=ACB  on_path=['A', 'B', 'C']
 7        at D  path=ACBD  on_path=['A', 'B', 'C', 'D']
          skip A: already on the path
 8          at E  path=ACBDE  on_path=['A', 'B', 'C', 'D', 'E']  <- goal, record a copy
 9      at D  path=ACD  on_path=['A', 'C', 'D']
        skip A: already on the path
10        at E  path=ACDE  on_path=['A', 'C', 'D', 'E']  <- goal, record a copy
['ABDE', 'ACBDE', 'ACDE'] calls: 10

Reading it: calls 1 to 4 go down A, B, D, E. At D the neighbour A is skipped because it is marked, which is the cycle handling, and E is the goal, so a copy of path is recorded. Returning from E, D and B removes their marks (the undo), so by call 5 only A is marked again. That is why call 6 can enter B a second time, this time through C: B is no longer marked. Calls 6 to 8 give the second route ACBDE, and calls 9 and 10 give ACDE. The total is 10 calls, one per line numbered 1 to 10, and 3 recorded paths.

Example 1: DFS used for traversal

dfs_reachable answers "which nodes can be reached from A, and in what order?" It adds a node to visited on entry and never removes it, so the walk touches each node once even though the graph has a cycle. The order is A, B, D, E, C. Cost is O(V + E) time and O(V) space (the visited set plus recursion depth).

Example 2: backtracking that constructs and undoes a partial solution

all_simple_paths answers "list every route from A to E that never repeats a node". The partial solution is path. Each step does choose (append the neighbour and mark it on the path), explore (recurse), undo (pop it and unmark it). It finds three routes: A,B,D,E, A,C,B,D,E and A,C,D,E. Note that B and D appear in several routes, which is only possible because the marks are undone.

The same template with no graph at all is permutation generation: the partial solution is the prefix built so far, and "already used" is a set that is added to and removed from.

How cycle handling differs

• Traversal: mark permanently. A node reached a second time through a different route adds nothing new, so skip it forever. This is what makes DFS linear.
• Backtracking: mark only while the node is on the current path. The question is not "have I ever seen it" but "is it already in the partial solution I am building". The mark is removed on the way back, which is exactly the undo step.
• Using the traversal habit in a path search is a correctness bug. paths_with_permanent_visited finds only one of the three routes, because the first route A,B,D,E marks B, D and E and the marks are never removed: A,C,B,D,E needs B again and A,C,D,E needs D again, so both are blocked.
• Using no check at all never finishes the search. paths_with_no_cycle_check keeps going around A, B, D, A, ..., so the recursion has no bottom. Python stops it by raising RecursionError when the call depth reaches its limit (set to 200 for the demo; the default is 1000); a language with no such limit would run until the stack memory is exhausted.
• The cost of correctness is growth. The last table chains diamonds that each offer two routes (a diamond is a node with two parallel one-step routes that meet again at the next node). DFS visits 3 more nodes per diamond (7, 13, 25 and 37 nodes for 2, 4, 8 and 12 diamonds), while backtracking calls double with each diamond (13, 61, 1,021 and 16,381 calls for the same sizes). Why the calls double: let T(k) be the calls from the first junction through k diamonds. That call makes two child calls (the upper and lower node), each of which makes one call into the rest of the chain, so T(k) = 1 + 2 * (1 + T(k-1)) = 2 * T(k-1) + 3, with T(0) = 1 (the goal alone). That solves to T(k) = 4 * 2^k - 3, which gives 13, 61, 1,021 and 16,381 for k = 2, 4, 8, 12, the numbers printed. DFS with a permanent visited set touches each of the 3k + 1 nodes once, so it grows by 3 per diamond. Exponential growth is why backtracking needs pruning and why a problem like "count the paths" often switches to memoization (caching answers per node) when the graph has no cycles.

Where the search space is itself a tree of choices (subsets, permutations, N-Queens), there is no cycle to detect, because every extra choice makes a strictly bigger partial solution. Only the undo step remains.

Complexity

DFS traversal: O(V + E) time, O(V) space. Backtracking path enumeration: in the worst case it explores every simple path, which is exponential in V (2^k paths for k chained diamonds above); space is O(V) for path, on_path and the recursion depth, plus the output.

Common mistakes

• Treating "visited" as a global flag in a solution-enumeration search, which silently drops valid solutions.
• Forgetting to undo the mark when returning, so later branches see a polluted state.
• Calling a traversal "backtracking" because it returns from recursion. Returning is not backtracking; undoing a choice to try an alternative is.
• Assuming backtracking is always exponential. With strong pruning it can be fast, but its worst case is not bounded by V + E.

Running the code

python3.12 dfs_vs_backtracking.py

Standard library only.

Direct answer. A code smell is a surface signal, not a bug in itself, that usually points to a deeper structural problem: the code works today but will resist the next change. It's a heuristic for WHERE to look, not proof that something is wrong.

Five smells common under deadline pressure

1. Long method -- a function that keeps growing because it's easier to add one more if than to stop and restructure. Remediation: extract by responsibility (see S5) as soon as a function needs a comment to separate its 'sections.'
2. Duplicated code -- the same logic copy-pasted with small tweaks because extracting a shared abstraction felt slower under a deadline. Remediation: extract the shared part once there are two clear copies (the classic 'rule of three' guards against over-extracting on the first duplicate).
3. God object/class -- one class or module that ends up owning unrelated responsibilities because it was the easiest place to bolt on 'just one more thing.' Remediation: split along 'reason to change' (SRP), migrating callers incrementally rather than in one big rewrite.
4. Shotgun surgery -- a single conceptual change (e.g., adding a new payment method) requires touching a dozen files because the concept isn't encapsulated anywhere. Remediation: consolidate the scattered logic behind one seam (a class, interface, or module) so future changes touch one place.
5. Primitive obsession -- passing raw strings/ints around for things that are really domain concepts (an email, a currency amount, a user ID), losing the validation and meaning a real type would carry. Remediation: introduce small value types/wrappers so invalid states become unrepresentable rather than merely 'usually correct.'

Why deadline pressure specifically produces these

Under pressure, the fastest LOCAL change is almost always to keep extending what's already there (one more branch, one more copy-paste, one more method on the class you already have open) rather than to pause and restructure. Each individual shortcut is locally rational; the smell accumulates because nobody's shortcut budget includes 'time to undo the last five shortcuts.'

Trade-offs and pitfalls

• Smells are a starting point for investigation, not an automatic verdict -- a long method that's a single linear sequence of well-named steps with no branching can be more readable than five tiny indirections that force you to jump around a file.
• Don't chase every smell with equal urgency; prioritize by where the churn and bug density actually are (see the complexity-metrics survivor for how to find that objectively) rather than refactoring whatever offends you first.
• Naming a smell is only useful if it's followed by a concrete remediation plan; 'this is a god object' without a proposed split is just a complaint.

Direct answer

With 30 days and a small team you cannot make a legacy app secure; you can close the most likely and most damaging attack paths (an attack path is a chain of steps an attacker could follow, such as an exposed login page, a weak password, then customer data) and leave an honest list of what remains. Pick subprojects by risk removed per person-day, start with finding what is exposed, and write the deferrals down with a trigger for revisiting each. At day 30 claim "top attack paths closed", never "secured".

Structured elaboration

Order of thinking. First learn what you protect and who would attack it (customer data, payments, admin functions), because that decides what "highest value" means. Then list candidate subprojects and rank them by exposure, severity and effort.

Subprojects (highest value first)

1. Inventory and exposure. What is reachable from the internet (admin pages, old test servers), which components and versions run. Close anything that never needed to be public.
2. Known-vulnerable components. Scan dependencies and server software, patch or upgrade those with known public exploits (ready-made attack code anyone can download).
3. Authentication and secrets. Multi-factor authentication (MFA: a password plus a second proof such as a phone code) for admin access, remove shared or default credentials, rotate secrets found in code and config.
4. Compensating control in front. A web application firewall (a filter that blocks common attack patterns) is a compensating control, a safeguard that reduces risk when the flaw itself cannot be fixed yet, and it buys time for flaws you cannot fix in 30 days. (Formally, a compensating control stands in for a recommended control and is expected to give comparable protection; a firewall in front usually gives less, which is why it is recorded as temporary.)
5. Top application flaws. Fix the worst findings of a scan or review (injection, where attacker-supplied text gets run as a database command or code; broken access control, where users can reach data or actions they should not) on the most sensitive functions.
6. Detect and recover. Basic logging and alerts, plus a backup that you have actually restored once.

Explicitly deferred (with a reason and a trigger): rewrite or re-architecture (needs months; revisit after a residual-risk review, a check of the risk that remains after the fixes), low-severity findings (batch into normal sprints), single sign-on migration (one login shared across systems; large and not an attack-path closer), compliance certification (needs evidence over time), network micro-segmentation (splitting the network into small zones so one breach cannot spread; design work first).

Triggers to revisit each deferral: rewrite, the residual-risk review at day 30; low-severity findings, the first normal sprint planning after day 30; single sign-on migration, the residual-risk review showing shared credentials as the top remaining risk; compliance certification, an audit or customer contract that sets a date; network micro-segmentation, the inventory showing sensitive systems on the same network as exposed ones.

Worked example

Illustrative: 3 people x 20 working days = 60 person-days.

The total is 60. The deliverable for leadership: what was closed, evidence for each, and the deferred list, each item with a named owner, a reason and its revisit trigger.

Variation: building an insider-risk detection capability from scratch. Decompose into data sources (identity and access logs, file access, endpoint activity, HR events like departures), signals (such as unusual download volume against the person's own baseline, or access outside their role), privacy constraints, tuning and review. Sequence privacy and legal constraints first, because they gate which data sources are allowed; then start with a few high-precision signals (signals that are rarely wrong when they fire), tune against a baseline period (a stretch of normal activity used to set thresholds), and route alerts to a small trained review group rather than automatic action. One signal worked through (illustrative): an employee normally downloads about 20 files a day; the rule fires when a day exceeds 10 times their own 30-day average and is at least 100 files, so 400 files in one day on the week they hand in notice fires, while 60 files on a busy day does not. Review the alerts raised in the baseline period: if 3 of 10 were real concerns the precision is 30%, and you tighten the threshold before anyone is contacted.

Trade-offs and pitfalls

• Scanning everything and fixing in severity order ignores effort and exposure; a medium flaw on an internet-facing login can outrank a high one deep inside.
• A WAF is a bandage, not a fix. Record it as a compensating control.
• Overpromising "secure in 30 days" damages credibility when the first finding arrives.
• If the app handles regulated data, some deferred items may not be deferrable; confirm obligations before finalizing the list.
• What would flip priorities: evidence of active exploitation, which moves incident response ahead of everything else.

The idea in plain words

In a sorted list, equal values are always next to each other, so a duplicate is always the node right after one that holds the same value. That means one walk with a single pointer is enough: if the next node repeats the current value, skip it by making cur.next point at cur.next.next; otherwise move forward. No set and no second pointer are needed, which is what gives O(1) extra space.

"In place" means you rewire the existing nodes' next pointers rather than building a new list.

Approach, step by step

1. Start cur at the head. Loop while cur and cur.next both exist (the check on cur.next protects the comparison below).
2. If cur.next.value == cur.value, set cur.next = cur.next.next. Do not move cur: the node after the one you skipped may be a duplicate too.
3. Otherwise set cur = cur.next.
4. Return the head. The head never changes, because the first node of any run is the one we keep.

The code

Each node carries a letter tag so the printout shows which node of a run survives (the first). The trace prints cur and the whole list after every loop iteration.

import random


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


def build(values):
    head = tail = None
    for i, v in enumerate(values):
        node = Node(v, chr(ord("a") + i))
        if head is None:
            head = tail = node
        else:
            tail.next = node
            tail = node
    return head


def show(head):
    out, cur = [], head
    while cur:
        out.append(f"{cur.value}{cur.tag}")
        cur = cur.next
    return " -> ".join(out) + " -> None"


def dedupe_sorted(head, trace=False):
    """Keep the first node of each run of equal values. O(n) time, O(1) space."""
    cur = head
    while cur and cur.next:
        if cur.next.value == cur.value:
            cur.next = cur.next.next          # skip the duplicate; stay on cur
        else:
            cur = cur.next                    # next value differs; move on
        if trace:
            print(f"  cur={cur.value}{cur.tag}  list={show(head)}")
    return head


def dedupe_unsorted(head):
    """Same goal for unsorted input: a set of values already kept. O(n) time, O(d) space."""
    seen, prev, cur = set(), None, head
    while cur:
        if cur.value in seen:
            prev.next = cur.next
        else:
            seen.add(cur.value)
            prev = cur
        cur = cur.next
    return head


def values(head):
    out = []
    while head:
        out.append((head.value, head.tag))
        head = head.next
    return out


print("start:", show(build([1, 1, 2, 3, 3, 3, 4])))
print("trace:")
result = dedupe_sorted(build([1, 1, 2, 3, 3, 3, 4]), trace=True)
print("done: ", show(result))
print("empty list:", dedupe_sorted(None))
print("all equal: ", show(dedupe_sorted(build([5, 5, 5]))))

print("sorted routine on unsorted input 1, 2, 1:", show(dedupe_sorted(build([1, 2, 1]))))
print("set routine on unsorted input 1, 2, 1:   ", show(dedupe_unsorted(build([1, 2, 1]))))

random.seed(43)
for _ in range(500):
    vals = sorted(random.randint(0, 5) for _ in range(random.randint(0, 12)))
    expected, last = [], object()
    for i, v in enumerate(vals):
        if v != last:
            expected.append((v, chr(ord("a") + i)))
            last = v
    assert values(dedupe_sorted(build(vals))) == expected
print("500 random sorted lists match a reference that keeps the first of each run")

Worked trace

The program printed:

start: 1a -> 1b -> 2c -> 3d -> 3e -> 3f -> 4g -> None
trace:
  cur=1a  list=1a -> 2c -> 3d -> 3e -> 3f -> 4g -> None
  cur=2c  list=1a -> 2c -> 3d -> 3e -> 3f -> 4g -> None
  cur=3d  list=1a -> 2c -> 3d -> 3e -> 3f -> 4g -> None
  cur=3d  list=1a -> 2c -> 3d -> 3f -> 4g -> None
  cur=3d  list=1a -> 2c -> 3d -> 4g -> None
  cur=4g  list=1a -> 2c -> 3d -> 4g -> None
done:  1a -> 2c -> 3d -> 4g -> None
empty list: None
all equal:  5a -> None
sorted routine on unsorted input 1, 2, 1: 1a -> 2b -> 1c -> None
set routine on unsorted input 1, 2, 1:    1a -> 2b -> None
500 random sorted lists match a reference that keeps the first of each run

Reading the trace: the first iteration finds 1b equal to 1a, unlinks it, and cur stays on 1a. The next iteration sees 2c differs and moves to 2c; then 3d is reached by a move. Two more iterations unlink 3e and then 3f while cur stays on 3d. The last iteration moves onto 4g, whose next is None, so the loop ends with 1a -> 2c -> 3d -> 4g -> None. The first node of every run (1a, 3d) survived. The empty list and a list of equal values are handled as printed, and the last line records a check against a reference on 500 random sorted lists.

Complexity

Time O(n) and extra space O(1). Each loop iteration either unlinks a node or advances cur, so there are at most n - 1 iterations. The loop is iterative. A recursive version looks natural but costs O(n) stack. Each call to a function gets a stack frame, the record Python keeps of that call (its variables and where to return to), and the frames pile up until the calls return. Python caps the pile at a recursion limit (1000 by default) and raises RecursionError beyond it. The version below keeps the first node of each run, like the loop: when the next node repeats the value it unlinks it and calls itself on the same node again, otherwise it recurses on the next node and keeps its own node. The trace indents each call by its depth, so the pile of frames is visible on a five-node list, and then two long lists show the limit:

import sys


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


def show(head):
    out = []
    while head:
        out.append(f"{head.value}{head.tag}")
        head = head.next
    return " -> ".join(out) + " -> None"


def dedupe_recursive(node, depth=0, trace=False):
    """Keep the first node of each run, recursively. One stack frame per call."""
    if trace:
        label = f"{node.value}{node.tag}" if node else "None"
        print("  " * depth + f"call on {label}")
    if node is None or node.next is None:
        return node
    if node.next.value == node.value:
        node.next = node.next.next                          # skip the duplicate
        return dedupe_recursive(node, depth + 1, trace)     # same node again
    node.next = dedupe_recursive(node.next, depth + 1, trace)
    return node


def build(n, with_tags=False):
    head = None
    for v in range(n, 0, -1):
        head = Node(v // 2, chr(ord("a") + v - 1) if with_tags else "", head)   # values come in equal pairs
    return head


small = build(5, with_tags=True)
print("start:", show(small))
print("recursive trace (indent = depth):")
small = dedupe_recursive(small, trace=True)
print("done: ", show(small))

print("recursion limit:", sys.getrecursionlimit())
for n in (500, 5000):
    try:
        dedupe_recursive(build(n))
        print(n, "nodes: ok")
    except RecursionError:
        print(n, "nodes: RecursionError")

Run output:

start: 0a -> 1b -> 1c -> 2d -> 2e -> None
recursive trace (indent = depth):
call on 0a
  call on 1b
    call on 1b
      call on 2d
        call on 2d
done:  0a -> 1b -> 2d -> None
recursion limit: 1000
500 nodes: ok
5000 nodes: RecursionError

On the five-node list the deepest call is indented four levels, so five frames are on the stack at once, one per node examined or skipped, and it ends with the same 0a -> 1b -> 2d that the loop keeps (first node of each run). CPython's default limit is 1000 frames, so the recursive form handles 500 nodes and fails at 5000. The loop above has no such limit.

If the list were unsorted

Equal values may be far apart, so "compare with the next node" misses them. The same sorted routine run on 1, 2, 1 leaves 1a -> 2b -> 1c unchanged (printed above). Two fixes:

• Remember what you have kept in a set: walk once, unlink any node whose value is already in the set. Time O(n) expected, extra space O(d) for d distinct values. The function dedupe_unsorted in the listing does this and prints 1a -> 2b for the same input.
• Re-scan for each node with a second pointer, O(n^2) time and O(1) space, when memory is the constraint.

Sorting first would restore the "equal values are adjacent" property in O(n log n), at the price of losing the original order.

Edge cases and common mistakes

• Empty list and single node: the loop condition stops immediately.
• Advancing cur after a skip. With 1 -> 1 -> 1, advancing right after the first skip leaves the third node in the list.
• Dereferencing (following a pointer to read the node it points at) cur.next.value when cur.next is None, which raises AttributeError.
• Assuming the input is sorted when it is not. The routine does not check; it silently leaves non-adjacent duplicates.
• Deleting the first of the run instead of later ones, which would need the previous node and special handling for the head.

Follow-ups

Remove every value that appears more than once (keep none of the repeated ones): now the head can be deleted, so a dummy node before the head removes that special case. Doubly linked list: the unlink also updates the prev pointer of the following node.

Running the code

# save the listings above as dedupe_sorted.py and recursion_limit.py (Python 3.12, standard library only)
python dedupe_sorted.py
python recursion_limit.py

Approach

Open addressing stores every entry directly inside one flat array (no linked chains); on a collision, double hashing computes a second, independent probe step so different keys that collide at the same starting slot still spread out across the table instead of clustering along a fixed stride. Concretely, slot i for probe attempt p is (h1(key) + p * h2(key)) mod capacity, where h2 is forced to never be zero and, with a prime table capacity, is guaranteed to eventually visit every slot. Deletion cannot simply null out a slot, because later entries may have probed past that slot to resolve their own collision; nulling it would break their probe chain and make get stop early and report them missing. The fix is a tombstone: a special "deleted, but keep probing past me" marker distinct from both "live entry" and "truly empty."

Code (Java)

public class DoubleHashTable {
    private static final Object TOMBSTONE = new Object();
    private Object[] keys;
    private Object[] values;
    private int capacity;
    private int size;   // live entries
    private int used;   // live entries + tombstones, drives resize

    public DoubleHashTable(int capacity) {
        this.capacity = capacity;
        this.keys = new Object[capacity];
        this.values = new Object[capacity];
    }

    private int h1(Object key) {
        return (key.hashCode() & 0x7fffffff) % capacity;
    }

    private int h2(Object key) {
        int h = key.hashCode();
        return 1 + ((h & 0x7fffffff) % (capacity - 1));  // never 0
    }

    public void put(String key, Integer value) {
        if ((double) (used + 1) / capacity > 0.6) resize();
        int idx = h1(key), step = h2(key), firstTombstone = -1;
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) {
                int target = (firstTombstone != -1) ? firstTombstone : slot;
                if (keys[target] == null) used++;
                keys[target] = key; values[target] = value; size++;
                return;
            } else if (keys[slot] == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = slot;
            } else if (keys[slot].equals(key)) {
                values[slot] = value;
                return;
            }
        }
        throw new IllegalStateException("table full, resize invariant violated");
    }

    public Integer get(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return null;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) return (Integer) values[slot];
        }
        return null;
    }

    public boolean delete(String key) {
        int idx = h1(key), step = h2(key);
        for (int probe = 0; probe < capacity; probe++) {
            int slot = (idx + probe * step) % capacity;
            if (keys[slot] == null) return false;
            if (keys[slot] != TOMBSTONE && keys[slot].equals(key)) {
                keys[slot] = TOMBSTONE; values[slot] = null; size--;
                return true;
            }
        }
        return false;
    }

    private void resize() {
        Object[] oldKeys = keys, oldValues = values;
        capacity = nextPrime(capacity * 2);
        keys = new Object[capacity]; values = new Object[capacity];
        size = 0; used = 0;
        for (int i = 0; i < oldKeys.length; i++) {
            if (oldKeys[i] != null && oldKeys[i] != TOMBSTONE) {
                put((String) oldKeys[i], (Integer) oldValues[i]);
            }
        }
    }

    private static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; (long) i * i <= n; i++) if (n % i == 0) return false;
        return true;
    }

    private static int nextPrime(int n) {
        int candidate = Math.max(n, 2);
        while (!isPrime(candidate)) candidate++;
        return candidate;
    }

    public int size() { return size; }
    public int capacity() { return capacity; }

    public static void main(String[] args) {
        DoubleHashTable t = new DoubleHashTable(7);
        t.put("a", 1); t.put("b", 2); t.put("c", 3);
        System.out.println("get a -> " + t.get("a"));
        System.out.println("get missing -> " + t.get("zzz"));
        t.delete("b");
        System.out.println("get b after delete -> " + t.get("b"));
        t.put("d", 4);
        System.out.println("get d after reusing tombstone slot -> " + t.get("d"));
        System.out.println("get a still resolves past tombstone -> " + t.get("a"));
        for (int i = 0; i < 30; i++) t.put("k" + i, i * 10);
        System.out.println("size after bulk insert -> " + t.size() + " capacity -> " + t.capacity());
        boolean allCorrect = true;
        for (int i = 0; i < 30; i++) if (!Integer.valueOf(i * 10).equals(t.get("k" + i))) allCorrect = false;
        System.out.println("all 30 post-resize keys correct -> " + allCorrect);
        System.out.println("c survived resize -> " + (t.get("c") == 3));
        System.out.println("b stays deleted after resize -> " + (t.get("b") == null));
    }
}

Output (compiled with javac and executed as shown; starting capacity 7):

get a -> 1
get missing -> null
get b after delete -> null
get d after reusing tombstone slot -> 4
get a still resolves past tombstone -> 1
size after bulk insert -> 33 capacity -> 79
all 30 post-resize keys correct -> true
c survived resize -> true
b stays deleted after resize -> true

Key points

• Tombstones on delete: a deleted slot is marked with a distinct TOMBSTONE sentinel (not null), so get keeps probing past it instead of stopping early, while put is free to reclaim that slot for a brand-new key. The demo confirms both halves: get("b") correctly returns null after delete, and get("a") still resolves even though its probe sequence now passes through b's tombstone.
• Rehashing strategy during resize: the table grows to the next prime at least double the old capacity (kept prime so h2's stride never shares a factor with the table size), and every live entry is walked and re-inserted through the normal put path; tombstones are dropped rather than copied, since a resize is exactly the natural point to reclaim their space. This is why used (live plus tombstones) rather than size (live only) drives the resize trigger: a table can fill up with tombstones alone and still needs to compact even though size looks small.
• Amortized O(1) argument: each resize costs (O(n)) (every live entry is rehashed once), but a resize only fires after roughly doubling the entries admitted since the last one, so the total rehashing work after (n) inserts is bounded by (n + n/2 + n/4 + \cdots < 2n), a constant multiple of (n). Spread over (n) inserts, that is (O(1)) amortized per insert, on top of the already-(O(1))-average probe cost.
• Production concurrency: this implementation is single-threaded only. Making open addressing thread-safe is harder than chaining, because a resize physically relocates every entry, so a reader mid-probe during a concurrent resize can land on a slot that no longer means what it did. Practical options are a single coarse lock around every operation (simple, but serializes all access), sharding into N independently-locked sub-tables (much better throughput, standard production pattern), or a lock-free design with versioned/CAS slots and a copy-on-resize scheme, which is substantially more complex to get correct and is usually reached for only when a proven mature implementation (like java.util.concurrent.ConcurrentHashMap, which uses chaining internally rather than open addressing for exactly this reason) is not applicable to the constraints.

Complexity

• Average case, insert/get/delete: (O(1)), assuming a good hash and load factor kept under the resize threshold (here 0.6) so probe sequences stay short.
• Worst case: (O(n)), a pathological hash or a table nearly saturated with tombstones can force a scan of most of the table.
• Resize: (O(n)) when triggered, (O(1)) amortized per insert overall, per the argument above.

Edge cases

• Deleting then reinserting a different key: must be able to reuse the tombstoned slot (put("d", 4) above lands where b was deleted).
• A key whose probe sequence crosses a tombstone left by an unrelated deleted key: must still resolve correctly (get("a") after b's deletion).
• A table that has accumulated many tombstones without much live growth: resizing on used rather than size prevents probe sequences from silently degrading toward (O(n)) even while the map looks small.
• Deleting a key that was never present: the loop reaches an empty (null) slot and returns false without touching the table.

Direct answer

I would restructure the write-up around a layered format: a short, jargon-free summary any executive can read in under a minute, followed by the full technical depth below for engineers, rather than trying to write one document that serves both audiences at the same density. The same layering principle applies whether the artifact is a written report or a live presentation to leadership.

Structured elaboration

The core tension is that an incident write-up detailed enough for engineers to actually learn from and prevent recurrence is, by design, too dense for an executive who needs the headline in the time it takes to skim it. Solving that by simply cutting the document down risks swinging too far the other way and leaving engineers without the technical depth they need to fix the root cause, which is the same failure in the opposite direction as the manager's original complaint. A structure that avoids favoring one audience at the other's expense:

• Executive summary at the top: what broke, customer or business impact, current status, and the single most important next step, with no jargon and no root-cause mechanism detail.
• Timeline: a short, chronological list of what happened and when, from detection through resolution, useful to both audiences at a glance.
• Root cause and technical detail: the full engineering depth, exact failure mechanism, logs, code paths, and why the mitigation works, placed below the summary so an executive can stop reading before they reach it and an engineer can keep going.
• Action items: owner and rough timeframe per item, visible to both audiences since executives care that follow-through is happening even without the technical detail behind each item.

This tiering is not specific to written reports. The equivalent for a live presentation to leadership is opening with the executive-summary content, then explicitly offering to go deeper on the technical root cause for whoever in the room needs it, an engineering lead present for technical sign-off, rather than either dumbing the whole talk down or delivering the same dense technical walkthrough regardless of audience. Done well, that structure earns both technical approval and executive buy-in from a single session instead of requiring two separate versions.

Worked example

My manager told me a recent incident write-up was eleven pages long and that an executive reader gave up after the first paragraph. I restructured it using the layered format above: a four-sentence executive summary at the top stating customer impact, current status, and the one thing being done to prevent recurrence; a short timeline; then the full technical root-cause section below, unchanged in depth, a misconfigured retry policy that amplified load into an already-degraded downstream service, so engineers still had everything they needed to review the fix. I used the same layered structure on a related situation with the opposite problem: a data-engineering debugging write-up that was technical enough for engineers to follow but so light on business impact that a data-platform stakeholder could not tell whether it mattered, and applied the same impact-first, mechanism-below fix there too. When I later had to present a similar incident live to leadership, I opened with the same executive-summary content in about ninety seconds, then said "I can go deeper on the technical root cause for anyone who wants it" and walked the engineering lead present through the mechanism afterward, so the same session delivered both executive buy-in on the plan and technical sign-off, instead of needing two separate meetings.

Trade-offs and pitfalls

Cutting a long write-up down without a deliberate structure risks solving the executive's complaint by quietly dropping the technical depth engineers actually need, trading one legitimate audience's needs for another's instead of serving both. An executive summary that is too vague to be useful is as much a failure as one that is too long; it needs the specific handful of facts an executive actually needs to decide whether to worry, not a softened restatement of the whole incident. For a live presentation, offering to go deeper only works if you can actually read the room and tell who needs it; defaulting to full technical depth for everyone wastes executives' time just as much as the original overlong document did.

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.