Google Software Engineer Interview Preparation Guide - Junior Level (1-2 years)

The first five minutes of an angry-client call aren't for solving the problem, they're for proving you've registered the complaint and gathering the specifics needed to actually solve it: an opening acknowledgment, reflective statements, open questions, and only then a concrete next step.

Verbatim opening (first five minutes)
[0:00] "Thanks for getting on with me, I know you're frustrated, and I want to understand exactly what's happened before we talk about fixing it."
[0:30] Client explains three tickets submitted since the 3rd with no response.
[1:00] Reflective: "So to make sure I've got this right: three tickets since the 3rd, no response on any of them, and it's affecting your team's ability to hit their own deadline. That's a real miss on our end, and I'm sorry it went unanswered this long. I can also see this breached our response-time SLA (the response-time commitment in your agreement), and that's on us, not you."
[2:00] Open question: "Can you walk me through which of the three is most urgent right now, and what does resolved actually look like for that one?"
[3:00] Open question: "Is this the first time you've had a gap like this, or has it happened before?"
[4:00] Next step: "Here's what I'm doing: pulling up all three tickets right now while we're on this call, giving you a status on each before we hang up, and personally checking in with you in 48 hours regardless of where things stand. Does that work as a starting point?"

Trade-offs and pitfalls
Apologizing before reflecting the specifics back can feel hollow, a "sorry" with no evidence you understood what happened. Reflect first, then apologize for the specific thing you now understand happened. Promising a fix timeline you don't yet control, instead of a check-in commitment you do control, is a common overcorrection under pressure, don't commit to an outcome before you have the information to back it.

Direct answer

Before your work depends on it, put a written interface contract in place (the shape of the data or API, error cases, and versioning), a single named owner on each side, and an SLA (service level agreement: the vendor's contractual uptime/response commitment) for questions and changes with a defined escalation path. Then build against a mock or stub (a fake stand-in for the real API that returns data matching the agreed contract, so your team can build and test without waiting on the real thing) that matches that contract, so a late dependency delays true integration, but doesn't block your team's progress.

Framework

Before you start building. Agree the contract explicitly (schema, error handling, versioning), name one owner per side rather than 'the team', and set an SLA for response time and change turnaround, with an escalation path if it slips.

While you wait. Build and test against a mock or stub that matches the agreed contract, so your team keeps moving. Pair it with automated contract tests, so if the mock and the real dependency drift apart, you find out at build time instead of at release.

Internal-team dependency vs external vendor dependency. The mechanics differ once the other side is a vendor rather than a team you can walk over to.

Worked example

Situation: a product depends on a vendor-managed API (for example a payments or identity provider). The vendor's contract commits to 99.5% availability, but the product's own reliability target requires 99.95%.
Quantifying the gap: a year has 8,760 hours. At 99.5% availability, permitted downtime is 0.5% of 8,760 = 43.8 hours per year. At 99.95%, permitted downtime is 0.05% of 8,760 = 4.38 hours per year. The vendor's contract therefore permits about 43.8 minus 4.38 = 39.42 hours per year more downtime than the product can actually tolerate.
Action: negotiated for a higher committed SLA where possible; where the vendor would not move the number, negotiated a compensation or credit clause tied to a downtime threshold, documented in writing. Regardless of the contract terms, added caching on the read path so a short vendor blip doesn't cascade immediately, and a fallback path that degrades the feature gracefully instead of erroring during an outage window.
Result: the contract negotiation raises the ceiling on paper, but the caching and fallback layer is what actually protects users during the gap between what the vendor promises and what the product needs, since a credit clause compensates you after an outage, it doesn't prevent one.

Trade-offs and pitfalls

• Mocks and stubs only help if kept in sync with the real contract. A stale mock creates a different kind of surprise at integration time.
• Vendor SLA credits are usually a small fraction of the real cost of downtime (lost trust, lost usage). Treat them as compensation, not as risk mitigation on their own, and pair them with technical fallbacks.
• Applying heavy contract-and-SLA process to a short, low-risk internal dependency slows down partners who need speed more than ceremony. Calibrate the rigor to the risk and duration of the dependency, not the same weight for every one.

Direct answer

Deciding whether to escalate a stakeholder disagreement or keep resolving it yourself comes down to three thresholds: whether the disagreement blocks real progress rather than just being uncomfortable, whether you've genuinely exhausted peer-level resolution attempts, and whether the decision's impact or reversibility justifies pulling in someone with broader authority.

Structured elaboration

1. Blocking versus uncomfortable. Genuine disagreement that's actively stalling a decision or delivery is different from disagreement that's merely unpleasant to sit in; escalate the former, and treat the latter as a normal part of collaborative work you should be resolving yourself.
2. Have you actually tried peer-level resolution? Escalating on the first sign of friction, before making a real attempt to resolve it directly, reads as avoidance and burns trust with the people you escalated past; a genuine, documented attempt should come first.
3. Impact and reversibility. A disagreement over a low-stakes, easily-reversible choice rarely needs escalation even if it's dragging on; a disagreement over something expensive or hard to undo justifies pulling in a decision-maker sooner rather than waiting for it to resolve itself.
4. Time-boxing your own attempt. Set an explicit, reasonable deadline for resolving it yourself before defaulting to escalation, so escalation isn't triggered by frustration in the moment but by a genuine, pre-committed threshold being crossed.
5. How you escalate matters. Frame it as "I need help resolving a genuine disagreement, here's what we've tried" rather than "person X is being unreasonable," which keeps the escalation about the decision, not about assigning blame.

Worked example

Two stakeholders disagree on a metric definition that's holding up a launch. After a genuine attempt at a joint conversation surfacing both sides' reasoning fails to converge within a couple of days, and the launch date is a real, externally-communicated commitment, escalating with a short, neutral summary ("here's the disagreement, here's what we tried, here's what's at stake if it's not resolved by Thursday") to whoever has authority over both parties is the right call, rather than continuing to shuttle between them indefinitely.

Trade-offs and pitfalls

Escalating too readily trains your own stakeholders to skip you and go straight to leadership themselves next time, since they've seen it doesn't take much. Escalating too late lets a genuinely blocking disagreement quietly cost real time; the discipline is having an honest, pre-committed threshold rather than deciding case by case under pressure.

The idea

The table of distances already records which choice won in every cell, so the edits come from walking the table backwards. Start at the bottom-right cell. At each cell, find a neighbour that explains its value: the diagonal cell (a match for free, or a substitution for +1), the cell above (a deletion, +1) or the cell to the left (an insertion, +1). Step there, write down the column of the alignment (a column pairs one character of each string, or a character with a gap -), and repeat until you reach the top-left corner. Reading the columns from the corner gives the alignment, and every column that is not a match is one edit. A gap is a - standing where the other string has a character: a gap in the top row is an insertion, a gap in the bottom row is a deletion.

The five things to state

1. What one cell means. dp[i][j] is the fewest edits that turn the first i characters of a into the first j characters of b.
2. The transition. dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost) where cost is 0 for equal characters and 1 otherwise.
3. Base cases. dp[i][0] = i and dp[0][j] = j.
4. Fill order. Row by row, left to right.
5. Where the answer is. The distance is dp[n][m]; the edits come from walking back from that cell to dp[0][0], the reverse of the fill order.

