Google Senior Backend Developer Interview Preparation Guide

Direct answer

Test an event-driven microservice at three levels: unit tests that mock the producer/consumer boundary entirely so business logic is verified in isolation, integration tests that run against a real embedded or local broker so the actual serialization, publish, and consume path is exercised end to end, and both layers use deterministic, explicitly seeded event fixtures so a failing test points at a real bug rather than a flaky, timing-dependent race. Retry and error-handling behavior specifically needs its own test scenarios, not just happy-path coverage, since that is exactly the logic that is hardest to get right and easiest to leave untested.

Structured elaboration

Mocking producers and consumers for unit tests. At the unit level, replace the actual broker client with a fake/mock that records what was published and lets the test inject arbitrary incoming events directly into the handler function, bypassing the network and serialization entirely. This isolates the test to the service's own business logic: given this event payload, does the handler produce the correct follow-on event(s) and the correct side effects, without needing a running broker at all. Keep these tests fast (milliseconds, no I/O) so they run on every commit.

Embedded or local brokers for integration tests. Unit tests alone miss real failure modes: serialization/deserialization bugs, schema mismatches, or broker-client configuration errors. Integration tests should run against a real broker, using either an embedded in-process broker (a lightweight broker implementation that starts and stops within the test process) or a local broker instance managed by the test runner (started fresh per test run, typically via a container the CI pipeline spins up and tears down). This validates the actual wire format and the actual client library configuration, not just the business logic mocked out from it, catching a class of bug unit tests structurally cannot see.

Deterministic seeding of events. Both layers depend on test fixtures being deterministic: a fixed, version-controlled set of input events with known ids, payloads, and (where ordering matters) a known arrival order, rather than randomly generated data on each run. Deterministic seeding means a failing test reproduces identically every time, which is essential for debugging, and it lets assertions check exact expected output rather than a fuzzy "something happened" check. Where randomness is genuinely useful (for fuzz-style coverage), still pin an explicit random seed so a failure is reproducible from the seed value alone.

Validating retry and error-handling behavior in CI. This needs dedicated test scenarios, not incidental coverage from happy-path tests: a handler that throws on a specific input should be asserted to trigger the configured retry policy (correct backoff behavior, correct retry count before giving up); a handler that keeps failing past the retry budget should be asserted to route the message to wherever poison messages go (commonly a dead-letter queue, DLQ) rather than being silently dropped or retried forever; and a handler that successfully processes a message but crashes before acknowledging it should be tested for what happens on redelivery (this is where consumer-side idempotency gets validated: does reprocessing the same event twice produce the same end state, not a duplicated side effect).

Worked example

A unit test for an order-processing handler: inject a fake order-created event with a fixed id (order-created-test-001) directly into the handler, using a mock producer that just records calls. Assert the handler calls the mock producer exactly once with a payment-attempted event whose order_id matches the input and whose trace_id was propagated from the input event, no real broker involved. An integration test for the same service: start an embedded broker in the test's setup step, publish the same fixed order-created-test-001 event to the real input topic using the real client library, then poll the real output topic (with a bounded timeout, not an unbounded wait) and assert the payment-attempted event actually arrives with the expected fields, this time exercising real serialization and the real broker client configuration. A retry-behavior test: configure the handler's downstream call to always throw for a specific test event id, publish that event, and assert the retry count and backoff delays recorded match the configured policy, then assert the event lands in the DLQ topic after the configured retry budget is exhausted, not before and not never.

Trade-offs and pitfalls

