Lyft Backend Developer (Entry Level) Interview Preparation Guide

Direct answer. A good error schema separates three concerns that a single "message" string conflates: a stable, machine-readable code a client can branch on programmatically, a human-readable message for logs and debugging, and enough structured detail (which field, what was wrong with it) for a UI to show something more useful than a generic failure.

A concrete shape.

{
  "error": {
    "code": "VALIDATION_ERROR",
    "message": "Request failed validation.",
    "retryable": false,
    "request_id": "req_8f2a1c",
    "details": [
      { "field": "email", "issue": "must be a valid email address" },
      { "field": "quantity", "issue": "must be greater than 0" }
    ]
  }
}

• code: a stable string a client's error-handling logic can switch on; unlike the HTTP status code alone, it can distinguish "insufficient funds" from "card declined" even though both might return the same 402.
• message: for humans (logs, a developer reading a support ticket), never the primary thing client CODE should branch on, since it is free to change wording without that being a breaking change.
• request_id: a correlation id the client can hand back to support, letting you find the exact server-side log line for this request instantly instead of searching by timestamp and endpoint.
• details: field-level validation information for a form UI to highlight the specific inputs that were wrong.

Client response vs. logs. The client response should NEVER include a stack trace, an internal service name, a raw database error message, or any other detail that reveals your system's internals; that information belongs only in your server-side logs, correlated by the same request_id, so an engineer investigating a support ticket can look up the full internal detail without ever exposing it to the caller.

Retryable vs. not. A retryable boolean (or deriving retryability from the error code via a documented mapping) tells the client whether blindly retrying the exact same request is safe and potentially successful (a transient 503) versus pointless or actively harmful (a 400 validation error, which will fail identically on every retry until the request itself changes). Without this signal, clients either retry everything (wasting calls on errors that can never succeed) or retry nothing (giving up on transient failures a simple retry would have fixed).

Trade-offs and pitfalls. The most common mistake is putting the human message where client code actually parses it, so a later, purely cosmetic wording change ("Invalid email" to "Please provide a valid email") silently breaks any client that was doing string-matching against the message instead of the code.

Direct answer

At $\alpha = 0.05$ (the significance threshold: the largest probability of a false alarm,
concluding there is a real difference when there actually isn't one, that we're willing to
accept), this A/B sample does not show statistically significant evidence that Server B is
faster: the observed 2ms difference has a t-statistic of about 1.81 (a t-statistic measures
how many standard errors the observed gap sits away from zero; a value close to zero looks
like ordinary noise) on about 95 degrees of freedom (a parameter, driven here by the sample
sizes and variances, used to pick the right threshold for this test), below the roughly 1.99
critical value (the threshold the t-statistic would need to exceed, in either direction, to
count as significant at this alpha), and the 95% confidence interval for the difference (a
range that, if you repeated this experiment many times, would contain the true average
difference about 95% of the time) includes zero.

Structured elaboration

A t-test is a standard way to check whether the gap between two group averages is larger
than you would expect from ordinary sampling noise alone, given how much the underlying data
varies. Because the two samples here have different standard deviations (5ms versus 6ms), use
Welch's t-test rather than the pooled-variance (Student's) t-test, which assumes equal
variances. Welch's test does not require that assumption and is the safer default
whenever sample variances differ, which they do here.

Degrees of freedom use the Welch-Satterthwaite approximation (a correction that accounts for
the two groups having different variances) rather than the simple
$n_A + n_B - 2$:

The 95% confidence interval for the mean difference uses the same standard error and
the critical value from the $t$ distribution at that degrees of freedom:

Required sample size per group to detect a difference $\Delta$ with significance level
$\alpha$ and power $1-\beta$ (power is the probability the test correctly detects a real
difference of size $\Delta$, if one truly exists; 0.8 means an 80% chance of catching a
real effect instead of missing it), given an assumed pooled standard deviation $\sigma$:

Worked example

$SE$ above is the standard error: an estimate of how much the difference between the two
sample means would bounce around if this experiment were repeated many times.

With $df \approx 95$, the two-sided critical value at $\alpha = 0.05$ is
$t_{crit} \approx 1.985$, and since $|t| = 1.81 < 1.985$, we fail to reject the null
hypothesis (the default assumption of no real difference between the two servers' mean
latency, which we only abandon if the data gives strong enough evidence against it) that the
two servers have equal mean latency; this corresponds to a p-value of about 0.07 (the
probability of seeing a gap at least this large purely by chance if the null hypothesis were
actually true). The 95% confidence interval for the difference is:

The interval spans zero, consistent with "not significant": Server B might be faster,
slower, or the same, and 50 samples per server was not enough to tell apart from noise.

One choice drives that verdict and it should be stated rather than assumed, because the
question asks a DIRECTIONAL thing ("is Server B faster") while the test above is
two-sided. A two-sided test splits the 5% false-alarm budget across both tails, so it
asks "are these two different" and needs $|t| > 1.985$. A one-sided test spends the
whole 5% on the "B is faster" tail, needs only $t > 1.661$ at the same degrees of
freedom, and on these exact numbers returns a one-sided p of about 0.037 against the
two-sided 0.073: the same data, the same alpha, and the opposite conclusion. I report it
as not significant because the direction was not fixed before the data was seen, and
switching to the one-sided test after noticing which way the gap fell is how a nominal 5%
false-alarm rate quietly becomes 10%. The defensible practice is to pre-register the
direction (and the sample size) before collecting, and to default to two-sided when you
did not. This is worth surfacing rather than burying, because a reviewer who assumed a
one-sided test would read this same table as a win.

For the required sample size to reliably detect a 1ms difference at 80% power
($z_{\alpha/2} = 1.96$, the cutoff value from the standard normal distribution for a
two-sided test at $\alpha = 0.05$; $z_\beta = 0.84$, the cutoff value corresponding to 80%
power; both are looked up from a standard normal table or quantile function, not derived
here, pooled $\sigma \approx 5.5$ms):

Round up to 475 samples per server (roughly 9-10x the current sample of 50), which
explains directly why the current experiment came back inconclusive: it was
underpowered for a difference this small.

Trade-offs & pitfalls

Latency distributions are typically right-skewed, not normal, and real interest is
often in a tail percentile (p95/p99) rather than the mean. This t-test framework is the
right first tool for a mean comparison, but the identical sample-size and rigor logic
applies to a percentile comparison too, for example an experiment framed as "did a
change improve p95 latency by 10%": there, a parametric t-test on the mean is the wrong
tool, and a bootstrap or permutation test on the percentile difference is preferred (these
resample the data itself to estimate variability, rather than assuming it follows a
particular curve like the normal or t-distribution), since it makes no distributional
assumption and directly targets the metric of interest. Also watch for non-independence:
back-to-back latency samples from the same server under sustained load are often
autocorrelated (a slow request tends to follow another slow request), which violates the
i.i.d. assumption (independent and identically distributed: each sample drawn independently
from the same underlying distribution) behind both the t-test and the sample-size formula and
can make a result look more significant than it really is; spacing samples out or using a
block-bootstrap (a resampling method that keeps runs of consecutive samples together, so it
captures that correlation instead of assuming independence) corrects for this.