Recovering the alignment

The move at cell (i, j) is valid when it reproduces the cell's value:

• diagonal when dp[i][j] == dp[i-1][j-1] + cost: the pair (a[i-1], b[j-1]) is a column (a match or a substitution);
• up when dp[i][j] == dp[i-1][j] + 1: delete a[i-1], so the column is (a[i-1], -);
• left when dp[i][j] == dp[i][j-1] + 1: insert b[j-1], so the column is (-, b[j-1]).

On the top row only left is possible and on the first column only up. The code walks back using the values alone, with no pointers stored, and the trace below it prints each cell, the valid moves at that cell and the one taken. For sunday to saturday the walk gives s--unday over saturday: two insertions (a, t) and one substitution (n becomes r), for a distance of 3. show prints the alignment with a middle row of marks: | under two equal characters (a match, free), * under two different characters (a substitution, one edit) and a blank wherever either row has a gap (an insertion or a deletion, one edit each). In the output below, s--unday over saturday has marks | |*|||: s and s match, the two gaps are blank, then u, n over u, r gives | and *, and d, a, y match. script_from_alignment turns the columns into positional edits on the original string, and apply_script applies them right to left so earlier positions are not shifted; the result is saturday.

When several answers tie

If more than one move is valid at a cell, each leads to a different but equally cheap alignment. For abc to acb there are three: one with two substitutions, and two with one deletion and one insertion. The walk's preference order picks one: diagonal first gives abc over acb, up first gives a-bc over acb-, left first gives abc- over a-cb. count_optimal counts them with a second table (ways[i][j] sums the ways of every valid predecessor) and the 300-pair check compares that count and the set of alignments against a brute-force enumeration. State the rule you used; unless the problem names one, any optimal alignment is a correct answer.

The code

import random


def edit_table(a, b):
    """dp[i][j] = fewest edits turning a[:i] into b[:j]."""
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(len(a) + 1):
        dp[i][0] = i
    for j in range(len(b) + 1):
        dp[0][j] = j
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            cost = 0 if a[i - 1] == b[j - 1] else 1
            dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + cost)
    return dp


def align(a, b, dp, order=("diag", "up", "left"), trace=None):
    """Walk back from the corner. At each cell take the first move in `order`
    that reproduces the cell's value. Returns two equal-length strings, '-' = gap."""
    i, j, top, bottom = len(a), len(b), [], []
    while i > 0 or j > 0:
        cost = 0 if i > 0 and j > 0 and a[i - 1] == b[j - 1] else 1
        valid = []
        if i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + cost:
            valid.append("diag")
        if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
            valid.append("up")
        if j > 0 and dp[i][j] == dp[i][j - 1] + 1:
            valid.append("left")
        move = next(m for m in order if m in valid)
        if trace is not None:
            trace.append(f"({i},{j}) value {dp[i][j]}, valid {valid}, take {move}")
        if move == "diag":
            top.append(a[i - 1]); bottom.append(b[j - 1]); i -= 1; j -= 1
        elif move == "up":
            top.append(a[i - 1]); bottom.append("-"); i -= 1
        else:
            top.append("-"); bottom.append(b[j - 1]); j -= 1
    return "".join(reversed(top)), "".join(reversed(bottom))


def show(top, bottom):
    marks = "".join(" " if "-" in (x, y) else ("|" if x == y else "*")
                    for x, y in zip(top, bottom))
    return f"{top}\n{marks}\n{bottom}"


def script_from_alignment(top, bottom):
    """Turn aligned rows into edits that use positions in the ORIGINAL first string."""
    ops, pos = [], 0
    for x, y in zip(top, bottom):
        if x == "-":
            ops.append(("insert", pos, y))
        elif y == "-":
            ops.append(("delete", pos, x)); pos += 1
        else:
            if x != y:
                ops.append(("replace", pos, y))
            pos += 1
    return ops


def apply_script(a, ops):
    s = list(a)
    for kind, pos, ch in reversed(ops):      # right to left keeps positions valid
        if kind == "replace":
            s[pos] = ch
        elif kind == "delete":
            del s[pos]
        else:
            s.insert(pos, ch)
    return "".join(s)