Unit tests that mock too much (for example, mocking the handler's own internal logic instead of just the broker boundary) stop testing anything meaningful; the mock boundary should be the I/O edge (the broker client), not the business logic itself. Integration tests against a shared, always-on broker environment (rather than a fresh embedded/local instance per run) are a common source of flaky tests, since leftover state or concurrent test runs from other branches can pollute topics; prefer an ephemeral broker per test run. Skipping explicit retry/error-handling tests is the most common gap in practice, because it requires deliberately engineering a failure, which is more work to write than a happy-path test, and it's exactly the code path most likely to have a subtle bug (an off-by-one retry count, a DLQ route that's never actually exercised until a real incident). Finally, non-deterministic event ordering in a multi-partition integration test can make assertions flaky if the test assumes a specific arrival order that the broker doesn't actually guarantee across partitions; only assert on ordering the system is actually supposed to guarantee.

Situation: A senior stakeholder wanted to launch in two weeks, while Operations warned that the support team was not ready.

Task: I needed to reset expectations without slowing the business unnecessarily.

Action: I made the trade-off visible in a simple readiness review. I listed the risks, the likely customer impact, and the mitigation options. I also translated the concern into business language, not just process language. For example, instead of saying Operations was not ready, I showed that we would have limited training coverage and slower incident response if we launched immediately. Then I proposed two paths: launch with a phased rollout and extra monitoring, or delay one week to complete training and testing.

Result: Both sides could support the phased rollout because the risk was named clearly and the plan had guardrails. The stakeholder got speed, Operations got protection, and we agreed on a decision that balanced business urgency with operational readiness.

That experience reinforced that good trade-off decisions are rarely about winning an argument. They are about making the risk and impact clear enough for everyone to support the choice.

Direct answer

Before committing to a plan, spend the first days mapping every team your work actually depends on, get an explicit, dated commitment from each one on what they will deliver, and track those commitments in one visible place so a slip surfaces the moment it happens instead of at the deadline.

Structured elaboration

Map the dependency graph early, not incidentally

Run a short cross-functional session at kickoff specifically to list what you need from other teams: what, by when, and in what form. Treat this as a deliverable of the kickoff, not a side conversation that happens if someone remembers to ask.

Get commitments, not assumptions

"They know we need this" is not a commitment. A commitment has an owner, a date, and an explicit acceptance criterion, meaning what "done" looks like from your side, not just theirs. Ambiguous handoffs are where dependencies quietly slip.

Make status visible continuously, not just at standups

A shared dependency tracker, checked weekly at minimum, with a clear ready, at risk, or blocked status per item, turns a hidden slip into a visible one while there is still time to react.

If you are joining an initiative already in motion

The mapping happens differently. Your first days are spent finding out who currently owns each piece, which may not match the org chart or what the original plan assumed, and estimating the time-to-impact for each dependency, meaning how long before a slip there would actually hit your own critical path (the specific chain of dependent tasks whose delay would directly delay your own delivery date, unlike a dependency that has slack to spare), before you commit to a timeline of your own. Committing to a date before doing this is committing to someone else's assumptions.

Worked example

A project depends on three other teams: one providing a new data feed, one exposing an API endpoint, and one delivering a design system component. At kickoff, the team runs a short dependency-mapping session and gets each provider to commit to a specific date and a specific definition of ready, for the API that means a documented contract and a staging environment, not just "the code exists." These commitments go into a shared tracker with a status column, reviewed weekly.

In week two, the API team's status moves to at risk because their own upstream dependency slipped. Because the tracker surfaced this immediately rather than at the original deadline, there is still time to either help unblock the API team or replan the timeline around a slower path, instead of discovering the problem in the final week when no good options remain.

For the joining-in-progress case: an engineer joins a multi-team initiative already underway. In the first few days, instead of accepting the existing plan at face value, they interview each team named in the plan to confirm who currently owns each dependency, since ownership has quietly shifted since the plan was written, and estimate the time-to-impact of each one: the API dependency would only hurt the timeline if it slipped more than two weeks, while the data-feed dependency has almost no buffer at all. Only after that mapping do they commit to a delivery date of their own, rather than inheriting the original plan's assumptions unchecked.

Trade-offs and pitfalls

A heavy dependency-tracking process on a small, low-risk project wastes more time than it saves; scale the rigor to the size and risk of the dependency rather than applying it uniformly everywhere.

The most common failure is treating the mapping as a one-time kickoff exercise instead of a living tracker. A dependency list that is accurate on day one and never updated again is exactly as useless as never having made one, because the whole point is catching drift as it happens.

Direct answer

Use histograms, not summaries, when p95/p99 needs to be aggregated across many instances, because histogram buckets are additive cumulative counters you can sum across instances before computing a quantile, while a summary's quantile is already computed per-instance and cannot be correctly averaged into a fleet-wide percentile.

Why this is true

Why summaries don't aggregate

A summary computes its quantile locally from that instance's own observations. Averaging five instances' p99s is not the fleet's p99: an instance handling a small, unlucky slice of high-latency traffic gets diluted by four instances with normal traffic, hiding exactly the tail behavior the query was meant to surface.

Why histograms do aggregate

A histogram exposes cumulative bucket counts, how many observations were at or below each boundary. Bucket counts are just counts, so you can sum them across instances first, then compute the quantile once from the merged distribution:

then interpolate the quantile from the merged $B^{fleet}$. This is mergeable because summation is associative; a pre-computed quantile is not.

The PromQL shape (illustrative, not the point of the question):

histogram_quantile(0.99, sum by (le, job) (rate(http_request_duration_seconds_bucket[5m])))

Pitfalls specific to aggregating this way

• All instances must share identical bucket boundaries, or sum by (le) is adding counts from buckets that don't actually represent the same ranges.
• Accuracy is bounded by bucket granularity (see the bucket-design question): a coarse tail bucket makes the interpolated p99 a rough estimate, not an exact value.
• At low sample counts, a low-traffic service or a short rate() window, the interpolated quantile can be noisy or misleading. Widen the window or require a minimum sample count before alerting on it.

When per-instance precision genuinely matters more

Summaries still have a place: debugging one specific instance's actual latency distribution, or client environments where a full histogram implementation isn't available. Just don't build fleet-wide SLO dashboards on top of them.

Alternatives when storing every observation isn't affordable

When a fixed-bucket histogram isn't precise enough, or the quantile is being computed outside the metrics pipeline entirely, for example inside application code or a tracing system, two streaming estimators are the common choices:

• Reservoir sampling: keep a fixed-size random sample of everything seen and compute the quantile from the sample at read time. Simple and unbiased, but tail accuracy (p99) degrades because a small sample only has a handful of items above the p99 threshold.
• t-digest or HDR histogram: adaptive structures that allocate more resolution near the tails (t-digest) or guarantee a fixed relative error across the whole range (HDR histogram), and both are mergeable across instances the way a Prometheus histogram is, unlike a plain reservoir sample, which isn't trivially mergeable without keeping the full underlying sample from every instance.
• The trade-off between the two: reservoir sampling is simpler with no accuracy bias but has higher tail variance for a fixed memory budget. t-digest and HDR trade a bit of implementation complexity for much better tail accuracy at the same memory footprint, which is why they're the more common choice in tracing systems where the tail is usually the point of interest.

Worked example

Quantify the reservoir-sampling tail-noise problem concretely. With a reservoir size $k=1000$ computing p99:

With only about 10 samples informing the estimate above the 99th percentile, the standard error of that estimate is large relative to the value itself, a handful of samples is a small basis for estimating a tail. That's exactly why reservoir sampling is fine for a median but noisy for p99, and why t-digest's tail-biased resolution, allocating proportionally more centroids near the extremes, exists specifically to fix this.

Trade-offs and pitfalls

• Reaching for a summary because the client library makes it one line of code, without realizing it breaks fleet-wide aggregation once the service scales past one instance, is the single most common version of this mistake.
• Mixing bucket boundaries across a service's versions, for example after a library upgrade changes the defaults, silently breaks historical quantile continuity even though nothing errors.
• Reservoir sampling's simplicity is attractive for a quick implementation, but if the actual goal is tail latency, which it almost always is for an SLO, the sample size needed for a stable p99 estimate is much larger than what feels sufficient for a median. Budget memory accordingly or use t-digest instead.

I would move production to a remote backend that supports both shared access and state locking. State is Terraform’s record of what it created, and locking means only one writer can change that record at a time.

Design choices

• Use one backend per environment, so prod does not share state with dev
• Turn on encryption at rest for the backend storage
• Restrict write access to CI and a small break-glass admin group
• Give most engineers read-only access to plans and state history
• Require an exclusive lock for apply, with a short timeout and clear failure message

Recovery
I would also enable versioning or history so I can recover a prior state file if an apply fails halfway through. If a run breaks, I would not edit state first. I would inspect the lock, compare the current cloud resources with terraform plan -refresh-only, and then decide whether to fix drift, import an orphan, or roll back.

Example
If a colleague applies from their workstation while CI is planning, the lock should stop the second write. That prevents two people from corrupting the same prod state.

Direct answer

A binary search tree (BST), a tree where every node's left subtree holds smaller keys and its right subtree holds larger keys, supports search, insert, and delete by walking down from the root using key comparisons, giving O(log n) operations only when the tree stays roughly balanced. Deleting a node has three cases depending on how many children it has: a leaf (0 children) is simply removed, a node with exactly 1 child is replaced by that child, and a node with 2 children is replaced by its in-order successor's key (the smallest key in its right subtree), after which that successor is deleted from its original position, where it is now guaranteed to have at most one child.

Structured elaboration

Approach: BST search, insert, delete

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


def bst_search(root, key):
    node = root
    while node is not None:
        if key == node.key:
            return node
        node = node.left if key < node.key else node.right
    return None


def bst_insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = bst_insert(root.left, key)
    elif key > root.key:
        root.right = bst_insert(root.right, key)
    return root


def _min_node(root):
    node = root
    while node.left is not None:
        node = node.left
    return node


def bst_delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = bst_delete(root.left, key)
    elif key > root.key:
        root.right = bst_delete(root.right, key)
    else:
        if root.left is None and root.right is None:
            return None                       # 0-child case
        if root.left is None:
            return root.right                 # 1-child case (right only)
        if root.right is None:
            return root.left                  # 1-child case (left only)
        # 2-child case: replace key with in-order successor, then delete it
        successor = _min_node(root.right)
        root.key = successor.key
        root.right = bst_delete(root.right, successor.key)
    return root

Approach: why a plain BST can degrade, and what AVL does differently

• A plain BST's height depends entirely on insertion order: inserting already-sorted keys (or reverse-sorted keys) builds a tree that is really a linked list in disguise, one child per node, giving O(n) search, insert, and delete instead of O(log n).
• An AVL tree (a self-balancing BST named for its inventors, Adelson-Velsky and Landis) prevents this by tracking a height at every node and, after every insert, walking back up and checking a balance factor (the height of the right subtree minus the height of the left subtree) at each ancestor. If the balance factor ever reaches +-2, a rotation restructures that subtree back to +-1; this happens on the way back up from the newly inserted node, so no ancestor is ever left unbalanced for more than the single insert that caused it.
• The specific rotation applied depends on where the imbalance shows up: a single rotation fixes a "straight-line" imbalance (left-left or right-right), and a double rotation (rotating the child first, then the node itself) fixes a "zig-zag" imbalance (left-right or right-left).
• A red-black tree solves the same degradation problem with a different, looser invariant, a coloring rule rather than a strict height-balance rule, trading a slightly taller worst-case tree for fewer rotations per insert.

def _h(node):
    return node.height if node else 0


def _update_height(node):
    node.height = 1 + max(_h(node.left), _h(node.right))


def _balance_factor(node):
    return _h(node.right) - _h(node.left)


def _rotate_left(x):
    y = x.right
    x.right = y.left
    y.left = x
    _update_height(x)
    _update_height(y)
    return y


def _rotate_right(y):
    x = y.left
    y.left = x.right
    x.right = y
    _update_height(y)
    _update_height(x)
    return x


def avl_insert(root, key):
    if root is None:
        node = Node(key)
        node.height = 1
        return node
    if key < root.key:
        root.left = avl_insert(root.left, key)
    elif key > root.key:
        root.right = avl_insert(root.right, key)
    else:
        return root

    _update_height(root)
    bf = _balance_factor(root)

    if bf > 1:  # right-heavy
        if _balance_factor(root.right) < 0:
            root.right = _rotate_right(root.right)  # RL case
        return _rotate_left(root)
    if bf < -1:  # left-heavy
        if _balance_factor(root.left) > 0:
            root.left = _rotate_left(root.left)      # LR case
        return _rotate_right(root)
    return root

Key points

• Search, insert, and delete on a BST are all O(height), so the entire performance story of a BST reduces to controlling its height.
• The delete case that needs the most care is the 2-child case: the node cannot simply be removed, a replacement key must be found that preserves the ordering invariant, and the in-order successor (or equivalently, the in-order predecessor) is the only choice that doesn't require restructuring more than one path.
• AVL's rebalancing only ever looks at the path from the inserted node back to the root, keeping a single insert's rebalancing cost proportional to the tree's height, not its size.

Worked example

Building a BST from [5, 3, 8, 2, 4, 7, 9] via repeated bst_insert, an in-order traversal prints [2, 3, 4, 5, 7, 8, 9], confirming the BST property. Deleting 2 (a leaf, the 0-child case) leaves [3, 4, 5, 7, 8, 9]. Deleting 3 next (now a 1-child case, since 3's only remaining child is 4) leaves [4, 5, 7, 8, 9]. Deleting 5, the root (a 2-child case), replaces its key with its in-order successor, 7, then removes the original 7 from the right subtree, leaving [4, 7, 8, 9].

To see the degradation: inserting [1, 2, 3, 4, 5, 6, 7] in sorted order into a plain BST via bst_insert produces a tree of height 7 (a straight chain, one child per node, for n = 7 nodes, the O(n) worst case). Running the same 7 keys through avl_insert instead produces a tree of height 3, and an in-order traversal still prints [1, 2, 3, 4, 5, 6, 7], confirming the rebalancing preserved the BST property while keeping the tree flat.

Trade-offs & pitfalls

Complexity

Plain BST: search, insert, and delete are all $O(h)$, where $h$ is the tree's height; $h$ ranges from $O(\log n)$ (balanced) to $O(n)$ (degenerate, such as sorted-order insertion).
AVL: search, insert, and delete are all $O(\log n)$ worst case, since the height-balance invariant guarantees $h = O(\log n)$ regardless of insertion order; each insert does $O(\log n)$ work walking back up, plus at most a constant number of rotations.
Space: $O(n)$ for the tree itself; $O(h)$ additional stack space for the recursive implementations shown here.

Edge cases

• Deleting a node with 2 children whose in-order successor is itself a leaf: the recursive bst_delete call on the successor correctly falls into the 0-child case.
• Deleting the root: handled the same as any other node, since the function returns the (possibly new) subtree root at every level.
• Inserting a duplicate key: the implementation shown ignores duplicates; a production version needs to decide up front whether duplicates are allowed and where they go if so.
• Empty tree: search and delete both return None safely; insert on an empty tree creates the first node.

A common bug in from-scratch delete implementations is fixing up the tree's shape but forgetting to also update any augmented metadata (heights, subtree sizes, color bits) on every node along the path back to the root; for AVL specifically, forgetting to update height before computing the balance factor at a node makes every rebalancing decision above it wrong. A second pitfall is choosing the in-order predecessor instead of the in-order successor for the 2-child case inconsistently across an implementation; either works, but mixing them without matching invariant logic can subtly break ordering.

Direct answer. HATEOAS (Hypermedia As The Engine Of Application State) means a response includes links describing what the client can legitimately do next from this resource's current state, so the client does not need to hard-code which endpoints exist or which transitions are valid; it follows links the server hands it.

Worked example. For an order in the "pending" state:

{
  "id": "ord_123",
  "status": "pending",
  "total": 4200,
  "_links": {
    "self": { "href": "/orders/ord_123" },
    "items": { "href": "/orders/ord_123/items", "method": "GET" },
    "pay":  { "href": "/orders/ord_123/pay", "method": "POST" },
    "cancel": { "href": "/orders/ord_123/cancel", "method": "POST" }
  }
}

The items link is a plain GET that stays present regardless of the order's state, since viewing the line items is never a state-dependent action, unlike pay and cancel, which only appear while the order is actually in a state where they are legal.

Once the order is paid, the server's next response for that same order would include a "ship" link and drop "pay" and "cancel" entirely. The client does not need business logic hard-coded like show a pay button only when status is pending; it just renders whatever links are present.

What this actually buys you. The client-server coupling gets looser in one specific way: valid-transition logic lives on the server, not duplicated in every client. If the business rule for when an order can be cancelled changes (say, cancellation is disabled once payment starts processing, not just once it succeeds), you change it in one place on the server, and every client (web, mobile, a partner's integration) picks up the new behavior automatically the next time they fetch the resource, because the cancel link simply stops appearing rather than each client needing an updated copy of the rule.

Why most public APIs skip it anyway. The honest reason is that hypermedia adds real client-side complexity (parsing and following links instead of calling a URL your team already documented and your SDK already hard-codes) for a benefit that mostly matters when you have many independent, evolving clients that cannot easily be updated in lockstep. Most companies' actual API consumers are their own web and mobile apps, deployed together with the backend, so the decoupling benefit is smaller than it sounds, and clients overwhelmingly prefer a documented, predictable URL they can call directly over a discovery protocol they have to implement. Full HATEOAS survives mostly in specs and prep material, not in most production public APIs, precisely because the cost (client complexity, harder caching of what actions exist) is paid up front while the benefit only shows up much later, if ever.

Trade-offs and pitfalls. Treat HATEOAS as a genuine trade-off you can articulate, not a rule you are expected to follow: if your API has one first-party client you control end-to-end, the coupling HATEOAS avoids barely exists in the first place.

Direct answer
Under active error-budget exhaustion from cascading 5xx errors, prioritize the mitigation that stops the cascade fastest with the least new risk: circuit breakers and request timeouts first (they cut the feedback loop immediately and are usually already-tested code paths), then backpressure/bulkheads to protect what's left, with retries-with-backoff and graceful degradation as the follow-up once the bleeding has stopped, not the first move.

Structured elaboration

• Circuit breakers, first: if a downstream change is causing cascading failures, the fastest way to stop the cascade is to stop CALLING the failing dependency; a circuit breaker (or a manual, config-driven kill switch if none exists yet for this path) halts the cascade immediately, faster than any code change can ship.
• Timeouts, immediately after: if calls to the failing dependency are hanging rather than failing fast, tightening the timeout (even a temporary, aggressive config change) frees up resources (threads, connections) being held hostage, which is often what's actually driving the cascade beyond the original failing dependency.
• Bulkheads/isolated thread pools: if the resource exhaustion has already spread to starve unrelated requests (see the bulkhead survivor), isolating pools limits further blast radius, though retrofitting a bulkhead mid-incident is a bigger, riskier change than flipping an existing breaker or timeout config.
• Retries with backoff and jitter: valuable for RECOVERY once the dependency is coming back, but retries added or left ENABLED during the active cascade make it worse, not better, by adding more load onto an already-struggling dependency; this is often the first thing to actively DISABLE, not add, during the incident.
• Backpressure: shedding load at the edge (rejecting a percentage of incoming requests outright, with a clear 503) protects the system's remaining capacity for the traffic it CAN serve, at the direct, visible cost of intentionally failing some requests.
• Graceful degradation: the longer-term fix (serve a fallback/cached response instead of failing) usually requires a code change that can't ship instantly during an active incident, so it's the follow-up hardening work, not the immediate mitigation.
• Measuring effectiveness: track the downstream dependency's own error rate and the error BUDGET burn rate in real time as each mitigation is applied; a mitigation is working if the burn rate visibly slows within minutes, not hours.

Worked example
During the incident: (1) immediately flip the circuit breaker for the failing downstream to force-open (or disable retries against it if no breaker exists) to stop the cascade; (2) tighten the client timeout for that dependency from 30s to 2s to stop threads from being held hostage; (3) if capacity is still degraded, enable load shedding (reject 20% of lowest-priority traffic) to protect the rest; (4) once the dependency confirms recovery, re-enable the breaker and retries gradually, watching the error rate as you do, rather than flipping everything back on at once.

Trade-offs and pitfalls
The instinctive first move during many outages is to add MORE retries ('the requests are failing, let's retry them harder'), which is exactly backwards during a cascading-failure incident: more retries onto an already-overloaded dependency deepens the cascade. The discipline that prevents this: stop calling the failing thing first, THEN worry about graceful recovery.

Direct answer

Adding the column itself should be near-instant: a plain ADD COLUMN with a constant (or
NULL) default is a metadata-only change on modern PostgreSQL and doesn't rewrite the
table. The actual risk is in populating it: run that as an explicit incremental backfill
in small batches with pacing between them, have the application dual-write the new column
on every new or updated row going forward before the backfill starts, and monitor replication lag (how far behind the primary a replica's copy of the data has fallen) and lock wait as hard caps that pause the job automatically.

The plan

The ADD COLUMN step itself. On PostgreSQL 11 and later, ADD COLUMN with a
constant default, including NULL, is metadata-only and does not rewrite existing rows.
That's a genuine change from older versions, and a common misconception is that any ADD COLUMN with a default rewrites the whole table; that's only true for a volatile,
non-constant default, or certain constraint additions. This step takes a brief exclusive
lock, but for milliseconds, a fundamentally different risk than the population step.

If a full backfill is needed (computing a derived value per row, the harder case this
question is really about):

• Incremental technique: iterate in small batches by primary-key range, each batch its
  own short transaction, with a brief pause between batches so replication and any read
  replicas can keep up, and so row locks don't accumulate into one long-held transaction.
• Dual-write: ship the application change that writes the new column on every new or
  updated row first, before the batch backfill starts, so the backfill isn't chasing a
  moving target. The batch job then only needs to cover rows written before that deploy.
• Monitoring and capping impact: watch replication lag (don't let a replica fall far
  enough behind that a failover would lose data, or that it starts serving badly stale
  reads); watch lock-wait time and set a lock_timeout so a batch that's queued too long
  aborts rather than backs up behind unrelated traffic; watch dead-tuple growth (a dead tuple is the old copy of a row that Postgres leaves behind after an UPDATE, since it writes a new row version instead of editing the old one in place); the backfill itself generates a dead row version for every update, a real bloat event, meaning the table fills up with dead tuples faster than they get cleaned out, at this row count that needs its own vacuum planning (VACUUM is the background process that reclaims the space those dead tuples hold so the table doesn't just keep growing); and cap the overall rate (target
  rows/sec) rather than running batches back to back as fast as possible.
• Backing out: since the column can be added nullable with nothing yet depending on it,
  backing out mid-backfill just means stopping the job. The column can sit partially
  populated with no correctness impact as long as nothing treats it as authoritative
  until the backfill and validation are complete, and the dual-write path can be
  feature-flagged off independently of the backfill's progress.

Worked example: backfill timing (pinned inputs)

total_rows = 400_000_000
batch_size_rows = 5_000
sleep_between_batches_ms = 50
exec_time_per_batch_ms = 20  # illustrative per-batch UPDATE execution time

num_batches = total_rows / batch_size_rows
time_per_batch_s = (sleep_between_batches_ms + exec_time_per_batch_ms) / 1000.0
total_time_s = num_batches * time_per_batch_s

print(f"num_batches = {num_batches:,.0f}")
print(f"time_per_batch = {time_per_batch_s*1000:.0f}ms")
print(f"total wall time = {total_time_s:,.0f}s = {total_time_s/3600:.1f} hours")

num_batches = 80,000
time_per_batch = 70ms
total wall time = 5,600s = 1.6 hours

Halving the batch size to 2,500 rows roughly doubles num_batches to 160,000 and, for a
similar per-batch overhead, roughly doubles the wall time to about 3.2 hours, a direct
trade between how gentle each batch is on the live system and how long the whole backfill
takes. That trade is worth sizing explicitly against how much time the migration is
actually allowed to take, not defaulted to "as small as possible."

Trade-offs and pitfalls

• Assuming ADD COLUMN itself is the risky step; on modern PostgreSQL with a constant
  default it usually isn't. The real risk in this scenario is almost always the
  subsequent full-table update to populate a derived value; don't spend the caution
  budget on the step that doesn't need it.
• Smaller batches and longer pauses are safer for the shared system but make the backfill
  take proportionally longer, size this trade-off deliberately, not by habit.
• Shipping the backfill before the dual-write path is verified working means the backfill is chasing a target that's still drifting from concurrent, uninstrumented writes: rows the backfill already processed keep getting changed by callers the dual-write path never reached, so the column silently falls out of sync with its source again after the batch job has already moved past that row. This is the same kind of drift failure that hits any derived copy of data, a cache, a summary table, a replica, whenever its update logic misses a write instead of catching every one.
• Not planning for the backfill's own bloat: 400 million updates generate 400 million
  dead tuples somewhere, a genuinely large vacuum workload competing with the same system
  the whole plan is trying not to disrupt.

Top-down (memoized recursive)

Approach: recursion with cache to avoid exponential recomputation.

# Python top-down memoized solution
from functools import lru_cache

def climb_memo(n: int) -> int:
    @lru_cache(maxsize=None)
    def dfs(k):
        if k == 0: return 1
        if k < 0: return 0
        return dfs(k-1) + dfs(k-2)
    return dfs(n)

Bottom-up (tabulation)

Approach: iterative DP filling array from base cases.

def climb_tab(n: int) -> int:
    if n == 0: return 1
    dp = [0] * (n+1)
    dp[0], dp[1] = 1, 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

Space-optimized O(1)

Use rolling variables since each state uses only two prior values.

def climb_rolling(n: int) -> int:
    if n == 0: return 1
    a, b = 1, 1  # a = ways(0), b = ways(1)
    for _ in range(2, n+1):
        a, b = b, a + b
    return b if n >= 1 else a

Complexity

• Memoized: Time O(n), Space O(n) for recursion + cache.
• Tabulation: Time O(n), Space O(n).
• Rolling: Time O(n), Space O(1).

Limitations & large n (n up to 1e9)

Naïve DP (O(n)) is infeasible for n = 1e9 due to time and memory. Use logarithmic-time methods: matrix exponentiation or fast doubling for Fibonacci-like recurrence. Both compute the nth Fibonacci in O(log n) multiplications; implement with modulo if counts must be bounded (common in backend services). Fast doubling is typically fastest and simplest to implement for integers at scale.