Senior Software Engineer Interview Preparation Guide (FAANG Standards)

Direct answer

Evaluate against the failure you are actually trying to fix, not the tool's feature list. Pilot on a small, real, high-friction slice of work with the people who will use it, not a toy example. Then treat adoption as something you have to earn, low switching cost, hands-on training, and visible evidence, rather than something you can mandate.

Structured elaboration

Evaluation: name the specific problem before comparing options, "deploys are manual and undocumented," not "we should modernize." Score a short list of real candidates against criteria that matter for this team specifically: integration cost with what you already run, learning curve for the team you actually have, and total cost including ongoing maintenance, not just the sticker price.

Pilot: pick a real, currently painful piece of work, not a demo, put a hard time box on it, and migrate a handful of concrete cases rather than the whole system. Instrument it so you can compare before and after, qualitatively at minimum, and with numbers you can show your work for where you actually measure them.

Getting real adoption, not a tool nobody uses:

1. Reduce switching cost directly: a starter template, a migration script, or paired sessions, not just published docs.
2. Find a credible first team, ideally one that is already vocal and frustrated with the status quo, and let their success be the pitch to the next team rather than a top-down mandate.
3. Expect and budget for a short-term velocity or quality dip during migration, for example a temporary regression while old and new systems run side by side, and get that dip pre-approved with your pilot data so it is not read as failure mid-rollout.
4. Make the new tool the path of least resistance. If the old way is still just as easy, most teams will quietly keep using it regardless of how much better the new one is.
5. Watch for adoption in name only: count teams actually using it in production, not teams who attended a training session.

Knowing when to reverse course: the same pilot discipline should let you kill an unpopular or risky tool cleanly too. If a pilot shows real operational risk, or the team genuinely cannot use it, that is a valid pilot outcome, not a failure of the champion.

Worked example

A team's nightly pipeline jobs were opaque and deploys were manual; engineers avoided touching the pipeline because a bad deploy was hard to diagnose and roll back. The proposal was a transformation framework with version-controlled, testable definitions orchestrated by a scheduler, instead of hand-rolled scripts. The pilot migrated three of the most-touched, most fragile pipelines, not the whole system, over four weeks, added tests for each, and wired basic deploy automation. Adoption plan: two hands-on working sessions instead of a slide deck, a working example repo new pipelines could copy from, and pairing with two engineers who became the first internal advocates.

Illustrative cost framing, stated up front rather than claimed after the fact: if a bad deploy previously cost about a day of debugging and happened roughly monthly, that is about 12 engineer-days a year, against an estimated 15 to 20 engineer-days to build and pilot the migration, so the pilot was expected to pay for itself within the first year even before counting ongoing savings from easier onboarding. The real adoption signal to watch for is simpler and harder to fake than any dashboard: did the next three pipelines that got touched get migrated voluntarily, or did people quietly keep writing the old way.

Trade-offs and pitfalls

• A pilot on a toy or greenfield example proves the tool works in ideal conditions, not that it survives your team's real mess. Pilot on something painful and real.
• Mandating adoption before switching cost is low produces compliance theater: people check the box during the pilot window and revert once attention moves on.
• Overselling the pilot's results erodes trust the first time someone re-runs your comparison and gets a different answer. Only claim what you can show.
• Committing to a tool because one senior engineer is enthusiastic about it, without a real pilot against a real failure, is how orgs end up maintaining tools nobody chose deliberately.

Direct answer

Name two to three concrete goals that span a delivery outcome, a relationship or context goal, and a craft improvement, then state one specific milestone you'd check yourself against at the interim mark, not a general feeling of being "on track." The exact goals should shift with the horizon asked, first six months, first year, or two to three years, and with the seniority of the role.

Structured elaboration