def count_optimal(a, b, dp):
    """ways[i][j] = number of different optimal alignments of a[:i] and b[:j]."""
    ways = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    ways[0][0] = 1
    for i in range(len(a) + 1):
        for j in range(len(b) + 1):
            if i == j == 0:
                continue
            total = 0
            if i > 0 and j > 0:
                cost = 0 if a[i - 1] == b[j - 1] else 1
                if dp[i][j] == dp[i - 1][j - 1] + cost:
                    total += ways[i - 1][j - 1]
            if i > 0 and dp[i][j] == dp[i - 1][j] + 1:
                total += ways[i - 1][j]
            if j > 0 and dp[i][j] == dp[i][j - 1] + 1:
                total += ways[i][j - 1]
            ways[i][j] = total
    return ways[-1][-1]


def all_optimal(a, b):
    """Reference: enumerate every alignment of minimum cost by plain recursion."""
    best, found = [10 ** 9], set()

    def go(i, j, top, bottom, cost):
        if cost > best[0]:
            return
        if i == len(a) and j == len(b):
            if cost < best[0]:
                best[0] = cost
                found.clear()
            found.add((top, bottom))
            return
        if i < len(a) and j < len(b):
            go(i + 1, j + 1, top + a[i], bottom + b[j], cost + (a[i] != b[j]))
        if i < len(a):
            go(i + 1, j, top + a[i], bottom + "-", cost + 1)
        if j < len(b):
            go(i, j + 1, top + "-", bottom + b[j], cost + 1)

    go(0, 0, "", "", 0)
    return best[0], found


cells = 0


def last_row(a, b):
    """Edit distances from a to every prefix of b, keeping one row at a time."""
    global cells
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            cells += 1
            cost = 0 if a[i - 1] == b[j - 1] else 1
            cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost)
        prev = cur
    return prev


def hirschberg_align(a, b):
    """Optimal alignment using only rows of length len(b)+1 for the split search."""
    if not a:
        return "-" * len(b), b
    if not b:
        return a, "-" * len(a)
    if len(a) == 1:                           # tiny table: 2 rows
        return align(a, b, edit_table(a, b))
    mid = len(a) // 2
    front = last_row(a[:mid], b)
    back = last_row(a[mid:][::-1], b[::-1])
    k = min(range(len(b) + 1), key=lambda k: front[k] + back[len(b) - k])
    t1, b1 = hirschberg_align(a[:mid], b[:k])
    t2, b2 = hirschberg_align(a[mid:], b[k:])
    return t1 + t2, b1 + b2


def cost_of(top, bottom):
    return sum(x != y for x, y in zip(top, bottom))


a, b = "sunday", "saturday"
dp = edit_table(a, b)
print("       " + "  ".join(["-"] + list(b)))
for i, row in enumerate(dp):
    print(f"{'-' if i == 0 else a[i - 1]}   " + "  ".join(str(v) for v in row))

trace = []
top, bottom = align(a, b, dp, trace=trace)
print("\ndistance:", dp[-1][-1], "\nwalk back (diagonal preferred):")
print("\n".join("  " + line for line in trace))
print(show(top, bottom))
ops = script_from_alignment(top, bottom)
print("edits:", ops, "->", apply_script(a, ops))

print("\nsunday -> saturday has", count_optimal(a, b, dp), "optimal alignment")
x, y = "abc", "acb"
tie_dp = edit_table(x, y)
print(x, "->", y, "has", count_optimal(x, y, tie_dp), "optimal alignments, distance", tie_dp[-1][-1])
for order in [("diag", "up", "left"), ("up", "left", "diag"), ("left", "up", "diag")]:
    print(f"order {order}:")
    print(show(*align(x, y, tie_dp, order)))
print("all optimal alignments:", sorted(all_optimal(x, y)[1]))

mid = len(a) // 2
front = last_row(a[:mid], b)
back = last_row(a[mid:][::-1], b[::-1])
sums = [front[k] + back[len(b) - k] for k in range(len(b) + 1)]
print(f"\nsplit search: a[:{mid}] = {a[:mid]!r}, a[{mid}:] = {a[mid:]!r}")
print("front[k] (first half vs b[:k]):         ", front)
print("back[m-k] (second half vs b[k:], k=0..m):", [back[len(b) - k] for k in range(len(b) + 1)])
print("sum per k:                              ", sums)
print("best k:", sums.index(min(sums)), "-> b splits into", repr(b[:sums.index(min(sums))]), "and", repr(b[sums.index(min(sums)):]))

ht, hb = hirschberg_align(a, b)
print("row-only alignment:", ht, "/", hb, "| cost", cost_of(ht, hb))

# Check against brute force on seeded random inputs.
rng = random.Random(21)
multi = 0
for _ in range(300):
    x = "".join(rng.choice("abc") for _ in range(rng.randint(0, 5)))
    y = "".join(rng.choice("abc") for _ in range(rng.randint(0, 5)))
    table = edit_table(x, y)
    best, found = all_optimal(x, y)
    assert best == table[-1][-1] and count_optimal(x, y, table) == len(found)
    multi += len(found) > 1
    for order in [("diag", "up", "left"), ("left", "up", "diag"), ("up", "diag", "left")]:
        t, bt = align(x, y, table, order)
        assert (t, bt) in found
        assert apply_script(x, script_from_alignment(t, bt)) == y
    ht, hb = hirschberg_align(x, y)
    assert cost_of(ht, hb) == best and ht.replace("-", "") == x and hb.replace("-", "") == y
print("\n300 random pairs: alignments, edit scripts and row-only alignments are optimal;",
      "pairs with more than one optimal alignment:", multi)