Direct answer

Use two pointers that both start at the head. slow moves one node per loop round and fast moves two. When fast can no longer move two steps, slow is standing on the middle. That is one trip over the list (a pass means one walk from the head to the end; each repetition of the loop is a round), O(n) time and O(1) extra space. For an even-length list I return the SECOND of the two middle nodes (index n // 2, counting from 0; // is whole-number division that drops any remainder, so 5 // 2 is 2 and 6 // 2 is 3), which is what the loop while fast and fast.next produces; the first middle (index (n - 1) // 2, which is 2 for 5 nodes and 2 for 6 nodes) needs a slightly earlier stop condition.

The idea in plain words

A singly linked list gives you no way to jump to position n // 2 because you do not know n and there is no index. The usual first answer is two passes over the list: count the nodes, then walk n // 2 steps. The one-pass trick is a speed difference. If one pointer moves twice as fast as the other, then at the moment the fast one reaches the end, the slow one has covered half the distance, so it is at the middle.

Why the pointers land where they do

Concretely, with the 5 nodes 1 2 3 4 5 (indexes 0 to 4): after 2 rounds slow is at index 2 and fast at index 4, the last node, so the loop stops and slow is on the 3. The general version follows. After k rounds, slow has moved k nodes (it is at index k) and fast has moved 2k nodes (index 2k).

• Odd length n = 2k + 1: after k rounds fast is at index 2k, the last node, and fast.next is None. The loop stops with slow at index k, the exact middle.
• Even length n = 2k: after k - 1 rounds fast is at index 2k - 2 and the last node (index 2k - 1) is still after it, so fast.next exists and the loop runs once more. After k rounds fast is None (it stepped past the end) and slow is at index k = n / 2, the second middle.

So the loop runs exactly n // 2 times and returns index n // 2.

Which middle to return for an even length, and why

I commit to the second middle (index n // 2) as the default, for two reasons: it is exactly what the simplest loop condition returns, and it equals nodes[len(nodes) // 2], the answer you would get by indexing into an array, so it is easy to explain and test. The first middle is the better choice when you need to CUT the list in half, as in merge sort of a list or a palindrome check: there slow must stop at the last node of the first half so you can set slow.next = None. The last lines of the program show it on 1 -> 2 -> 3 -> 4: cutting after the first middle gives two halves of 2 and 2, cutting after the second middle gives 3 and 1, and a palindrome check or a merge sort wants the balanced split. The code ships both. The first-middle version stops one round earlier by testing fast.next and fast.next.next instead.

Code

import random


class ListNode:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def build(values):
    head = None
    for v in reversed(values):
        head = ListNode(v, head)
    return head


def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def middle_second(head):
    """Second middle on even length (index n // 2)."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def middle_first(head):
    """First middle on even length (index (n - 1) // 2)."""
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow


def show_middle(values):
    """Print slow and fast positions after each loop round, then the answer."""
    head = build(values)
    nodes = to_list(head)
    print("list:", " -> ".join(map(str, nodes)), "-> None")
    slow = fast = head
    step = 0
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        step += 1
        print(f"  round {step}: slow at {slow.val}, fast at {fast.val if fast else None}")
    print(f"  returns {slow.val}   (first middle would be {middle_first(head).val})")


show_middle([1, 2, 3, 4, 5])
show_middle([1, 2, 3, 4, 5, 6])
show_middle([7, 8])
show_middle([9])

# Why the first middle is the one to use for cutting a list in half
def cut_after(head, node):
    """Detach everything after node; return the second half."""
    second, node.next = node.next, None
    return second


for name, find_middle in (("first middle ", middle_first), ("second middle", middle_second)):
    head = build([1, 2, 3, 4])
    second = cut_after(head, find_middle(head))
    print(f"cut after the {name}: {to_list(head)} and {to_list(second)}")

# Check against indexing, for every length from 1 to 40
rng = random.Random(3)
for n in range(1, 41):
    values = [rng.randint(0, 99) for _ in range(n)]
    head = build(values)
    node = middle_second(head)
    # walk from the head to find the position of the returned node
    pos, cur = 0, head
    while cur is not node:
        cur, pos = cur.next, pos + 1
    assert pos == n // 2
    first = middle_first(head)
    pos, cur = 0, head
    while cur is not first:
        cur, pos = cur.next, pos + 1
    assert pos == (n - 1) // 2
print("lengths 1 to 40: second middle is index n // 2, first middle is index (n - 1) // 2")

Output:

list: 1 -> 2 -> 3 -> 4 -> 5 -> None
  round 1: slow at 2, fast at 3
  round 2: slow at 3, fast at 5
  returns 3   (first middle would be 3)
list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
  round 1: slow at 2, fast at 3
  round 2: slow at 3, fast at 5
  round 3: slow at 4, fast at None
  returns 4   (first middle would be 3)
list: 7 -> 8 -> None
  round 1: slow at 8, fast at None
  returns 8   (first middle would be 7)
list: 9 -> None
  returns 9   (first middle would be 9)
cut after the first middle : [1, 2] and [3, 4]
cut after the second middle: [1, 2, 3] and [4]
lengths 1 to 40: second middle is index n // 2, first middle is index (n - 1) // 2

Worked trace

Both pointers start on the head. For 1 -> 2 -> 3 -> 4 -> 5 -> None the printout shows round 1 with slow at 2 and fast at 3, round 2 with slow at 3 and fast at 5. fast.next is now None, so the loop stops and returns 3. For 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None there is a third round: slow moves to 4 and fast steps off the end to None, so the function returns 4 (the second middle) while the first-middle function returns 3. The two-node list 7 -> 8 takes one round and returns 8. The one-node list returns its only node after zero rounds. The two lines before the last show the cut. The final line is an assertion run over every length from 1 to 40, confirming the index formulas.

Complexity

• Time O(n): fast visits about every node once; the loop runs n // 2 rounds.
• Space O(1): two pointers, no recursion and no array.

Edge cases

• Empty list: middle_second(None) returns None (the loop test fast and fast.next is false at once). middle_first(None) would raise AttributeError because it reads fast.next; guard with if head is None: return None when empty input is possible.
• One node: both functions return it.
• Two nodes: second middle is the tail node, first middle is the head.
• Very long lists: the code is iterative, so Python's recursion limit (1000 frames by default) is not involved.

Common mistakes

• Writing while fast.next and fast.next.next and expecting the second middle: that returns the first middle for even lengths.
• Writing while fast.next: with fast = fast.next.next: on an even-length list fast becomes None, and the next test reads None.next, which raises AttributeError. The shipped conditions check fast before reading fast.next.
• Counting first, then walking: correct, but two passes over the list and it does not meet a "one pass" requirement.

Running the code

python middle_node.py

Python 3.12, standard library only.

Direct answer

Rabin-Karp finds a pattern inside a text by hashing the pattern once, then sliding a "rolling hash"
across the text one character at a time, updating that hash in O(1) per step (rather than
recomputing it from scratch), and only falling back to an actual character-by-character comparison
when the rolling hash matches the pattern's hash, which guards against the rare case where two
different substrings happen to hash the same.

Structured elaboration

Why a rolling hash, not a fresh hash per window. Treating the text as a sequence of overlapping
windows and hashing each one from scratch costs O(m) per window (m = pattern length), O(nm) overall,
no better than brute force. A rolling hash instead computes the FIRST window's hash directly, then
updates it for each subsequent window in O(1): remove the outgoing character's weighted contribution,
shift, add the incoming character, all via simple modular arithmetic, giving O(n) total work across
the whole text (plus O(m) for the pattern itself), a real asymptotic improvement.

Why you still verify on a hash match, never trust it alone. A hash is a many-to-one mapping,
different substrings CAN produce the same modular hash value purely by chance (a hash collision).
Skipping the verification step and trusting a hash match as a real match would make the algorithm
occasionally, silently WRONG, reporting a match where none exists. Verifying with an actual string
comparison whenever the hash matches keeps the algorithm always correct; it only affects how often
you pay that verification cost, which is why the algorithm's average-case running time depends on
using a large enough modulus to keep spurious hash collisions rare.

Worked example

def rabin_karp_search(text, pattern, base=256, mod=1_000_000_007):
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    high_order = pow(base, m - 1, mod)

    pattern_hash = window_hash = 0
    for i in range(m):
        pattern_hash = (pattern_hash * base + ord(pattern[i])) % mod
        window_hash = (window_hash * base + ord(text[i])) % mod

    matches = []
    for i in range(n - m + 1):
        if window_hash == pattern_hash and text[i:i+m] == pattern:   # verify, don't trust the hash alone
            matches.append(i)
        if i < n - m:
            window_hash = (window_hash - ord(text[i]) * high_order) % mod
            window_hash = (window_hash * base + ord(text[i + m])) % mod
            window_hash %= mod
    return matches

text, pattern = "abracadabra_abra_cadabra", "abra"
found = rabin_karp_search(text, pattern)
expected = [i for i in range(len(text) - len(pattern) + 1) if text[i:i+len(pattern)] == pattern]
print("found:", found)
print("expected (brute force):", expected)
print("match:", found == expected)

# deliberately use a tiny modulus to force frequent hash collisions, and confirm
# the verification step still keeps the result correct despite them.
tiny_mod_matches = rabin_karp_search(text, pattern, base=256, mod=97)
print("tiny-modulus run (heavy collisions expected) still correct:", tiny_mod_matches == expected)


def count_candidates(text, pattern, base, mod):
    """Counts how often a hash match triggers verification, a proxy for collision-driven overhead."""
    n, m = len(text), len(pattern)
    high_order = pow(base, m - 1, mod)
    p_hash = w_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        w_hash = (w_hash * base + ord(text[i])) % mod
    candidates = 0
    for i in range(n - m + 1):
        if w_hash == p_hash:
            candidates += 1
        if i < n - m:
            w_hash = (w_hash - ord(text[i]) * high_order) % mod
            w_hash = (w_hash * base + ord(text[i + m])) % mod
    return candidates


def count_double_hash_candidates(text, pattern, base1, mod1, base2, mod2):
    """Double hashing: require agreement of TWO independent (base, modulus) rolling hashes
    before calling a position a candidate."""
    n, m = len(text), len(pattern)

    def hashes(mod, base):
        high_order = pow(base, m - 1, mod)
        p_hash = w_hash = 0
        for i in range(m):
            p_hash = (p_hash * base + ord(pattern[i])) % mod
            w_hash = (w_hash * base + ord(text[i])) % mod
        return p_hash, w_hash, high_order

    p1, w1, ho1 = hashes(mod1, base1)
    p2, w2, ho2 = hashes(mod2, base2)
    candidates = 0
    for i in range(n - m + 1):
        if w1 == p1 and w2 == p2:
            candidates += 1
        if i < n - m:
            w1 = (w1 - ord(text[i]) * ho1) % mod1
            w1 = (w1 * base1 + ord(text[i + m])) % mod1
            w2 = (w2 - ord(text[i]) * ho2) % mod2
            w2 = (w2 * base2 + ord(text[i + m])) % mod2
    return candidates


import random
random.seed(42)
long_text = "".join(random.choice("abcd") for _ in range(2000))
long_pattern = "abcd"
true_count = sum(
    1 for i in range(len(long_text) - len(long_pattern) + 1)
    if long_text[i:i + len(long_pattern)] == long_pattern
)
single_candidates = count_candidates(long_text, long_pattern, base=256, mod=13)
double_candidates = count_double_hash_candidates(long_text, long_pattern, base1=256, mod1=13, base2=257, mod2=17)
print(f"true matches in 2000-char text: {true_count}")
print(f"single small-modulus (mod=13) candidates needing verification: {single_candidates}")
print(f"double-hash (mod=13 AND mod=17) candidates needing verification: {double_candidates}")

Running this prints found: [0, 7, 12, 20], expected (brute force): [0, 7, 12, 20], match: True,
confirming correctness against a large modulus. The second run, deliberately using mod=97 (a
tiny modulus guaranteed to produce many spurious hash collisions across a 24-character text),
still prints True for tiny_mod_matches == expected, directly demonstrating that the verification
step (text[i:i+m] == pattern) is what keeps the algorithm correct EVEN when the hash itself is
colliding constantly, the hash is only ever an optimization for which positions to check first, never
a substitute for actually checking.

Double hashing as a collision-probability mitigation. A single modulus makes the odds of a
spurious hash match roughly 1/mod under a reasonable hash function, so a small modulus makes
verification-triggering false matches common, exactly what the mod=97 run above demonstrates.
Double hashing computes two INDEPENDENT rolling hashes (different base/modulus pairs) in parallel
and only calls a position a candidate when BOTH agree, an event with probability roughly
1/(mod1 * mod2), far rarer than either hash colliding alone. Over a longer 2000-character random
text with a 4-character pattern (long_text/long_pattern above, 8 true occurrences), a single
small modulus (mod=13) produces 163 candidate positions needing verification (only 8 of them
real), while requiring agreement of two independent small moduli (mod=13 AND mod=17) cuts that
to 20 candidates, still a superset of the 8 true matches (no false negatives introduced), but
roughly 8x fewer spurious verification triggers than the single small modulus alone. Double
hashing never removes the need to verify on a match, two independent hashes can still agree by
chance, it only makes that case rarer, which is why production implementations reach for either
one sufficiently large modulus (as pattern_hash/window_hash above use) or two independent
smaller ones, rather than a single small one.

Trade-offs and pitfalls

Extending this to searching for MULTIPLE distinct patterns simultaneously is a natural next step:
instead of comparing the rolling hash against one target pattern_hash, maintain a hash map from
hash value -> list of pattern indices with that hash, letting you check candidate matches for many
patterns in one pass over the text, still verifying each candidate to rule out both ordinary hash
collisions AND genuine hash VALUE collisions between two different target patterns that happen to
share a hash. The main implementation pitfall is using a modulus too small for the expected text
size, raising the real collision rate to the point where the "rare fallback to verification" case
stops being rare, silently degrading the algorithm's average-case speed back toward brute force even
though it remains CORRECT throughout, since correctness comes from the verification step, only speed
depends on collisions staying rare.

Direct answer

Keep a stalled dependency peer-to-peer as long as direct conversation is still making progress. Escalate when you hit a concrete trigger: a scope change that neither side can unilaterally absorb, genuinely conflicting priorities that only someone with visibility into both roadmaps can arbitrate, or a hard deadline-driven blocker where peer-to-peer conversation has already stalled.

Framework

Default: work it peer-to-peer. Most stalls are under-communication or unclear ownership, and a direct conversation or a short written proposal usually unsticks them without anyone else getting involved.

Concrete triggers to escalate.

• Scope change: the fix now requires work neither team budgeted for, and only a manager can reprioritize that.
• Conflicting priorities: both sides are acting rationally from their own team's goals, and the trade-off needs someone with visibility into both roadmaps to arbitrate.
• Hard blocker with a deadline: a fixed external date is genuinely at risk, and peer-to-peer conversation has already stalled past a reasonable window, for example no movement after two direct attempts over several days.
• Repeated pattern: the same kind of stall keeps recurring with the same team, which means the real issue is the working relationship or process, not this one dependency.

What to bring when you escalate. A short brief: what's blocked, what you've already tried peer-to-peer, the realistic options and their trade-offs, and the specific decision you need.

Worked example (applying the criteria)

Situation: your team's deliverable needs a schema change from another team that they've deprioritized for two weeks despite two direct requests.
Applying the criteria: this isn't just a communication gap, direct conversation was already tried twice with no movement. It's a conflicting-priorities case, the other team's roadmap has no room for this without reprioritizing something else, combined with a hard blocker, a fixed external deadline in three weeks that this schema change sits on the critical path for (meaning if this dependency slips, the final deadline slips by the same amount, unlike a dependency with buffer to absorb delay).
Action: escalated to the shared manager with a one-page brief covering what's blocked, the two peer-to-peer attempts and their outcome, and two options: the other team reprioritizes one sprint of work, or your team ships a temporary workaround with known limitations, along with the deadline risk if neither happens within the week.
Result: the shared manager reprioritized one sprint item, unblocking the schema change with two weeks to spare before the deadline. Both teams also agreed to flag scope-affecting asks earlier next time, so the same dependency doesn't reach this point again.

Trade-offs and pitfalls

• Escalating too early over normal friction burns trust and reads as an inability to work horizontally.
• Escalating too late, repeatedly trying peer-to-peer past the point it's actually working, puts the deadline at real risk and looks like poor judgment in hindsight.
• A vague escalation with no options and no specific ask wastes the leader's time compared with a brief that names the decision needed.

Direct answer

Try IPv4 first: split on ., require exactly 4 parts, and each part must be all digits, at most 255, with no leading zero unless the part is exactly "0". If that fails, try IPv6: split on :, handle the :: zero-compression shorthand (which can appear at most once), require the expanded form to have exactly 8 groups, and each group must be 1 to 4 hexadecimal digits. Both formats have real edge-case density, which is exactly why this question is a good filter for carefulness rather than algorithmic cleverness.

Approach: IPv4

1. Split on .; reject unless there are exactly 4 parts.
2. Each part must be all-digit (test against /^[0-9]+$/), which also rejects a sign character or empty part.
3. Reject a leading zero unless the part is exactly "0" (i.e. "0" is valid, "00" and "01" are not).
4. Reject if the numeric value exceeds 255.

Approach: IPv6

1. :: can appear at most once; more than one is invalid (the shorthand would be ambiguous about how many zero groups it represents).
2. If :: is present, split the string into a "head" and "tail" around it, split each side on : (an empty side yields zero groups, not one empty-string group), and the total number of explicit groups on both sides together must be strictly less than 8 (the whole point of :: is to stand in for at least one omitted group).
3. If :: is absent, splitting on : must yield exactly 8 groups.
4. Every resulting group must be 1 to 4 hexadecimal digits.

Complexity

Both: O(L) where L is the length of the input string (each character is inspected a constant number of times across the split and per-group checks).

Edge cases

• IPv4 with a leading zero ("1.1.1.01"): rejected under the standard interview convention, discussed further below.
• IPv6 with the :: shorthand at the very start or end ("::1", "1::"), or standing alone for all-zero ("::"): all valid, and the head/tail split correctly produces zero groups on the empty side.
• A string that looks numeric but isn't a valid address in either format (e.g. too many or too few groups): correctly rejected by both checks, so the overall answer is "neither."

function isValidIPv4(s) {
  const parts = s.split(".");
  if (parts.length !== 4) return false;
  for (const p of parts) {
    if (!/^[0-9]+$/.test(p)) return false;
    if (p.length > 1 && p[0] === "0") return false;
    if (parseInt(p, 10) > 255) return false;
  }
  return true;
}

function isValidIPv6(s) {
  if ((s.match(/::/g) || []).length > 1) return false;
  let parts;
  if (s.includes("::")) {
    const [head, tail] = s.split("::");
    const headParts = head ? head.split(":") : [];
    const tailParts = tail ? tail.split(":") : [];
    if (headParts.length + tailParts.length >= 8) return false;
    parts = headParts.concat(tailParts);
  } else {
    parts = s.split(":");
    if (parts.length !== 8) return false;
  }
  for (const p of parts) {
    if (p.length < 1 || p.length > 4) return false;
    if (!/^[0-9a-fA-F]+$/.test(p)) return false;
  }
  return true;
}

const cases = ["172.16.254.1", "256.1.1.1", "1.1.1.1.1", "192.168.0.1",
  "2001:0db8:85a3:0000:0000:8a2e:0370:7334", "2001:db8::8a2e:370:7334", "::1", "::"];
for (const c of cases) {
  console.log(`${c} -> (${isValidIPv4(c)}, ${isValidIPv6(c)})`);
}

Output (executed, node s59_ip_validate.js):

172.16.254.1 -> (true, false)
256.1.1.1 -> (false, false)
1.1.1.1.1 -> (false, false)
192.168.0.1 -> (true, false)
2001:0db8:85a3:0000:0000:8a2e:0370:7334 -> (false, true)
2001:db8::8a2e:370:7334 -> (false, true)
::1 -> (false, true)
:: -> (false, true)

Each IPv4-shaped input is correctly recognized only as IPv4 ((true, false)), each IPv6-shaped input only as IPv6 ((false, true)), and the malformed 256.1.1.1 / 1.1.1.1.1 cases are correctly rejected as neither.

Trade-offs and pitfalls, grounded against a real parser

I checked this implementation's verdicts against Node's built-in net.isIP() (a mature, spec-driven parser shipped with the runtime this answer targets), as ground truth, over a wider test set that included two intentionally awkward cases. It surfaced one genuine, useful disagreement rather than confirming everything blindly:

const net = require("net");
console.log("1.1.1.01 -> mine:", isValidIPv4("1.1.1.01"), "net.isIP:", net.isIP("1.1.1.01"));
console.log("02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine:", isValidIPv6("02001:0db8:85a3:0000:0000:8a2e:0370:7334"), "net.isIP:", net.isIP("02001:0db8:85a3:0000:0000:8a2e:0370:7334"));
console.log("::ffff:1.2.3.4 -> mine:", isValidIPv6("::ffff:1.2.3.4"), "net.isIP:", net.isIP("::ffff:1.2.3.4"));

Output (executed, node s59_parser_check.js):

1.1.1.01 -> mine: false net.isIP: 0
02001:0db8:85a3:0000:0000:8a2e:0370:7334 -> mine: false net.isIP: 0
::ffff:1.2.3.4 -> mine: false net.isIP: 6

• Leading zero and the oversized hex group: no disagreement here, and that itself is worth confirming rather than assuming. net.isIP("1.1.1.01") returns 0 (invalid), agreeing with this implementation's rejection; the same is true for the 5-hex-digit IPv6 group. Leading-zero rejection is a deliberate, security-motivated convention: leading zeros in IPv4 octets are genuinely ambiguous across tools (some historically parsed them as octal, so "010" meant 8, not 10), and that exact ambiguity was serious enough that Python's own standard-library ipaddress module was patched (CVE-2021-29921, fixed in Python 3.8.12 / 3.9.5 / 3.10.0a7) to reject any leading-zero octet outright rather than guess, precisely because parser disagreement on this point had been used to bypass IP-based access controls elsewhere. Node's net.isIP happens to already enforce the strict reading here, so this specific check doesn't surface a gap, but it would be a mistake to conclude every runtime's built-in parser is this strict; confirm it for whichever one you actually ship against.
• A real disagreement: "::ffff:1.2.3.4" (an IPv4-mapped IPv6 address, RFC 4291 section 2.5.5.2) is accepted by net.isIP as valid IPv6 (6), but this implementation rejects it (false). The reason is structural, not a bug in the sense of violating the question's own spec: the question defines IPv6 validity as "eight groups of 1-4 hex digits, allowing shorthand :: once," and "1.2.3.4" is neither a hex group nor handled by the ::-splitting logic, so it correctly falls out of scope for THIS definition. A production-grade validator that needs to accept the full real-world IPv6 address space would need an explicit extra branch recognizing a trailing dotted-quad segment. This is a good example of why "matches a mature real parser" and "matches the question's stated spec" are two different bars, and a candidate should be explicit about which one their implementation is targeting.
• A common bug in the IPv6 head/tail split: using head.split(":") unconditionally, without the head ? ... : [] guard, on an empty head (e.g. for "::1") produces [""] (one empty-string "group") instead of [] (zero groups), which then incorrectly fails the later 1-to-4-hex-digit check on that phantom empty group. This applies identically in JavaScript and in a straightforward Python port of the same logic.

Direct answer

For an enterprise rich-text editor that must support offline edits and multi-region users, I recommend a CRDT (conflict-free replicated data type) implemented with a mature library such as Yjs or Automerge, paired with a server that still authenticates, sequences and stores every update so the audit log is authoritative. OT (operational transformation) is proven for online, single-region editing with a central server, but long offline branches and cross-region users are exactly where it becomes expensive and fragile. The main costs of the CRDT choice are metadata growth and harder server-side validation, and both are manageable.

The two ideas in plain terms

• OT: each edit is a position-based operation such as "insert 's' at index 3". When two edits happen concurrently, a central server picks an order and transforms the later one so it still means what its author intended given the earlier one.
• CRDT: each inserted character (or run of characters) gets a unique ID, and an insert says "put this after item X" rather than "at index 3". Because edits reference IDs, not positions, replicas can apply them in any order and still converge. This property is called strong eventual consistency: any two replicas that have received the same set of updates are identical.

A traced example

The document is cat. Concurrently, Alice appends s (intending cats) and Bob deletes the c.

• OT: the server orders Bob's delete(0) first. Alice's insert(3, 's') must be transformed: one character before position 3 was deleted, so it becomes insert(2, 's'). Server result: cat then at then ats. On Alice's screen she already has cats; Bob's delete(0) is at a position before her insert, so it is unchanged, giving ats. Both converge on ats, but only because the transform function was right.
• CRDT: Alice's insert says "put s after the item whose ID is t1" (the ID the original t received when it was typed). Bob's delete marks item c as deleted (a tombstone). Applied in either order, the result is ats, with no transformation logic.

Comparison on the six asked axes

How the enterprise requirements tip it

• Offline edits: a user edits on a flight for 6 hours. With a CRDT, the client merges 6 hours of updates in one exchange. With OT, the server must transform every one of those operations against everything that changed meanwhile, and a bug in any transform pair corrupts the document.
• Multi-region users: a CRDT lets each region run a local relay that exchanges updates with other regions, so typing latency stays local. OT needs one authoritative server per document, so the far-away user always pays the cross-region round trip on acknowledgement.
• Audit logs: both can satisfy them, and the CRDT choice does not mean giving up a central log. The server authenticates each connection, stamps each incoming update with the verified user ID, server time and a per-document sequence number, and appends it to an immutable log. That log is replayable to reconstruct any past state. OT gets this log for free as its operation history; with a CRDT you build it deliberately.

Recommendation, and what would flip it

Choose a CRDT library, with a server that sequences and records every update. Enforce permissions at connect time and on every received update before relaying it.

It would flip to OT if the product were online-only and single-region, the team already ran a mature OT stack, or the document model needed strict server-enforced invariants (for example "this cell must always hold a valid number"). A CRDT cannot simply refuse an update that clients have already applied; it must issue a compensating edit, whereas an OT server can reject the operation before anyone sees it.

Pitfalls

• Assuming convergence means no conflicts. Two people retyping the same sentence converge to one merged sentence that may read badly. The UI still needs author highlights and easy revert.
• Never compacting. Tombstones and update history grow without bound; schedule snapshots and let the library garbage-collect where no offline replica can still need the history.
• Writing your own CRDT or OT for rich text. Both are research-grade problems; use a maintained library unless editing is your core product and you can staff it.

The idea in plain words

A binary search tree (BST) keeps smaller keys to the left and larger keys to the right, so an in-order walk (left subtree, node, right subtree) visits keys in sorted order. Sorted inserts turn the tree into a chain, so a lookup walks about half of the chain on average. The fix needs one insight. Many different trees hold the same sorted keys: the keys 1 to 7 can form a chain with root 1 (height 6) or a tree with root 4 (height 2), and both read 1, 2, 3, 4, 5, 6, 7 in order. So a BST is fully determined by its in-order sequence plus the choice of root for each range of keys, and if you pick the middle element as the root of every range, the height is as small as possible. The rebuild is therefore: flatten the tree into a sorted list, then rebuild by repeatedly taking the middle.

Heights here count edges: the empty tree has height -1 and a single node has height 0.

Brute force and why it is not enough

Re-inserting the sorted keys one by one into a fresh tree reproduces the chain (the same sorted order that caused the problem) and costs O(n^2). Inserting in a shuffled order gives an average node depth that grows like 1.39 log2 n (the leading term of the textbook result for random insertion orders), but with no guarantee for a given order; the checking program below measures it. Picking the middle element each time gives the guaranteed minimum height, floor(log2 n), in O(n).

Approach

1. Walk the tree in order with an explicit stack (not recursion, because a chain of 5000 nodes exceeds CPython's default limit of 1000 frames) and collect the Node objects themselves, not only their keys.
2. Recursively build over the half-open index range [lo, hi) (it includes index lo but not index hi, so [0,7) is indexes 0 to 6 and [2,2) is empty): the middle node becomes the root, [lo, mid) builds its left subtree, [mid+1, hi) its right. The +1 skips the middle itself, and the two ranges differ in size by at most one, which is why neither side can be much taller than the other. This recursion is only about log2 n frames deep, so it is safe at any size.
3. Reusing the same Node objects means any extra per-node data (here payload) travels with its key and nothing needs copying. Every left and right pointer is overwritten, so no stale link survives.

Code

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


def insert(root, key, payload=None):
    """Plain BST insert (iterative, so a long chain never hits the recursion limit)."""
    node = Node(key, payload)
    if root is None:
        return node
    cur = root
    while True:
        if key < cur.key:
            if cur.left is None:
                cur.left = node
                break
            cur = cur.left
        else:
            if cur.right is None:
                cur.right = node
                break
            cur = cur.right
    return root


def height(root):
    """Height in edges: empty tree -1, single node 0. Iterative (level by level)."""
    if root is None:
        return -1
    h, level = -1, [root]
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h


def inorder_nodes(root):
    """Iterative in-order walk: returns the Node objects in ascending key order."""
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur)
        cur = cur.right
    return out


def build_balanced(nodes, lo, hi, log=None, depth=0):
    """Make nodes[lo:hi] into a tree rooted at the middle node; relinks the existing Node objects."""
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    if log is not None:
        log.append(f"{'  ' * depth}range [{lo},{hi}) -> root {nodes[mid].key}")
    node = nodes[mid]
    node.left = build_balanced(nodes, lo, mid, log, depth + 1)
    node.right = build_balanced(nodes, mid + 1, hi, log, depth + 1)
    return node


def rebalance(root, log=None):
    nodes = inorder_nodes(root)
    return build_balanced(nodes, 0, len(nodes), log)


def draw(root):
    """Sideways text drawing: right subtree on top, root at the left margin."""
    lines = []
    def walk(n, depth):
        if n is None:
            return
        walk(n.right, depth + 1)
        lines.append("    " * depth + str(n.key))
        walk(n.left, depth + 1)
    walk(root, 0)
    return "\n".join(lines)


if __name__ == "__main__":
    # Sorted inserts make a chain. Each node carries extra data (payload).
    root = None
    for k in [1, 2, 3, 4, 5, 6, 7]:
        root = insert(root, k, payload=f"user-{k}")
    print("before, height", height(root))
    print(draw(root))
    keys_before = [n.key for n in inorder_nodes(root)]
    print("sorted keys:", keys_before)
    log = []
    root = rebalance(root, log)
    print("\n".join(log))
    print("after, height", height(root))
    print(draw(root))
    print("payload kept:", [(n.key, n.payload) for n in inorder_nodes(root)][:3], "...")

    # Larger check: 5000 sorted inserts, then compare against the minimum possible height.
    big = None
    for k in range(5000):
        big = insert(big, k, payload=k * 10)
    print("chain of 5000: height", height(big))
    big = rebalance(big)
    print("rebalanced: height", height(big), "minimum possible", (5000).bit_length() - 1)
    assert [n.key for n in inorder_nodes(big)] == list(range(5000))
    assert all(n.payload == n.key * 10 for n in inorder_nodes(big))

    # A recursive in-order walk fails on the same chain (CPython default limit is 1000 frames).
    chain = None
    for k in range(5000):
        chain = insert(chain, k)
    def recursive_inorder(n, out):
        if n:
            recursive_inorder(n.left, out)
            out.append(n.key)
            recursive_inorder(n.right, out)
    try:
        recursive_inorder(chain, [])
    except RecursionError:
        print("recursive in-order on the chain: RecursionError")

Output:

before, height 6
                        7
                    6
                5
            4
        3
    2
1
sorted keys: [1, 2, 3, 4, 5, 6, 7]
range [0,7) -> root 4
  range [0,3) -> root 2
    range [0,1) -> root 1
    range [2,3) -> root 3
  range [4,7) -> root 6
    range [4,5) -> root 5
    range [6,7) -> root 7
after, height 2
        7
    6
        5
4
        3
    2
        1
payload kept: [(1, 'user-1'), (2, 'user-2'), (3, 'user-3')] ...
chain of 5000: height 4999
rebalanced: height 12 minimum possible 12
recursive in-order on the chain: RecursionError

Worked trace

The seven sorted inserts give the chain drawn first (the drawing is sideways: the right subtree is above its parent, the root is at the left margin). The log lines show which index range each call handles and which node becomes its root: [0,7) picks index 3 (key 4), then [0,3) picks key 2 and [4,7) picks key 6, and the single-element ranges finish the leaves. Height drops from 6 to 2, which is floor(log2 7). The 5000-node chain drops from 4999 to 12, equal to the minimum possible height floor(log2 5000).

Complexity

• Time: O(n). The in-order walk touches each node once, and the build creates each node's links once.
• Memory: O(n) extra. The list of n node references is the cost. The walk's stack is at most h entries (up to n on a left-leaning chain: the checking program shows 5000 entries for a 5000-node chain, next to a list of the same length), and the build recursion is O(log n). No new Node objects are allocated.
• Copying out (key, payload) pairs and allocating new nodes instead would roughly double the node memory while both trees exist; reusing the nodes avoids that.

Edge cases and common mistakes

• Empty tree: the list is empty, build_balanced returns None, and the height is -1.
• One node: returns that node with height 0.
• Duplicate keys (inserted to the right here) keep their order because the walk is in order and the build never compares keys. The checking program rebuilds 300 lists with many repeated keys and finds the same keys and arrival tags in the same order.
• Using a recursive in-order walk: it works on a balanced tree and raises RecursionError on the chain, as the last output line shows.
• Rebuilding from keys only: any payload attached to a node is silently lost.
• Choosing mid = lo + (hi - lo) // 2 or (lo + hi) // 2 are both fine in Python; in a fixed-width language the sum lo + hi can overflow, so use the first form.
• Forgetting to reset left and right on a reused node: the old links keep pointing at nodes that now sit elsewhere, so a walk reaches nodes a second time. The last two lines of the checking program show 0 repeats with the reset and 3 repeats without it, for seven keys.

Checking the claims and one rotation

The program below shows a rotation on three keys, measures the average node depth for random insertion orders against the middle-rooted tree, checks that every middle split leaves halves that differ by at most one, counts the stack and list sizes when walking a left-leaning chain of 5000 nodes, rebuilds lists with many repeated keys, and compares a rebuild that resets the links with one that does not:

import math
import random


class Node:
    def __init__(self, key, tag=None):
        self.key = key
        self.tag = tag               # stands in for the extra per-node data
        self.left = self.right = None


def insert(root, key, tag=None):
    node = Node(key, tag)
    if root is None:
        return node
    cur = root
    while True:
        side = "left" if key < cur.key else "right"
        nxt = getattr(cur, side)
        if nxt is None:
            setattr(cur, side, node)
            return root
        cur = nxt


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


def rotate_right(node):
    """The left child moves up; the old root becomes its right child."""
    top = node.left
    node.left, top.right = top.right, node
    return top


def rotate_left(node):
    top = node.right
    node.right, top.left = top.left, node
    return top


# Same in-order sequence 1, 2, 3 in two different shapes: a rotation changes only the shape.
chain = Node(3)
chain.left = Node(2)
chain.left.left = Node(1)
print("left-leaning chain, preorder:", preorder(chain))
balanced = rotate_right(chain)
print("after one right rotation at the root, preorder:", preorder(balanced))
print("root", balanced.key, "children", balanced.left.key, balanced.right.key)
back = rotate_left(balanced)
print("one left rotation undoes it, preorder:", preorder(back))


def average_depth(keys_in_order):
    root = None
    for k in keys_in_order:
        root = insert(root, k)
    total, stack = 0, [(root, 0)]
    while stack:
        node, d = stack.pop()
        total += d
        for c in (node.left, node.right):
            if c:
                stack.append((c, d + 1))
    return total / len(keys_in_order)


def balanced_order(lo, hi):
    """Keys lo..hi-1 listed so that inserting them in this order builds the middle-rooted tree."""
    if lo >= hi:
        return []
    mid = (lo + hi) // 2
    return [mid] + balanced_order(lo, mid) + balanced_order(mid + 1, hi)


n = 1023
rng = random.Random(11)
trials = 100
mean_random = sum(average_depth(rng.sample(range(n), n)) for _ in range(trials)) / trials
print(f"\nn = {n} keys, average node depth (edges):")
print(f"  random insertion orders, mean of {trials}: {mean_random:.2f}")
print(f"  1.39 * log2(n): {1.39 * math.log2(n):.2f}")
print(f"  middle-rooted tree: {average_depth(balanced_order(0, n)):.2f}")


def halves_differ_by_at_most_one(lo, hi):
    if hi - lo <= 1:
        return True
    mid = (lo + hi) // 2
    return (abs((mid - lo) - (hi - mid - 1)) <= 1
            and halves_differ_by_at_most_one(lo, mid) and halves_differ_by_at_most_one(mid + 1, hi))


print("every range of every size 0..2000 splits into halves that differ in size by at most 1:",
      all(halves_differ_by_at_most_one(0, size) for size in range(2001)))

# Memory: walking a left-leaning chain keeps every node on the stack at once.
size = 5000
chain = None
for k in range(size, 0, -1):
    chain = insert(chain, k)
stack, cur, deepest, collected = [], chain, 0, 0
while stack or cur:
    while cur:
        stack.append(cur)
        cur = cur.left
    deepest = max(deepest, len(stack))
    cur = stack.pop()
    collected += 1
    cur = cur.right
print(f"descending inserts of {size} keys: the in-order stack reaches {deepest} entries, the node list {collected}")


# Repeated keys and stale links. Same rebuild as the main listing, with a switch to skip the link reset.
def inorder_nodes(root):
    out, stack, cur = [], [], root
    while stack or cur:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur)
        cur = cur.right
    return out


def build(nodes, lo, hi, reset=True):
    if lo >= hi:
        return None
    mid = (lo + hi) // 2
    node = nodes[mid]
    left = build(nodes, lo, mid, reset)
    right = build(nodes, mid + 1, hi, reset)
    if reset or left:
        node.left = left
    if reset or right:
        node.right = right
    return node


def height(root):
    h, level = -1, [root] if root else []
    while level:
        h += 1
        level = [c for n in level for c in (n.left, n.right) if c]
    return h


rng = random.Random(3)
good = True
for _ in range(300):
    keys = [rng.randint(0, 4) for _ in range(rng.randint(0, 40))]      # few distinct values, many repeats
    root = None
    for i, k in enumerate(keys):
        root = insert(root, k, tag=i)                                  # tag = arrival position
    before = [(n.key, n.tag) for n in inorder_nodes(root)]
    nodes = inorder_nodes(root)
    root = build(nodes, 0, len(nodes))
    after = [(n.key, n.tag) for n in inorder_nodes(root)]
    good = good and before == after and height(root) == (len(keys).bit_length() - 1 if keys else -1)
print("300 lists with many repeated keys: same keys and tags in the same order, height floor(log2 n):", good)


def times_reached(root):
    """How many times a walk from the root reaches nodes it has already seen (0 in a proper tree)."""
    seen, repeats, stack = set(), 0, [root]
    while stack:
        node = stack.pop()
        if id(node) in seen:
            repeats += 1
            continue
        seen.add(id(node))
        stack.extend(c for c in (node.left, node.right) if c)
    return repeats


for reset in (True, False):
    chain = None
    for k in range(1, 8):
        chain = insert(chain, k)
    nodes = inorder_nodes(chain)
    rebuilt = build(nodes, 0, len(nodes), reset)
    print(f"reset links = {reset}: nodes reached a second time = {times_reached(rebuilt)}")

Output:

left-leaning chain, preorder: [3, 2, 1]
after one right rotation at the root, preorder: [2, 1, 3]
root 2 children 1 3
one left rotation undoes it, preorder: [3, 2, 1]

n = 1023 keys, average node depth (edges):
  random insertion orders, mean of 100: 11.08
  1.39 * log2(n): 13.90
  middle-rooted tree: 8.01
every range of every size 0..2000 splits into halves that differ in size by at most 1: True
descending inserts of 5000 keys: the in-order stack reaches 5000 entries, the node list 5000
300 lists with many repeated keys: same keys and tags in the same order, height floor(log2 n): True
reset links = True: nodes reached a second time = 0
reset links = False: nodes reached a second time = 3

A right rotation at the root of the chain 3, 2, 1 lifts 2 to the root with 1 and 3 as children; the in-order sequence 1, 2, 3 is unchanged and only the shape differs. For 1,023 keys the middle-rooted tree has the minimum possible average depth, while a random insertion order averages about 11 levels. The leading term 1.39 log2 n overshoots the measured average by a constant, since it ignores lower-order terms.

Follow-ups and how the answer changes

• To rebalance in O(1) extra memory, use the Day-Stout-Warren algorithm (a rebalancing method built only from rotations): rotate the tree into a right-leaning chain, then do rounds of left rotations. It is still O(n) time but needs no list. A rotation is a local change of two links that moves one node up and one down while keeping the in-order sequence; the checking program shows one on three nodes. Day-Stout-Warren is extension reading; a typical interview needs the list-and-middle rebuild above and a one-line mention of rotations.
• If other threads are reading the tree during the rebuild, relinking the live nodes breaks them: build a copy and swap the root pointer instead.
• To avoid rebuilds altogether, use a self-balancing tree (AVL or red-black) that restores balance on every insert.

Running the code

Save the listing as bst_rebuild.py and run python3 bst_rebuild.py (Python 3.12, standard library only). The checking program is self-contained: save it as rebuild_checks.py and run it the same way.

Direct answer

Pick a project that genuinely missed its goal, not a disguised win or a "weakness that's really a strength." Narrate what happened briefly, then spend most of the answer on root-cause analysis and the concrete practice you changed afterward. Interviewers weight the diagnosis and the behavior change far more than the failure itself.

Structured elaboration

Selecting the story

• The miss has to be real and consequential: a target you clearly did not hit, not a near-miss inside an overall win (that's a different story, see the near-miss variant of this question).
• Pick something you had real decision authority over. "Leadership decided X and it failed" isn't your story to own.

Structure

1. Situation/Task: 2-3 sentences, just enough context to understand the stakes.
2. Action: what you actually controlled, not the whole team's work.
3. Result: state the miss plainly, including what it cost (schedule, trust, money).
4. Root cause, as a distinct pass, split into technical, process, and communication causes. Most real failures have more than one.
5. Changed behavior: the specific practice you adopted afterward, and whether it's held up since.

Ownership calibration
Name your specific role and decisions without blaming teammates or "the org." A senior answer identifies systemic causes it can point to concretely, not just personal fault, and it doesn't hide behind the team either.

Worked example

Situation: six-month project to build a real-time analytics dashboard with a strict latency target under 200ms for filtered queries.

Task: I owned the architecture and delivery.

Action: I chose a custom in-memory indexing approach and, under schedule pressure, deferred load testing until late in the build instead of building it in from the start.

Result: under real load the custom index caused GC pauses (the runtime periodically freezing to reclaim memory), and query latency exceeded the 200ms target by several times over. We missed the launch date and shipped a mitigated version a few weeks late.

Root cause:

• Technical: an unproven custom component was carrying a hard non-functional requirement.
• Process: load testing was deferred instead of scheduled in from day one.
• Communication: I didn't flag the performance risk to stakeholders until it had already materialized.

Changed behavior: I now put a load-test gate before any performance-sensitive feature is considered done, and I default to proven, battle-tested storage/indexing components for hard non-functional requirements instead of building custom ones under time pressure.

Trade-offs & pitfalls

• Choosing a "fake failure" that's secretly a win is the most common wrong turn here, and interviewers see through it immediately.
• Stopping at a generic lesson like "I learned to test more" signals you didn't actually diagnose the cause; name the specific practice that changed.
• Scapegoating teammates or "the org" undermines the ownership signal this question is testing for.
• Don't minimize the real cost of the miss (schedule slip, client impact), but don't catastrophize it either; state it plainly and move to what changed.

Direct answer

I treat resilience on-call as something built out of a small number of concrete habits and boundaries decided in advance, not willpower in the moment: a fixed way I triage what's actually urgent, an explicit point at which I hand off or pull someone else in, and a real recovery plan after a shift, not just getting through it.

Structured elaboration

• Concrete habits:
  • Before anything else during a page (an automated on-call alert, typically a phone call or app notification, that summons you to respond to an incident), I do a short check: is this actually degrading users right now, or can it wait until working hours? That single habit stops adrenaline from treating every page as equally urgent.
  • One habit I've taught teammates directly: at the start of any incident expected to run long, write one line stating what "good enough for now" looks like, separate from "fully fixed." Naming the stopping point up front stops a shift from silently stretching for hours past the point where the immediate danger was already contained.
  • Physical basics that sound trivial but hold up under pressure: water and food within reach before starting, and a standing habit of stepping away from the screen for even a couple of minutes once the immediate danger is contained, because clear thinking degrades measurably after sustained high-alert focus.
• Escalation boundaries: I decide, before I'm tired and pressured, what conditions justify waking someone else up (customer-facing data loss, a security exposure, anything I can't diagnose within a set amount of time alone) versus what can wait for the next person's shift. Having that boundary decided in advance means I'm not negotiating it with myself at 3 a.m., which is exactly when judgment is worst.
• Continuity during long incidents:
  • Delegation: as soon as an incident looks like it will run past roughly an hour, I explicitly hand off a piece of it, even something small like "you own customer updates, I own the fix," rather than trying to hold the whole thing myself. Splitting ownership early is much easier than trying to split it after everyone is exhausted.
  • Rest plans: for anything spanning multiple hours or overnight, I build in an explicit handoff or rotation rather than pushing through solo, and I say out loud when I'm no longer sharp enough to be making decisions, which is a harder habit than it sounds because admitting fatigue under pressure can feel like admitting weakness.
• After the incident: recovery isn't just going back to normal work immediately. I protect a short block of low-stakes time right after a long incident before diving into new tickets, since the mental load of a multi-hour incident doesn't clear the moment the page stops firing, and skipping that block is how minor mistakes creep into the next day's work.

Worked example

During a multi-hour outage that started late at night, I was the first responder. At the one-hour mark, using my own rule of thumb for when a page has gone long, I paged a second engineer to take over customer updates so I could stay fully focused on the fix rather than context-switching between diagnosis and status writing. Some hours in, using my own escalation boundary, I wasn't confident that pushing forward alone was still the right call given how tired I was starting to feel, so I looped in a more senior engineer as a second set of eyes rather than waiting until fatigue caused a bad decision. We resolved it not long after.

Rather than immediately picking up the next morning's backlog, I blocked the first hour of my day for nothing beyond writing up what happened while it was fresh, and I didn't schedule anything requiring careful judgment until after that recovery block, since I've learned that skipping it is when I make my next mistake.

Trade-offs and pitfalls

The failure mode on the habits side is pretending stress management is purely personal willpower rather than a set of decisions made in advance; boundaries decided under pressure, in the moment, are unreliable exactly when you need them most. On the delegation side, the common mistake is holding onto full ownership too long out of a sense that asking for a handoff looks like weakness, which is precisely what turns a one-hour incident into an exhausted, error-prone six-hour one. The other trap is skipping recovery entirely once the alert clears, treating the page stopping as the end of the cost, when the accumulated fatigue and narrowed judgment from a long incident carries directly into the next day's decisions if you don't protect time to actually recover.