• Match scope to horizon. A first-six-months goal set is mostly about ramp-up and one visible first contribution; a first-year set adds one meaningful, largely independent delivery plus established trust with key stakeholders; a two-to-three-year set shifts toward growth in scope, ownership, or a chosen specialization rather than a single deliverable.
• Cover three goal types, not just the technical one: a concrete problem solved or thing shipped, a context and relationship goal (understanding the systems and people whose buy-in you'll need for anything ambitious later), and a craft or process improvement you personally own end to end.
• Attach a leading indicator to each goal, something observable well before the deadline, not just the final outcome. This is what makes a mid-point check-in credible instead of a guess.
• Calibrate ambition to seniority. A candidate for a more senior role should include a scope or influence goal, not only execution goals; someone earlier in their career should show they understand ramp-up comes first.
• The single strongest closing move: state the concrete milestone you'd check yourself against at the interim mark, a specific thing shipped, a decision made, feedback actually received, rather than restating the goals as if listing them again proves progress.

Worked example

When I started a previous role, I set three goals for the year: ship one meaningful improvement to a system that mattered to the team, build real working relationships with the two or three people whose sign-off I'd need for anything ambitious later, and establish one process habit I could point to as mine. At the six-month mark, my checkpoint wasn't "do I feel settled," it was two specific things: had I shipped the first version of that improvement, and could I name the people who'd actually back me if I proposed the next, bigger version of it. Both were true, so instead of starting a new goal from zero, I used the credibility from the first six months to scope a larger version of the same problem for the rest of the year.

Trade-offs & pitfalls

• Vague goals ("learn a lot," "add value") signal you haven't actually thought this through; goals that depend entirely on something outside your control (a launch owned by another team) are the opposite failure.
• Loading up only on technical goals while skipping relationship or context goals tends to stall growth later, once the technical work is good you still need sponsors.
• Skipping the interim checkpoint definition means "on track" becomes something you decide retroactively rather than something you can actually check.
• Answering with only execution goals at a senior level under-signals; answering with only scope-and-influence goals very early on over-signals.

The idea in plain words

Rabin-Karp slides a window the length of the pattern across the text and compares a small number (a hash, a fingerprint of the window) instead of the characters. A rolling hash updates that number in constant time when the window moves one place. Two different windows can share a fingerprint (a collision), so a fingerprint match is only a suspect, and the usual code then compares the characters (verification). The expected running time O(n + m) assumes few collisions. An attacker who controls the text attacks exactly that assumption, in two different ways, and the two need two different defences.

How a rolling hash is computed

Pick a base (a small multiplier) and a modulus (a number the result is reduced by, so it stays small). Treat the window as a number written in that base: the hash of abc with letters valued a=1, b=2, c=3 and base 10 is 1100 + 210 + 3 = 123. To slide one place, subtract the leading letter's contribution, multiply by the base, and add the new letter. This is the update used in the code below, with a tiny base and modulus so the arithmetic can be followed by hand.

BASE, MOD = 10, 1_000_003          # tiny base so the arithmetic can be followed by hand

def window_hash(s):
    h = 0
    for ch in s:
        h = (h * BASE + ord(ch) - 96) % MOD     # a=1, b=2, c=3, ...
    return h

h_abc = window_hash("abc")
print("hash of abc =", h_abc, "(1*100 + 2*10 + 3)")
top = BASE ** 2                                  # weight of the leading letter in a window of length 3
h_bcd = ((h_abc - 1 * top) * BASE + 4) % MOD
print("slide: remove a, shift, add d ->", h_bcd, "; direct hash of bcd =", window_hash("bcd"))

Output:

hash of abc = 123 (1*100 + 2*10 + 3)
slide: remove a, shift, add d -> 234 ; direct hash of bcd = 234

Everything that follows is this same computation with a large base and modulus.

Attack 1: force collisions

If the base and modulus are fixed and known (they are in the source code, or can be probed), the attacker builds inputs where many windows have the pattern's fingerprint but are not the pattern. Each such window costs an O(m) verification, and the attacker chooses how many there are. A classic case is hashing with a 64-bit unsigned integer that overflows, which is arithmetic modulo 2^64. A Thue-Morse string (a binary sequence built by repeatedly appending the complement of what you have; here a/b letters, so abba is followed by its swap baab) and its letter-swapped complement can have the same hash when the arithmetic is modulo 2^64. The reason is visible on the 4-letter pair X = abba and Y = baab: the difference of their hashes is, up to sign, the product (base - 1) * (base^2 - 1), and for length 2^k it is a product of k such factors, one per doubling. With an odd base every factor is even, and the powers of 2 add up across the factors. For base 257 the factors carry 2^8, 2^9, 2^10, ... (base - 1 = 256 is already 2^8), so the seven factors of a length-128 string carry 8 + 9 + ... + 14 = 77 powers of two, more than 64. Once the product is divisible by 2^64 the two hashes are equal modulo 2^64. Every odd base reaches that by length 1024: the first factor carries at least one power of two and the factor for the i-th doubling (i = 1, 2, ...) at least i + 2, so ten factors carry at least 1 + 3 + 4 + ... + 11 = 64. Base 1000003 in the run below is exactly that worst case.

def thue_morse(k):
    word = [0]
    for _ in range(k):
        word += [1 - x for x in word]
    return "".join("ab"[x] for x in word)

def hash_mod(s, base, mod):
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % mod
    return h

X4 = thue_morse(2)
Y4 = X4.translate({ord("a"): ord("b"), ord("b"): ord("a")})
b = 257
print(X4, Y4, "hash difference =", hash_mod(X4, b, 1 << 64) - hash_mod(Y4, b, 1 << 64))
print("(b-1)*(b**2-1) =", (b - 1) * (b * b - 1))
for base in (31, 257, 1000003):
    found = []
    for k in range(2, 11):
        X = thue_morse(k)
        Y = X.translate({ord("a"): ord("b"), ord("b"): ord("a")})
        if hash_mod(X, base, 1 << 64) == hash_mod(Y, base, 1 << 64):
            found.append(len(X))
    print("base", base, "collides mod 2**64 at lengths", found)

Output:

abba baab hash difference = -16908288
(b-1)*(b**2-1) = 16908288
base 31 collides mod 2**64 at lengths [256, 512, 1024]
base 257 collides mod 2**64 at lengths [128, 256, 512, 1024]
base 1000003 collides mod 2**64 at lengths [1024]

So a constant odd base does not rescue a power-of-two modulus: base 257 collides from length 128 up, base 31 from length 256 up, and base 1000003 at length 1024 (the longest length the run tries). A hash of a window is the sum of the hashes of its letters weighted by powers of the base, so a window made of blocks that are each either X or its complement Y collides with a pattern made of X blocks of the same length.

Verification stops at the first letter that differs, so the attacker wants the first Y block as late in the window as possible: the later it sits, the more of the pattern is compared before the mismatch. The demo text below places one Y per 64 blocks, so the first mismatch lands at a different place in each window; a text that kept it near the end of every window would cost more.

Attack 2: no collisions needed

Text a repeated n times and pattern a repeated m times: every window is a true match. A verify-on-hit program compares all m characters at every position, so the cost is about n*m even with a perfect hash. Verification fixes correctness; it does not bound time.

Hardening

An interview answer needs the first, second, fourth and fifth items (random base, prime modulus, verify, budget with fallback); the third is an optional strengthening, and the sixth and seventh are alternatives to the whole design.

1. Random base per call (from a cryptographic random source such as Python's secrets, which an attacker cannot predict, unlike a clock-seeded generator), not a constant. The attacker cannot precompute colliding strings for a base they cannot see. Cost: almost nothing (one pow and one random call), but runs are no longer reproducible, so log the chosen base in test environments so a failing run can be replayed.
2. A prime modulus, not a power of two. For two different windows of length m, the difference of their hashes is a polynomial in the base with degree at most m-1, and it is not the zero polynomial. A nonzero polynomial of degree d has at most d roots modulo a prime p (a base that makes the difference exactly 0). A uniformly random base is therefore a bad base for that pair with probability at most (m-1)/p. A small check: with p = 101 and windows of length 3 over the letters a, b, c, no pair of different windows collides for more than 2 of the 101 bases.

from itertools import product

P, M = 101, 3                      # tiny prime modulus, windows of length 3
def h(w, base):
    v = 0
    for ch in w:
        v = (v * base + ord(ch) - 96) % P
    return v

worst = 0
windows = ["".join(t) for t in product("abc", repeat=M)]
for u in windows:
    for w in windows:
        if u != w:
            bad = sum(h(u, base) == h(w, base) for base in range(P))
            worst = max(worst, bad)
print("most bases (out of", P, ") that make two different length-3 windows collide:", worst, "; bound m-1 =", M - 1)

p1, p2, n, m = 2**61 - 1, 2**31 - 1, 10**6, 10**4   # moduli, number of windows, window length
print(f"expected false hits: one hash {n * (m - 1) / p1:.1e}, two hashes {n * (m - 1) / p1 * (m - 1) / p2:.1e}")

Output:

most bases (out of 101 ) that make two different length-3 windows collide: 2 ; bound m-1 = 2
expected false hits: one hash 4.3e-09, two hashes 2.0e-14

With p = 2^61 - 1, n = 10^6 windows and m = 10^4, the expected number of false hits is about n*(m-1)/p, which is 4.3e-9 (printed by the program above). Cost: Python handles it natively; in C or Java the product of two 61-bit values can exceed 64 bits, so it needs a 128-bit type or a multiply split into halves.
3. Two independent hashes (independent random bases and second modulus 2^31 - 1). A collision must happen in both, so the probabilities multiply: the same example gives about 2.0e-14 (printed by the same program). Cost: roughly twice the arithmetic per character and twice the state to store.
4. Verify every hit. A residual false positive then costs time but cannot produce a wrong answer. Cost: O(m) per hit, which is exactly attack 2.
5. A work budget and a deterministic fallback. Count the characters compared during verification. When the count passes a multiple of n + m (4 times n + m below), stop and run KMP (Knuth-Morris-Pratt, a linear-time search that needs no hashing) on the whole input. The worst case is then the budget plus O(n + m). Cost: a second algorithm to maintain and test, and an unlucky-but-honest input (many true overlapping matches) switches algorithms.
6. Skip verification when a tiny error probability is acceptable (de-duplication, fingerprinting). The time is then always O(n + m), but a wrong answer is possible with the probability above. Not a choice for a search whose result drives security decisions.
7. Choose a deterministic algorithm when the text is untrusted and there is only one pattern: KMP or the Z-algorithm (another linear-time matcher that computes, for every position, how long a prefix of the pattern matches there) give O(n + m) worst case with no randomness. Rabin-Karp earns its place with many patterns of the same length, where one rolling hash is looked up in a set.

The code

import secrets

MASK64 = (1 << 64) - 1
P1, P2 = (1 << 61) - 1, (1 << 31) - 1          # two prime moduli


def rabin_karp_fixed(text, pattern, verify=True):
    """Textbook version: base 257, arithmetic modulo 2**64. Returns (hits, char comparisons)."""
    n, m = len(text), len(pattern)
    if m > n:
        return [], 0
    base, top = 257, pow(257, m - 1, 1 << 64)
    hp = ht = 0
    for i in range(m):
        hp = (hp * base + ord(pattern[i])) & MASK64
        ht = (ht * base + ord(text[i])) & MASK64
    hits, compared = [], 0
    for s in range(n - m + 1):
        if hp == ht:
            if verify:
                k = 0
                while k < m and text[s + k] == pattern[k]:
                    k += 1
                compared += min(k + 1, m)
                if k == m:
                    hits.append(s)
            else:
                hits.append(s)
        if s + m < n:
            ht = ((ht - ord(text[s]) * top) * base + ord(text[s + m])) & MASK64
    return hits, compared


def kmp(text, pattern):
    fail, k = [0] * len(pattern), 0
    for i in range(1, len(pattern)):
        while k and pattern[i] != pattern[k]:
            k = fail[k - 1]
        k += pattern[i] == pattern[k]
        fail[i] = k
    hits, k = [], 0
    for i, ch in enumerate(text):
        while k and ch != pattern[k]:
            k = fail[k - 1]
        k += ch == pattern[k]
        if k == len(pattern):
            hits.append(i - len(pattern) + 1)
            k = fail[k - 1]
    return hits


def rabin_karp_hardened(text, pattern, budget_factor=4):
    """Random bases, two moduli, verify each hit, fall back to KMP if verification gets expensive.
    Returns (hits, char comparisons, whether the fallback ran)."""
    n, m = len(text), len(pattern)
    if m > n:
        return [], 0, False
    b1, b2 = 256 + secrets.randbelow(P1 - 512), 256 + secrets.randbelow(P2 - 512)
    t1, t2 = pow(b1, m - 1, P1), pow(b2, m - 1, P2)
    p1 = p2 = w1 = w2 = 0
    for i in range(m):
        p1, p2 = (p1 * b1 + ord(pattern[i])) % P1, (p2 * b2 + ord(pattern[i])) % P2
        w1, w2 = (w1 * b1 + ord(text[i])) % P1, (w2 * b2 + ord(text[i])) % P2
    hits, compared, budget = [], 0, budget_factor * (n + m)
    for s in range(n - m + 1):
        if (p1, p2) == (w1, w2):
            k = 0
            while k < m and text[s + k] == pattern[k]:
                k += 1
            compared += min(k + 1, m)
            if k == m:
                hits.append(s)
            if compared > budget:
                return kmp(text, pattern), compared, True
        if s + m < n:
            w1 = ((w1 - ord(text[s]) * t1) * b1 + ord(text[s + m])) % P1
            w2 = ((w2 - ord(text[s]) * t2) * b2 + ord(text[s + m])) % P2
    return hits, compared, False


def thue_morse(k):
    word = [0]
    for _ in range(k):
        word += [1 - x for x in word]
    return "".join("ab"[x] for x in word)


if __name__ == "__main__":
    X = thue_morse(7)                                   # 128 letters
    Y = X.translate({ord("a"): ord("b"), ord("b"): ord("a")})
    print("X != Y but same hash mod 2**64:", X != Y, rabin_karp_fixed(Y, X, verify=False)[0])
    print("with verification the false hit is rejected:", rabin_karp_fixed(Y, X)[0])

    blocks = 64
    pattern = X * blocks                                # length 8192
    text = (X * (blocks - 1) + Y) * 4                   # length 32768, one Y per 64 blocks
    n, m = len(text), len(pattern)
    hits, compared = rabin_karp_fixed(text, pattern)
    print(f"attack, fixed hash:    n={n} m={m} hits={len(hits)} comparisons={compared}")
    hits, compared, fell_back = rabin_karp_hardened(text, pattern)
    print(f"attack, hardened:      hits={len(hits)} comparisons={compared} fallback={fell_back}")

    text = "a" * 20000
    pattern = "a" * 5000
    hits, compared = rabin_karp_fixed(text, pattern)
    print(f"all-true matches, verify only: hits={len(hits)} comparisons={compared}")
    hits2, compared2, fell_back = rabin_karp_hardened(text, pattern)
    print(f"all-true matches, hardened:    hits={len(hits2)} comparisons={compared2} fallback={fell_back}")
    assert hits2 == hits == kmp(text, pattern)

Output:

X != Y but same hash mod 2**64: True [0]
with verification the false hit is rejected: []
attack, fixed hash:    n=32768 m=8192 hits=0 comparisons=789409
attack, hardened:      hits=0 comparisons=0 fallback=False
all-true matches, verify only: hits=15001 comparisons=75005000
all-true matches, hardened:    hits=15001 comparisons=105000 fallback=True

Reading the output

• X and Y (128 letters each, differing everywhere) give a false hit at position 0 with verification off, and verification rejects it.
• The attack text has 32,768 characters, the pattern 8,192, and there are no true matches at all. The fixed-hash version nevertheless compares 789,409 characters during verification, about 24 times the text length, and the factor grows with the pattern length. The hardened version, with a random base and two prime moduli, compares none, because no window's fingerprint equals the pattern's.
• With 20,000 as and a pattern of 5,000 as there are 15,001 true matches. Verify-only compares 75,005,000 characters (15,001 times 5,000, about 3,750 times the text length). The hardened version stops verifying once the count exceeds 4 * 25,000 = 100,000 (it had reached 105,000) and finishes with KMP, returning the same 15,001 positions.

Complexity

Honest case: O(n + m) time with O(1) extra space (the hash state), plus O(m) per verified hit. Attack 1 and attack 2 push the verification cost to O(n*m) for the fixed version. The hardened version is bounded by O(budget + n + m), where the budget is 4 * (n + m), so O(n + m) in the worst case, and its KMP fallback uses O(m) space.

Edge cases and common mistakes

• Pattern longer than the text returns no hits (both functions check it). An empty pattern happens to work in this Python listing (it returns every index from 0 to n) only because pow(base, -1, modulus) is the modular inverse, so top is defined and cancels in the update; in languages where the exponent m - 1 = -1 is not valid, add an early return.
• Subtracting the leading character after the modulus can go negative in languages with signed remainders; add the modulus back. Python's % is always non-negative.
• Seeding a "random" base from the clock or from a value the attacker can observe is not random to the attacker.
• Using the same base for both hashes (then they collide together), or a second modulus that is a multiple of the first.
• Believing verification makes Rabin-Karp safe: it makes it correct, not fast.

Running the code

# Python 3.12, standard library only
# save the three small blocks as hash_primer.py, thue_morse_collision.py, root_bound.py
# save the main listing as rolling_hash_attack.py
python hash_primer.py
python thue_morse_collision.py
python root_bound.py
python rolling_hash_attack.py

Direct answer

Psychological safety, in a mentoring relationship, is a mentee's confidence that they can ask a question, admit a mistake, or push back on something without it costing them standing or opportunity. It's built through small, consistent moments early on, and it's genuinely tested the first time the mentee takes a visible risk and sees how you respond.

Concrete early actions

• Name failure modes yourself first. Mentioning a mistake you made in a similar situation signals that admitting error is normal here, not a one-way expectation.
• Model uncertainty openly. Say "I don't know, let's find out" instead of bluffing, so not-knowing reads as acceptable.
• Treat early mistakes as expected, not exceptional. React to a mistake by focusing on the fix and what it reveals, not on assigning blame.
• Be consistent between casual moments and anything formal. If private conversations are open but a formal review contradicts them, trust breaks immediately.
• Give credit publicly, give hard feedback privately. This is the pattern most people are watching for even if they never say so.
• Agree explicitly that disagreement is welcome, and actually respond well the first time it happens.

Worked example

Early in a relationship, a mentee admitted they'd made a mistake that caused some rework. The response focused entirely on understanding what happened and fixing it, walking through the reasoning openly rather than assigning blame, and treating it as a useful, expected part of learning. In the sessions that followed, the mentee started surfacing problems earlier and asking more pointed questions, rather than waiting until something couldn't be hidden.

Trade-offs and pitfalls

A common mistake is treating psychological safety as a one-time opening statement ("feel free to ask me anything") rather than an ongoing pattern that has to survive contact with a real mistake. The mentee will judge safety retrospectively, based on what actually happened the first time they took a risk, not on what was said at the start. It's also worth not confusing psychological safety with lowered standards: it's about how failure is handled and discussed, not about removing accountability for the work.

Direct answer

For 200 million monthly active users (MAU) and 10,000 writes/sec, a pure fan-out-on-write pushes every new post into every follower's feed at write time, buying very low read latency at the cost of massive write amplification and storage. Pure fan-out-on-read defers that work to feed-view time, keeping writes cheap but making every read do more work. A celebrity account with millions of followers breaks the pure push model outright, which is why the practical answer is a hybrid: push for ordinary accounts, pull (or a separate merge step) for very high-fan-out accounts.

Structured elaboration

The decision criterion is the read:write ratio implied by a given account's follower count, not a single global choice: an account followed by 200 people generates trivial fan-out and huge read-latency benefit from push; an account followed by millions generates enormous fan-out for a benefit (marginally faster reads for those followers) that pull-at-read can approximate at read time instead.

Worked example

At 10,000 writes/sec, assume (illustrative, pinned input) an average of 300 followers per post for non-celebrity accounts:
$\text{fan-out ops/s} = 10{,}000 \text{ writes/s} \times 300 \text{ avg followers} = 3{,}000{,}000 \text{ inbox writes/s}$
That is the write-amplification cost a pure push model pays continuously just for ordinary accounts.

Now take one celebrity post going to 5 million followers, and assume (illustrative) a fan-out cluster capable of sustaining 500,000 inbox writes/s:
$\text{time to fan out one celebrity post} = \frac{5{,}000{,}000 \text{ followers}}{500{,}000 \text{ writes/s cluster capacity}} = 10 \text{ s}$
A single celebrity post would take roughly 10 seconds to fully propagate through push fan-out, and that's before accounting for every other post competing for the same fan-out capacity at the same time. This is the concrete reason celebrity accounts change the answer: pushing their posts synchronously into millions of inboxes is not just expensive, it measurably delays delivery to everyone else sharing that fan-out capacity.

Trade-offs & pitfalls

• Treating fan-out-on-write and fan-out-on-read as a single global choice, rather than a per-account decision keyed on follower count, is the most common shallow answer.
• A hybrid design still needs a merge step at read time for celebrity posts, so pull-style merge logic doesn't disappear; it just gets scoped to a small fraction of accounts instead of all of them.
• Async, idempotent fan-out pipelines are required regardless of strategy, because retries and partial failures are certain at this scale; a synchronous fan-out-on-write implementation is a reliability risk independent of the storage trade-off.
• Caching the celebrity's own recent posts aggressively (rather than fanning them out) reduces the read-time merge cost without reintroducing full push fan-out.

Direct answer

The 0/1 knapsack DP state is dp[c] meaning "maximum total value achievable using a budget of exactly (or up to) c," updated per item by dp[c] = max(dp[c], dp[c - weight] + value), iterating capacities in descending order so each item is only used once. If the question changes from "maximize value" to "is some exact target sum achievable at all," the state becomes a boolean reachable[s] instead of a running maximum, using the identical recurrence shape (reachable[s] = reachable[s] or reachable[s - weight]) but tracking reachability instead of an optimum. This exact-sum variant is the same shape as the well-known Partition Equal Subset Sum problem, which asks whether a set of numbers can be split into two subsets with equal totals.

Structured elaboration

Value-maximization DP.

def knapsack_max_value(weights, values, capacity):
    """
    0/1 knapsack: maximum total value without exceeding capacity, each item
    at most once. dp[c] = best value achievable with budget c.
    Time O(n * capacity), Space O(capacity) (rolling 1D array).
    """
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # descending: each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

Feasibility (exact-sum) DP. Change the table's meaning from "best value so far" to "is this sum reachable," and change the update from a max to a boolean OR:

def subset_sum_feasible(weights, target):
    """
    Can some subset of weights sum to exactly target?
    reachable[s] = True if sum s is achievable using a subset of items seen
    so far. Same 0/1 recurrence as knapsack, but the DP value is a boolean
    "reachable" flag instead of a running maximum.
    Time O(n * target), Space O(target).
    """
    reachable = [False] * (target + 1)
    reachable[0] = True
    for w in weights:
        for s in range(target, w - 1, -1):
            if reachable[s - w]:
                reachable[s] = True
    return reachable[target]

Partition Equal Subset Sum is exactly this feasibility check with target set to half the total sum of the input numbers (if the total is odd, an equal split is impossible immediately, no DP needed). The same feasibility shape also applies to budget-constrained subset-selection outside pure combinatorics: for example, choosing dashboard KPIs or metrics under a display-cost budget, where each metric has a fixed "screen cost" and you want to know whether some subset exactly fills an allotted display budget (or, with the max-value version, which subset of metrics maximizes total business value within that budget).

Worked example

weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack_max_value(weights, values, 5))

Output: 7 (taking the weight-2/value-3 and weight-3/value-4 items exactly fills the capacity-5 budget for total value 7; no other combination of these items reaches higher value within capacity 5).

nums = [1, 5, 11, 5]
total = sum(nums)
print(total, total % 2 == 0, subset_sum_feasible(nums, total // 2) if total % 2 == 0 else None)

Output: 22 True True. The total is 22 (even), so an equal split needs a subset summing to 11; subset_sum_feasible confirms 11 is reachable (via 5 + 5 + 1), so [1, 5, 11, 5] can be partitioned into two equal-sum halves.

Trade-offs & pitfalls

Key points

• Greedy selection by value-to-weight ratio is optimal for the fractional knapsack (where you can take a fraction of an item) but is not guaranteed optimal for 0/1 knapsack, since taking a high-ratio item can leave awkward leftover capacity that a different combination would have used better.
• The feasibility DP is strictly cheaper to reason about than the value-maximization DP (booleans instead of running maxima), but it answers a narrower question: it tells you whether a target is reachable, not which subset achieves it, unless you also track parent pointers or reconstruct the choice by scanning backward through the table.
• Both DP variants are pseudo-polynomial: their cost scales with the numeric capacity or target value, not just the number of items, so a very large capacity or target (in the millions) can make the DP impractical even though the item count is small; that is where a greedy approximation or a meet-in-the-middle exact method becomes attractive.

Complexity

• Value-maximization: time $O(n \cdot W)$, space $O(W)$, where n is the item count and W is the capacity.
• Feasibility: time $O(n \cdot T)$, space $O(T)$, where T is the target sum.

Edge cases

• Target or capacity of 0: dp[0]/reachable[0] are the trivial base cases (empty selection), both handled directly.
• An item heavier than the remaining capacity: naturally excluded by the descending-range guard (w - 1 lower bound), never considered for smaller capacities.
• Odd total sum in the partition-equal-subset-sum framing: no DP needed at all, an equal-value split is impossible by simple arithmetic before touching the table.

Direct answer

I would first pin down what "10% more retention" means, because the roadmap depends on it. Then I would build the roadmap from the reasons small businesses actually leave, not from a list of features we like. And at month three I would judge it by leading indicators (early behaviours that predict staying), because true retention cannot be read that fast.

Step 1: Make the target measurable

Retention means the share of customers who are still subscribed after a period. "10% more" is ambiguous. Suppose annual logo retention (customers kept, counted by account, not revenue) is 80% today. A 10% relative gain means 88%. A 10-point gain means 90%.

monthly churn = 1 - (annual retention)^(1/12)
at 80%: 1 - 0.80^(1/12) = about 1.84% of accounts lost per month
at 88%: 1 - 0.88^(1/12) = about 1.06% of accounts lost per month

So the target means cutting monthly churn by roughly 42% (1.06 divided by 1.84 is about 0.58, so churn has to fall by the remaining 42%), which is a much bigger ask than "10%" sounds. I would say that out loud to the product owner before committing.

Step 2: Choose what goes in

1. Segment churned accounts from the last two quarters and read exit surveys and support tickets. For small businesses the usual causes are never reaching a first useful result, a missing integration, billing failures, and the one admin who set the product up leaving.
2. Turn each cause into a candidate bet, then ask three questions per bet: how many churned accounts does it plausibly touch, how directly does it cause a stay-or-leave decision, and how large is it compared with our capacity?
3. Reserve capacity: most to the top one or two causes, a small slice for reliability work on flows customers use daily (a slow or broken core flow shows up as churn), and a slice for measurement so we can see results at all.
4. Sequence so the earliest items affect the earliest customer moments (onboarding first, because churn is highest in the first months), and the slow items start early.

Step 3: Month-three check

Worked example with illustrative numbers: 1,000 accounts at 1.84% monthly churn lose about 18 per month. The target pace is about 11. Month-to-month counts of that size swing by roughly 4 either way by chance (counts of independent events such as cancellations typically wobble by about the square root of the count, and the square root of 18 is about 4), so one month of churn data cannot distinguish 18 from 11 reliably. Hence I would agree three leading indicators in advance, each tied to a bet: share of new accounts reaching a first useful outcome within seven days, weekly active use of the feature each bet targets, and failed-payment recovery rate. At month three I compare the cohorts (groups of accounts that signed up in the same period) that got the changes against earlier cohorts, or against a holdout (a small group of accounts deliberately kept on the old experience) where we ran one, and ask whether these early behaviours moved.

Trade-offs and pitfalls

• Shipping many small features that nobody connects to a churn cause.
• Declaring victory on feature usage while churn is flat. Usage is a means.
• Judging month three on one month of churn.
• What would change my plan: if exit data shows most churn is businesses closing or being acquired, product work cannot reach it, and I would say the target needs reframing.

Direct answer. Use a story where you made three distinct calls (one accepted, one deferred, one refused) and explain the rule behind them. Here is a plausible example shape for a partner-integration launch with a fixed date; use your own real details.

Situation. A team had a committed launch date for an API integration with a large partner. In the design review I found three gaps: no per-partner rate limiting, no exportable audit log of partner activity, and a single shared administrative credential used by the deployment job.

Task. Protect the launch date where possible without shipping something I could not defend, and make sure the people who owned the risk made the call knowingly.

How I decided. I used one rule: what is the harm if it goes wrong, and can we fix it afterward without rework?

What I did

• Refused: the shared administrative credential. One leaked job credential would expose every customer, and nothing about it could be reversed after the fact. The fix was small (a scoped credential per job), so I offered the engineers pairing time and it went in before launch.
• Deferred: the audit-log export. Events were already being logged centrally; only the customer-facing export was missing. I got a named owner and a date written into the launch ticket, plus an interim step: security could pull logs for a partner on request.
• Accepted: per-partner rate limiting. Abuse risk was bounded because the partner was a known party under contract, and a global limit existed. The product owner signed a risk acceptance stating the risk, the global limit as the compensating control, and a review date tied to the second partner onboarding.

Result. The launch kept its date. The shared credential never shipped, the audit export arrived on its committed date, and the rate-limit acceptance was reopened when the second partner arrived and was then implemented. I measured success by those commitments being met and by no exceptions expiring unreviewed.

What I would do differently. I would have raised the three gaps a sprint earlier by reading the design draft rather than waiting for the review meeting, which would have let the team fix more before the date pressure peaked.

Pitfalls. Do not present only refusals (you look like a blocker) or only concessions (you look like you have no line). Show the principle, the alternative you offered, and who owned each accepted risk.

Direct answer

Shortlist MongoDB (self-managed or Atlas) and DynamoDB paired with Amazon DocumentDB Elastic Clusters (a sharded, MongoDB-API-compatible AWS service) as the two realistic candidates, and recommend MongoDB as the primary pick for this exact combination: a variable JSON schema plus secondary queries on NESTED fields is precisely what MongoDB's indexing was built to answer directly, while DynamoDB's indexing only covers top-level attributes, so DynamoDB either forces you to flatten every queryable nested field at write time or bolt on a second search system just to answer the query the question is asking for.

Structured elaboration

Indexing on nested fields. MongoDB supports multikey and compound indexes on any dotted path inside a document (for example profile.address.city), so a query like "find profiles where preferences.notifications.email is true" is a direct, indexed lookup. DynamoDB indexes (its partition/sort key, plus up to 20 global secondary indexes, GSIs, per table) only cover TOP-LEVEL attributes; querying inside a nested JSON blob means either promoting the field you need to query into a flat top-level attribute at write time, or exporting the data into a separate search index (OpenSearch) and keeping the two in sync. Couchbase, via its SQL++/N1QL query language and Global Secondary Indexes, can also index array and nested fields directly, making it a closer functional match to MongoDB than to DynamoDB here.

Schema evolution. All three stores are schema-flexible at the storage layer: none require an ALTER TABLE-style migration to add a field. The real cost of schema evolution shows up in application code (readers that must tolerate old and new document shapes at once), not in the database, for any of the three.

Write throughput at 10k writes/s. For DynamoDB, one write capacity unit (WCU) covers one standard write of up to 1 KB, and a documented soft limit caps a single partition at 1,000 WCU/s, so the table needs to be split across enough partitions for the traffic to avoid throttling on any one of them:

writes_per_sec = 10_000
kb_per_item = 1  # ~1 KB profile write
wcu_per_sec = writes_per_sec * kb_per_item
wcu_limit_per_partition = 1000  # AWS documented soft limit
min_partitions = wcu_per_sec / wcu_limit_per_partition
print(f"total WCU/s needed: {wcu_per_sec:,}")
print(f"minimum partitions at the per-partition limit: {min_partitions:.0f}")
print(f"partitions with 3x headroom: {min_partitions * 3:.0f}")

total WCU/s needed: 10,000
minimum partitions at the per-partition limit: 10
partitions with 3x headroom: 30

10,000 writes/s is comfortably achievable by any of the three; it is not the deciding factor here. MongoDB scales writes by sharding, and reaching this rate needs a shard key with enough cardinality to spread writes evenly (a hashed key, or a high-cardinality field like user_id); a monotonically increasing key would concentrate writes on the newest shard, the same hot-partition failure mode DynamoDB has under a different name.

Replication. MongoDB uses replica sets (one primary, multiple secondaries, asynchronous by default, with an optional "majority" write concern that waits for acknowledgement from a majority of replicas at a latency cost). DynamoDB replicates synchronously across AZs within a region by default, and across regions via Global Tables if needed. Couchbase supports cross-datacenter replication (XDCR).

Sharding. MongoDB shards natively via mongos routers and config servers, with range or hashed sharding on a chosen key. DynamoDB auto-partitions transparently, with no operator control beyond key design. Instance-based Amazon DocumentDB does NOT shard writes at all (a single primary handles every write, with up to 15 read replicas for read scaling only); Amazon DocumentDB Elastic Clusters is a separate, newer AWS product that does add hash-based write sharding (up to 32 shards) while keeping the MongoDB-compatible API, which is the option to reach for if the team specifically wants document-store query flexibility with AWS-managed write sharding.

Backups. MongoDB Atlas offers continuous backups with point-in-time restore. DynamoDB offers point-in-time recovery (PITR) and on-demand backups. Couchbase has its own backup service.

Recommendation. For 10k writes/s (a modest, easily-provisioned rate for any of these) with a p95 write latency under 20ms and a hard requirement to secondary-query NESTED fields, MongoDB's native multikey/compound indexing is the most direct fit: the team writes the query it actually means, rather than redesigning the schema every time a new nested field needs to become queryable. If the organization is already AWS-committed and wants a single fully-managed vendor, DynamoDB plus DocumentDB Elastic Clusters (or DynamoDB with an OpenSearch index kept in sync via DynamoDB Streams) is a reasonable fallback, at the real cost of running two systems, a source of truth and a query index, for one job.

Worked example

If a single MongoDB shard, on typical cloud hardware, comfortably sustains a few thousand writes per second for a roughly 1 KB document (an estimate for sizing purposes, not a measured benchmark), then reaching 10,000 writes/s needs on the order of 3 to 4 shards with a well-distributed shard key, a small, ordinary Atlas cluster, not a scale-driven reason to avoid MongoDB.

Trade-offs & pitfalls

The "flatten for query" trap is the main risk of choosing DynamoDB here: teams pick it for its operational simplicity and then discover they need to query inside a JSON blob, and end up either denormalizing every field they might ever query into a top-level attribute (constant schema churn) or bolting on OpenSearch as a second, eventually-consistent system that has to be kept in sync via streams. On the MongoDB side, the classic mistake is letting a nested array grow without bound (an embedded activity log on the profile document) until it approaches the 16 MB document size ceiling and degrades write performance well before that; unbounded lists belong in a separate, referencing collection, not embedded.

Direct answer

A topological sort orders the jobs in a directed acyclic graph (DAG) of dependencies so that every job appears after everything it depends on. Kahn's algorithm computes this by repeatedly running jobs whose dependencies are all satisfied (in-degree zero) and removing them from consideration; the DFS-based approach computes it by finishing a full depth-first exploration of each job's dependents before recording the job itself, then reversing that finish order. Cycle detection falls out of each approach differently, and tie-breaking between simultaneously-runnable jobs needs an explicit policy, since neither algorithm has an opinion about which "ready" job should go first beyond whatever order it happens to process them in.

Structured elaboration

Kahn's algorithm. Compute in-degree (number of unmet dependencies) for every job. Seed a queue with every job whose in-degree is already zero. Repeatedly pop a job, append it to the schedule, and decrement the in-degree of every job that depends on it; any dependent whose in-degree just reached zero joins the queue. If the final schedule has fewer jobs than the graph, some jobs never reached in-degree zero: that is exactly a cycle.

DFS-based approach. Run depth-first search (DFS) from every job, marking each as visiting when entered and visited when all its dependents have been fully processed. When a job finishes (nothing left to explore from it), push it onto a stack. After DFS covers the whole graph, popping the stack gives a valid schedule. If, during DFS, an edge is followed into a job that is currently marked VISITING (still on the active recursion path, not yet finished), that is a back edge: a job depends, directly or transitively, on something that depends on it, a cycle.

Detecting cycles before scheduling. Either approach doubles as the detector: Kahn's algorithm reports a cycle implicitly by producing a short schedule (fewer jobs output than exist), and can additionally report exactly WHICH jobs never reached zero, which is often the more actionable diagnostic for an operator, since it isolates the entire tangled component rather than a single edge; the DFS-based approach reports a cycle explicitly at the moment a back edge is found, and can report the SPECIFIC path forming the cycle (everything on the current recursion stack from the target of the back edge up to the source), which is often the more actionable diagnostic for debugging exactly where a circular dependency was introduced. A practical ETL (extract, transform, load) scheduler benefits from running cycle detection as a fast pre-check (either approach) BEFORE ever attempting to schedule, since discovering a cycle mid-run (after some jobs have already executed) can leave a pipeline in a partially-applied, hard-to-reason-about state.

Tie-breaking between simultaneously-runnable jobs. Once more than one job is ready at the same time (same in-degree-zero moment, or same DFS-finish layer), the base algorithms are silent on which one to prefer, and several policies are reasonable depending on what the scheduler is actually optimizing for:

• Priority or SLA-driven: run the job with the tightest downstream deadline or highest declared business priority first.
• Shortest-job-first: run the job with the smallest estimated runtime first, maximizing throughput by keeping the pipeline of ready jobs flowing.
• Resource-aware: prefer whichever ready job best fits currently available cluster capacity, avoiding a resource-heavy job blocking several small ones behind it.
• Deterministic/reproducible: break ties by a stable rule (job id, or creation timestamp) purely so the SAME graph always produces the SAME schedule, which matters for debugging and for reproducible test fixtures even when no other priority signal applies.
• Weighted combination: a real production scheduler often combines several of these (a priority queue keyed on a composite score of SLA urgency, estimated runtime, and downstream fan-out) rather than picking exactly one rule.

Worked example

Four ETL jobs: ingest (no dependencies), clean (depends on ingest), enrich (depends on ingest), load (depends on both clean and enrich).

Kahn's algorithm: in-degrees start at ingest=0, clean=1, enrich=1, load=2. Pop ingest, decrement clean and enrich to 0 simultaneously, both now ready, a tie. Whichever tie-break policy is chosen decides whether clean or enrich is scheduled first; either order is valid with respect to the dependency graph itself, since neither depends on the other. Pop the second of the pair, decrement load to 0. Pop load last. Final schedule respects every dependency regardless of how the clean/enrich tie was broken.

If a fifth job reload_ingest were mistakenly declared to depend on load while ingest was ALSO mistakenly declared to depend on reload_ingest, that creates the cycle ingest -> clean -> load -> reload_ingest -> ingest (equally via enrich instead of clean). Running Kahn's algorithm on this exact graph (verified by execution, not just described): in-degrees become ingest=1 (a NEW incoming edge from reload_ingest, where before it was the only in-degree-0 job), clean=1, enrich=1, load=2, reload_ingest=1. Because ingest itself picked up an incoming edge, NONE of the five jobs starts at in-degree zero, so the seed queue is empty and Kahn's algorithm outputs a 0-job schedule, not 4. This is a sharper failure than 'the cycle's own members get excluded': a single mistaken edge back to a widely-depended-upon root job pulls the ENTIRE pipeline into the cycle, including jobs (clean, enrich) that are not themselves part of any circular reasoning, purely because they transitively depend on ingest, and ingest is now unreachable at in-degree zero. The operational lesson is stronger than the original framing suggested: a cyclic edge added anywhere upstream in the graph can silently block scheduling of the WHOLE DAG, not just the jobs directly involved in the cycle, which is exactly why running detection as a pre-check (see below) matters even more than it would if cycles only ever affected their own local neighborhood.

Trade-offs and pitfalls

• Common mistake: treating "a topological order exists" and "there is only one reasonable order" as the same thing. As the clean/enrich tie shows, most real DAGs have several jobs ready at once, and shipping a scheduler with no explicit, documented tie-break policy means the schedule's exact order becomes an accident of implementation detail (dict iteration order, queue insertion order) rather than a deliberate choice.
• Common mistake: discovering a cycle only after some jobs in the tangled component have already partially executed, because cycle detection was folded into the scheduling loop itself rather than run as a separate pre-check. Running detection first, and refusing to schedule anything until the whole graph passes, avoids ever having to reason about a half-applied ETL run.
• Kahn's algorithm's diagnostic advantage: naming the whole set of jobs that never reached zero pinpoints the tangled component at a glance, useful when a cycle might span many jobs across an unfamiliar dependency graph.
• DFS's diagnostic advantage: naming the exact back edge and recursion-stack path pinpoints precisely which two jobs' dependency declaration is the immediate culprit, useful when the goal is "which line of configuration do I need to fix."