# Work done by the row-only method on two random strings of length 300.
rng = random.Random(8)
s = "".join(rng.choice("ACGT") for _ in range(300))
t = "".join(rng.choice("ACGT") for _ in range(300))
cells = 0
ht, hb = hirschberg_align(s, t)
print("n*m =", len(s) * len(t), "| row-only cell updates =", cells,
      "| cost matches table:", cost_of(ht, hb) == edit_table(s, t)[-1][-1])

Output

       -  s  a  t  u  r  d  a  y
-   0  1  2  3  4  5  6  7  8
s   1  0  1  2  3  4  5  6  7
u   2  1  1  2  2  3  4  5  6
n   3  2  2  2  3  3  4  5  6
d   4  3  3  3  3  4  3  4  5
a   5  4  3  4  4  4  4  3  4
y   6  5  4  4  5  5  5  4  3

distance: 3 
walk back (diagonal preferred):
  (6,8) value 3, valid ['diag'], take diag
  (5,7) value 3, valid ['diag'], take diag
  (4,6) value 3, valid ['diag'], take diag
  (3,5) value 3, valid ['diag'], take diag
  (2,4) value 2, valid ['diag'], take diag
  (1,3) value 2, valid ['left'], take left
  (1,2) value 1, valid ['left'], take left
  (1,1) value 0, valid ['diag'], take diag
s--unday
|  |*|||
saturday
edits: [('insert', 1, 'a'), ('insert', 1, 't'), ('replace', 2, 'r')] -> saturday

sunday -> saturday has 1 optimal alignment
abc -> acb has 3 optimal alignments, distance 2
order ('diag', 'up', 'left'):
abc
|**
acb
order ('up', 'left', 'diag'):
a-bc
| | 
acb-
order ('left', 'up', 'diag'):
abc-
| | 
a-cb
all optimal alignments: [('a-bc', 'acb-'), ('abc', 'acb'), ('abc-', 'a-cb')]

split search: a[:3] = 'sun', a[3:] = 'day'
front[k] (first half vs b[:k]):          [3, 2, 2, 2, 3, 3, 4, 5, 6]
back[m-k] (second half vs b[k:], k=0..m): [5, 4, 3, 2, 1, 0, 1, 2, 3]
sum per k:                               [8, 6, 5, 4, 4, 3, 5, 7, 9]
best k: 5 -> b splits into 'satur' and 'day'
row-only alignment: s--unday / saturday | cost 3

300 random pairs: alignments, edit scripts and row-only alignments are optimal; pairs with more than one optimal alignment: 138
n*m = 90000 | row-only cell updates = 179559 | cost matches table: True

What this does to the space optimization

Keeping only one or two rows throws away exactly the cells the walk back needs, so the plain rolling-row version can give you the distance but not the edits. There are three ways out:

1. Keep the whole table. Time O(nm), space O(nm). For two strings of length 2000 that is about four million cells. Storing one small direction code per cell instead of the number is still O(nm) cells, only smaller ones.
2. Divide and conquer (Hirschberg's method). hirschberg_align computes, with rolling rows only, the cost of aligning the first half of a with every prefix of b (front) and the cost of aligning the second half with every suffix (back, computed on the reversed strings). An optimal alignment crosses the middle of a at some column k of b, and the best k minimizes front[k] + back[len(b) - k]. Recurse on the two halves. Time stays O(nm) but is about twice the plain table: on two random strings of length 300 it made 179,559 cell updates against n*m = 90,000, because the first level costs about nm and the work halves at each level below it (1 + 1/2 + 1/4 + ...). The recursion is about log2(n) deep. The split search itself uses two rows of length m + 1 at a time, but this listing is not memory-tight: every call keeps its rows and its copied slices alive while it recurses, so in the worst case it holds up to about m cells for each of about log2(n) levels. The textbook form passes index ranges instead of slices and discards the rows before recursing, which needs only linear space.

A worked split on sunday to saturday (the split search lines in the output): the middle of a cuts it into sun and day. front[k] is the cost of turning sun into the first k characters of saturday, and the second row is the cost of turning day into the remaining characters from k on. Adding the two for every k gives [8, 6, 5, 4, 4, 3, 5, 7, 9], and the smallest sum, 3, is at k = 5. Reading it as a cell: at k = 5, sun against satur costs 3 (insert a and t, substitute n with r) and day against day costs 0, so 3 + 0 = 3, which equals the distance. So some optimal alignment pairs sun with satur and day with day, and each half is then solved on its own with the same method. Hirschberg's method is deeper material than most coding rounds ask for; a typical interview wants the full-table walk back and the observation that rolling rows lose the path.
3. Recompute only when needed. If you need edits for very few pairs, run the cheap length-only version for all of them and reconstruct for the pairs that matter.

Complexity

• Table and walk back: time O(nm) to fill, O(n + m) to walk (every step lowers i or j); space O(nm).
• Row-only alignment: time O(nm) (about 2nm updates); linear space in the textbook form, a little more in the listing for the reason given above.

Edge cases and common mistakes

• If a is empty the alignment is all insertions, and if b is empty it is all deletions; the while i > 0 or j > 0 loop handles both with no special case, since only the left or only the up move is valid there.
• Forgetting to reverse the collected columns, which prints the alignment backwards.
• Applying the edits left to right with original positions, which shifts every later position after an insert or delete. Apply right to left, or track an offset.
• Treating a substitution of equal characters as an edit: only columns where the two characters differ count.
• Assuming the alignment is unique when count_optimal can be greater than 1.

Running the code

Save the listing as edit_alignment.py and run python edit_alignment.py (Python 3.12, standard library only).

The idea

The factorial of n (written n!) is the product 1 x 2 x ... x n, with 0! = 1. It can be defined by itself: n! = n x (n-1)!, with 1 (or 0) as the stopping point. That definition is the recursive version. A loop multiplying 2, 3, ..., n into a running product is the iterative version. Both compute the same number with the same n - 1 multiplications; what differs is how much stack they use. The call stack is the fixed-size region of memory that holds one stack frame (a block with that call's arguments, local variables and return point) for every call that has started but not finished. The recursive version keeps one frame alive per pending multiplication; the loop keeps none.

A third form carries the running product in a parameter called an accumulator: factorial_tail(n, acc) multiplies as it goes down, so nothing is left to do when the inner call returns. The listing below includes it.

The code

import math
import sys


def factorial_recursive(n: int) -> int:
    if n < 0:
        raise ValueError("factorial is undefined for negative numbers")
    if n <= 1:                          # base case: 0! = 1! = 1
        return 1
    return n * factorial_recursive(n - 1)


def factorial_iterative(n: int) -> int:
    if n < 0:
        raise ValueError("factorial is undefined for negative numbers")
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result


def factorial_tail(n: int, acc: int = 1) -> int:
    """Tail-recursive form: the recursive call is the last thing done, and the product rides in acc."""
    if n < 0:
        raise ValueError("factorial is undefined for negative numbers")
    if n <= 1:
        return acc
    return factorial_tail(n - 1, acc * n)


for n in (0, 1, 5, 20):
    assert factorial_recursive(n) == factorial_iterative(n) == factorial_tail(n) == math.factorial(n)
print(factorial_recursive(5), factorial_iterative(5), factorial_tail(5), factorial_recursive(20))

print("recursion limit:", sys.getrecursionlimit())
for fn in (factorial_recursive, factorial_tail, factorial_iterative):
    for n in (900, 1500):
        try:
            fn(n)
            print(f"{fn.__name__}({n}): ok")
        except RecursionError:
            print(f"{fn.__name__}({n}): RecursionError")

Output:

120 120 120 2432902008176640000
recursion limit: 1000
factorial_recursive(900): ok
factorial_recursive(1500): RecursionError
factorial_tail(900): ok
factorial_tail(1500): RecursionError
factorial_iterative(900): ok
factorial_iterative(1500): ok

factorial_tail is the tail-recursive form: it carries the running product in acc, so the recursive call is the very last thing the function does. factorial_recursive is not tail-recursive, because after the inner call returns it still has to multiply by n.

Time and space

max_depth = 0


def factorial_counted(n, depth=1):
    global max_depth
    max_depth = max(max_depth, depth)
    if n <= 1:
        return 1
    return n * factorial_counted(n - 1, depth + 1)


for n in (5, 50, 500):
    max_depth = 0
    value = factorial_counted(n)
    print(f"n={n}: deepest frame count={max_depth}, result has {value.bit_length()} bits")

Output:

n=5: deepest frame count=5, result has 7 bits
n=50: deepest frame count=50, result has 215 bits
n=500: deepest frame count=500, result has 3768 bits

The output shows the call depth equals n (the frames alive at the deepest point) and how big the result gets: a 500! needs 3,768 bits. bit_length() returns how many binary digits a number needs.

The result size in the table has a short reason: n! is at most n^n (n factors, each at most n), and a number of at most n^n needs at most floor(n log2 n) + 1 bits (the + 1 only matters for tiny n: 1! = 1 needs one bit while n log2 n is 0). The bound is loose: by Stirling's approximation n! has about n log2 n - 1.44 n bits (plus a small logarithmic term), so the bound overshoots by an amount that grows in proportion to n, and the ratio of actual bits to n log2 n climbs toward 1 as n grows (0.60, 0.76 and 0.84 for the three values of n in the listing below, which prints both quantities):

import math

for n in (5, 50, 500):
    bits = math.factorial(n).bit_length()
    print(f"n={n}: {n}! has {bits} bits; n * log2(n) = {n * math.log2(n):.0f}")

Output:

n=5: 5! has 7 bits; n * log2(n) = 12
n=50: 50! has 215 bits; n * log2(n) = 282
n=500: 500! has 3768 bits; n * log2(n) = 4483

Python integers are arbitrary precision (they grow as large as memory allows instead of overflowing at 64 bits), so a multiplication is not constant time once the product is large: each step multiplies a big number by a small one, which costs time proportional to the number's length. Counting multiplications, which is the usual interview answer, both versions are O(n), and both must hold the same result of O(n log n) bits. The recursive version also holds n stack frames at once, and CPython allows 1000 by default, which is why factorial_recursive(1500) raises RecursionError while factorial_iterative(1500) returns.

Would tail-call optimization change the space?

Tail-call optimization (TCO) means that when a function's last action is a call, the runtime reuses the current stack frame instead of adding another, so the recursion runs in constant stack space. For factorial_tail that would change the space from O(n) to O(1); for factorial_recursive it would not, because the multiplication happens after the call returns, so the frame cannot be dropped. To benefit, you must first rewrite to the accumulator form, as factorial_tail does.

Why Python does not do it

CPython never reuses the frame for a tail call: factorial_tail(1500) raises RecursionError in the output just like the plain version. Python's creator explained the decision in a 2009 blog post: eliminating tail calls removes frames from tracebacks (the list of active calls Python prints when an error is raised), which makes debugging harder; he also objected that code written to rely on it would break on implementations without it, and that rebinding names at run time makes it impossible to know at compile time that a call is a self-call. His recommended alternative is to write the loop. Raising the limit with sys.setrecursionlimit only moves the wall, and a very high limit can crash the interpreter, so a loop (or math.factorial) is the real answer for large n. Scheme (a Lisp-family language) requires TCO by specification; compilers for C-family languages may do it as an optimisation but are not required to.

Edge cases and common mistakes

• n = 0 and n = 1 both return 1; a base case of only n == 0 works but makes one more call.
• Negative input has no factorial. The code raises ValueError, because the n <= 1 base case would otherwise quietly return 1.
• A base case of n == 1 alone, without the negative-input check, makes factorial(0) recurse through -1, -2, ... until RecursionError; with the check in the listing it raises ValueError at -1 instead.
• Believing the accumulator form is automatically O(1) in Python: it is not.
• Floats: factorial_recursive(5.0) and factorial_tail(5.0) return 120.0 by accident, while factorial_iterative(5.0) raises TypeError because range needs integers. Reject non-integers up front so all versions behave the same.

Follow-ups

• Compute n! mod m for huge n: reduce after each multiplication so numbers stay small.
• Memoise factorials for many queries: one table of prefix products answers each query in O(1).
• Recursion to iteration in general: the explicit stack, or the trampoline pattern (a loop that repeatedly calls a function that returns the next function to call, instead of letting each call nest).

Running the code

Python 3.12, standard library only.
python3 factorial.py ; python3 factorial_depth.py ; python3 factorial_bits.py   (the three listings)

Direct answer

Sort the array, then fix each element in turn as the "anchor" and use a two-pointer scan over the remaining sorted suffix to find pairs that complete the triplet to zero, skipping over duplicate values at every level to avoid duplicate triplets. This runs in O(n^2) time (O(n log n) sort plus an O(n) two-pointer scan for each of n anchors) and O(1) extra space beyond the output and the sort itself. The same anchor-then-two-pointer idea generalizes to k-sum by recursing: fix one more element per level until only two remain, then solve that base case with two pointers.

Algorithm: 3Sum

1. Sort nums.
2. For each index i (the anchor), skip it if it's a duplicate of the previous anchor (nums[i] == nums[i-1]), which prevents emitting the same triplet-starting-value twice.
3. If nums[i] > 0, stop entirely: since the array is sorted, every remaining element is also non-negative, so no triplet starting here or later can sum to zero (unless all are zero, already handled by the anchor being the smallest of the three).
4. Two-pointer scan left = i+1, right = n-1 over the sorted suffix: if the three-element sum is 0, record it and advance both pointers past any duplicate values; if the sum is negative, advance left (need a larger value); if positive, retreat right (need a smaller value).

def three_sum(nums):
    nums = sorted(nums)
    n = len(nums)
    result = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        if nums[i] > 0:
            break
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Generalizing to k-sum

The pattern is: fix one element, reduce the target by its value, and recurse on k-1 with the remaining sorted suffix, until k == 2, at which point solve with the same two-pointer scan used above (which is really just 3Sum with the anchor already fixed by the outer recursion). Each recursive level still needs the duplicate-skip at its own position to avoid duplicate combinations, and a similar early-exit prune (if the smallest possible sum of the remaining k elements already exceeds the target, or the largest possible sum is already below it, stop).

def k_sum(nums, target, k):
    nums = sorted(nums)

    def helper(start, k, target):
        n = len(nums)
        if k == 2:
            res = []
            left, right = start, n - 1
            while left < right:
                total = nums[left] + nums[right]
                if total == target:
                    res.append([nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left - 1]:
                        left += 1
                    while left < right and nums[right] == nums[right + 1]:
                        right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
            return res

        res = []
        for i in range(start, n - k + 1):
            if i > start and nums[i] == nums[i - 1]:
                continue
            for sub in helper(i + 1, k - 1, target - nums[i]):
                res.append([nums[i]] + sub)
        return res

    return helper(0, k, target)

This runs in O(n^(k-1)) time: each of the k-2 outer recursive levels contributes a factor of O(n), and the base case two-pointer scan is O(n), for a total of O(n^(k-1)). 3Sum is exactly this generalization with k=3.

Worked example

import itertools

def brute_force_k_sum(nums, target, k):
    nums_sorted = sorted(nums)
    seen = set()
    result = []
    for combo_idx in itertools.combinations(range(len(nums_sorted)), k):
        combo_vals = tuple(nums_sorted[i] for i in combo_idx)
        if sum(combo_vals) == target and combo_vals not in seen:
            seen.add(combo_vals)
            result.append(list(combo_vals))
    return sorted(result)

print(three_sum([-1, 0, 1, 2, -1, -4]))
k_sum_result = k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print(k_sum_result)

brute = brute_force_k_sum([1, 0, -1, 0, -2, 2], target=0, k=4)
print("brute-force cross-check:", brute)
print("agree:", sorted(k_sum_result) == brute)

Output (verified by execution, and k_sum's results were independently cross-checked against a brute-force itertools.combinations scan over every k-subset of indices, so agreement is real validation, not the same logic checked twice):

[[-1, -1, 2], [-1, 0, 1]]
[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
brute-force cross-check: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
agree: True

Tracing why [-1, -1, 2] and [-1, 0, 1] are the only two triplets on the sorted input [-4, -1, -1, 0, 1, 2]: anchor -4 (index 0) needs a pair summing to 4 from [-1,-1,0,1,2], and the two-pointer scan finds none (max reachable pair sum here is -1+2=1, which the pointers converge past without hitting 4). Anchor -1 (index 1) needs a pair summing to 1 from [-1,0,1,2]: the scan finds -1 and 2 first (giving [-1,-1,2]), then continues and finds 0 and 1 (giving [-1,0,1]). The next anchor is also -1 (index 2), but it's skipped as a duplicate of index 1's value, which is exactly what prevents [-1,-1,2] (or a duplicate [-1,0,1]) from being emitted twice.

Trade-offs and pitfalls

• The two duplicate-skip lines are the single most error-prone part of this problem. Skipping the anchor's duplicates prevents duplicate triplet-starts; skipping left/right duplicates after recording a match prevents duplicate triplet-ends. Missing either one produces a correct set of values but with duplicate entries in the output.
• The nums[i] > 0: break early exit is an optimization, not a correctness requirement for 3Sum specifically (target 0): once sorted, a non-negative anchor means the two-pointer scan can never reach a negative-enough sum to cancel it out to zero. For a general k-sum with a nonzero target, this prune needs to be a real bounds check (is the target reachable at all given the remaining sorted suffix's min/max possible sums), not just a sign check.
• k-sum's O(n^(k-1)) complexity grows fast: 4Sum is already O(n^3), and this approach stops being practical well before k gets large; for genuinely large k, a hash-map-based approach (precompute all pair sums for k/2 elements when k is even) trades space for a lower time exponent, at the cost of needing to dedupe combinations across the two halves.
• Common wrong turn: using a hash set of frozenset or sorted tuples to dedupe triplets after generating all of them (including duplicates) via brute force. This works but is O(n^3) or worse and defeats the purpose of the sorted two-pointer approach, which prevents duplicates from being generated in the first place rather than filtering them out afterward.

count++ is not one atomic operation: it is read-count, add-one, write-count, and with 100 threads calling increment() concurrently, two threads can both read the same value before either writes back, so one increment is silently lost.

Verified demonstration

Running a deterministic interleaving (thread A reads 0, sleeps, then writes 1; thread B reads 0 before A writes, then writes 1) confirms the lost update directly: two increments were issued, but the final count is 1, not 2, because B's read happened before A's write landed, so A's write overwrote B's already-lost update.

Two correct fixes

1. Synchronize the read-modify-write:

public synchronized void increment() { count++; }
public synchronized int get() { return count; }

Simple and correct; adds lock contention under very high thread counts.
2. Use AtomicInteger:

private final AtomicInteger count = new AtomicInteger(0);
public void increment() { count.incrementAndGet(); }
public int get() { return count.get(); }

Uses a lock-free CPU-level compare-and-swap; typically faster than a full lock under contention because it never blocks a thread, it just retries the CAS.

Trade-offs

synchronized is simpler to reason about for compound operations (e.g., updating two related fields together atomically); AtomicInteger is faster for a single counter specifically but doesn't generalize to multi-field invariants without a more complex lock-free design. For a plain counter under high contention, AtomicInteger (or LongAdder for extremely high contention) is the standard choice.

An aggregator sitting in front of several third-party services needs its own STABLE error vocabulary, translated from whatever each third party actually returns, so that a change to a partner's internal error format never leaks through as a breaking change to the aggregator's own consumers.

Categorizing transient versus permanent errors

Transient (the caller should retry, possibly after a delay): a third-party timeout, a rate limit from the partner, a temporary partner outage. Permanent (retrying will never help without a code change or user action): the partner rejected the request as fundamentally invalid, an authentication failure with the partner's credentials, a resource that genuinely does not exist. This classification, not the raw partner error, is what the aggregator's OWN error contract should expose, because a consumer of the aggregator should not need to know which specific third party was involved to decide whether retrying makes sense.

Masking internal and third-party-sensitive detail

The aggregator's public error response should never leak a partner's internal error codes, stack traces, or account-specific detail verbatim; those get logged internally (tied to the correlation ID) for debugging, while the public-facing error exposes only the aggregator's own stable vocabulary (upstream_timeout, upstream_rejected, and so on) plus a correlation ID a consumer can hand back for support escalation.

Propagating a correlation ID for debugging

A single correlation ID, generated when the aggregator receives the original request, should be threaded through every downstream call to every third party and included in every log line on both sides of the boundary. When something goes wrong three services deep, that one ID is what lets an engineer reconstruct the whole call chain instead of correlating timestamps across three different systems' logs by hand.

Worked example

The aggregator calls a shipping-rate partner whose gateway times out during a transient outage, returning a partner-specific error like ERR_GATEWAY_TIMEOUT with an internal partner request ID in the body. The aggregator's response to ITS OWN consumer never repeats that partner error verbatim; instead it returns:

{
  "error": {
    "code": "upstream_unavailable",
    "category": "transient",
    "message": "A shipping provider is temporarily unavailable. Please retry.",
    "correlation_id": "req_a91f2b3c"
  }
}

Internally, the aggregator's logs (searchable by req_a91f2b3c) retain the full partner error detail (including the raw ERR_GATEWAY_TIMEOUT code and the partner's own internal request ID) for an engineer investigating the incident, while the consumer only ever sees the stable, categorized, non-sensitive shape. Contrast this with a DIFFERENT partner error, ERR_CARRIER_ACCT_SUSPENDED (the aggregator's own account with that carrier has been suspended over a billing dispute): even though it also arrives from a third party, it belongs in the PERMANENT bucket, not transient, because no amount of client-side retrying resolves a suspended account. That failure should map to a distinct code (upstream_rejected) with "category": "permanent" and a message that does not invite a retry, since telling a client to retry a failure that only a human resolving a billing dispute can fix wastes capacity on both sides and delays anyone noticing the real, unretryable problem.

Trade-offs and pitfalls

Masking too aggressively can leave consumers unable to distinguish genuinely different failure modes that they need to handle differently (treating every upstream failure as one generic "something went wrong" code removes the transient-versus-permanent signal that makes the categorization useful in the first place). The opposite failure, passing partner error detail through unmodified "to be helpful," ties the aggregator's own contract to every partner's internal error format, so a partner changing their error codes becomes a breaking change for the aggregator's consumers even though nothing about the aggregator's own contract changed on purpose.

Direct answer. Choose module/package boundaries around cohesive RESPONSIBILITIES (what the code is FOR), not around technical layer alone (all 'models' together, all 'utils' together) -- so a reader can find everything related to one feature/concept without hunting across the whole tree, and a 'utils' dumping ground never gets a chance to form.

A workable layout for a medium-sized app

src/
  users/          # everything about the 'users' concept
    models.py
    repository.py
    validation.py
    service.py
  orders/         # everything about the 'orders' concept
    models.py
    repository.py
    service.py
  shared/         # genuinely cross-cutting, used by 2+ feature modules
    http.py
    logging.py

A feature-oriented layout (users/, orders/) groups everything related to ONE concept together, so a change to how orders work touches files in ONE directory, and a new engineer exploring 'how does order processing work' finds everything in one place rather than jumping between a top-level models/, services/, and repositories/ folder hunting for the order-specific pieces scattered across each.

Choosing names and avoiding the 'utils' trap

• Name modules after the DOMAIN CONCEPT they own (users, billing, notifications), not after a technical pattern (helpers, common, misc) -- a domain name tells a reader WHAT lives there; a technical/generic name invites anything unrelated to be dropped in because it 'kind of fits.'
• When you're tempted to put something in utils, ask what CONCEPT it actually belongs to -- a date-formatting helper used only by the orders module belongs IN the orders module; a date-formatting helper used by three unrelated modules might genuinely warrant a small, precisely-named shared module (date_formatting, not utils).

Common failure modes as the codebase grows

• Circular imports: two feature modules that both need something from each other usually indicates a THIRD, shared concept hasn't been extracted yet -- pull the genuinely shared piece into its own module that both can depend on, rather than letting them depend on each other directly.
• Unclear ownership: as team size grows, ambiguous module boundaries (who owns shared/?) become a real coordination problem -- pairing module structure with clear ownership (even informally) prevents a shared module from becoming everyone's problem and no one's responsibility.

Trade-offs and pitfalls

• Feature-oriented layout can feel like more upfront ceremony for a genuinely small app where a flat structure is perfectly readable -- the benefit compounds as the app and team grow, so don't over-structure a small, stable prototype preemptively.
• A shared/ module can silently become the new utils/ dumping ground if nobody enforces the bar ('genuinely used by 2+ modules, not just convenient to put here') -- periodic review of what's landed in shared/ catches this drift before it compounds.

Direct answer: Classical matrix multiplication is $O(n^3)$, requiring $n^3$ scalar multiplications for two $n \times n$ matrices; Strassen's algorithm reduces this to $O(n^{\log_2 7}) \approx O(n^{2.807})$ by recursively dividing each matrix into four $n/2 \times n/2$ quadrants and combining them using only 7 quadrant multiplications (instead of the naive 8), at the cost of extra additions/subtractions - a genuine asymptotic improvement, but with a large constant factor and worse numerical stability that mean it's rarely used naively in production numerical libraries.

Structured elaboration

• Core idea: partition each $n \times n$ matrix into four $(n/2) \times (n/2)$ blocks. Naive block multiplication would need $2^3=8$ block-multiplications (each of the 4 output blocks needs 2 products summed). Strassen's insight is a clever algebraic identity that computes the same result using only 7 block-multiplications (combined with a larger number of additions/subtractions), by computing 7 specific linear combinations of the input blocks, multiplying those, and then combining the 7 products via more additions to recover the 4 output blocks.
• Recurrence: applying this recursively gives $T(n) = 7T(n/2) + O(n^2)$ (7 recursive multiplications of half-size matrices, plus $O(n^2)$ work for the additions/subtractions at each level). By the Master Theorem (Case 1, since $n^{\log_2 7} \approx n^{2.807}$ dominates the $O(n^2)$ additive term), this resolves to $T(n) = \Theta(n^{\log_2 7})$.
• Why $\log_2 7$: at each level of recursion, the problem size halves (dividing $n$ by 2 in each dimension) while the number of subproblems is 7 (not 8) - the recurrence $T(n) = 7T(n/2)$ alone (ignoring the additive term) gives exactly $n^{\log_2 7}$ by the same reasoning as any divide-and-conquer recurrence with $a$ subproblems of size $n/b$.

Worked example

For $n=1024$: naive is $1024^3 \approx 1.07 \times 10^9$ scalar multiplications; Strassen's is $1024^{\log_2 7} = 1024^{2.807} \approx 2.82 \times 10^8$ - roughly 3.8x fewer multiplications asymptotically at this size, a gap that widens further (favoring Strassen) as $n$ grows larger, since the exponents differ (3 versus 2.807). But Strassen's algorithm's PRACTICAL constant factor (from the extra additions and the recursive overhead/memory allocation at each level) means the crossover point where it actually beats a well-optimized naive (or blocked) implementation in WALL-CLOCK time is typically in the hundreds-to-low-thousands range for $n$, and even past that crossover, production numerical libraries (BLAS implementations) rarely use naive Strassen because of two additional real costs: extra memory for the intermediate combination matrices at each recursion level, and materially worse numerical stability (Strassen's algebraic recombination can amplify floating-point rounding error more than the straightforward triple-loop computation, a real concern for ill-conditioned matrices).

Trade-offs & pitfalls

• "Better asymptotic complexity" and "actually faster in practice" are NOT the same claim - Strassen is the textbook example of an asymptotically superior algorithm that's rarely used naively in production for exactly this reason, alongside its numerical-stability cost.
• Numerical stability matters concretely: Strassen's recombination can amplify relative error by a larger factor than naive multiplication for matrices with certain structure (e.g. large dynamic range in values), a real correctness concern for scientific/numerical applications beyond just "it's slower than expected."
• Even faster matrix-multiplication algorithms exist theoretically (the current best known is below $O(n^{2.373})$, via more elaborate algebraic constructions), but these have even LARGER constant factors and are essentially never used in practice - purely of theoretical/complexity-theoretic interest, worth knowing exists as the frontier but not as a practical recommendation.