Lyft Data Engineer Interview Preparation Guide (Entry Level)

Direct answer

Since a raw Python dict cannot be a set/dict key (dicts are unhashable, by design, because
they are mutable), convert each record to something hashable before deduping: a canonical
serialization (deterministic JSON with sorted keys), a sorted tuple of its items, or a stable
content fingerprint (a SHA-256 digest of the canonical form). The fingerprint approach is
usually best in an ETL (extract, transform, load) pipeline, since it gives a fixed-size, directly
comparable key regardless of record size, but all three require deliberate handling of key order, floating-point
representation, and missing fields, or dedup will silently under- or over-merge records.

Structured elaboration

Why the dict itself cannot be a key. Python requires a key to be hashable, and hashability
requires immutability, since a mutable object's hash could change after it is inserted, which
would break the exact bucket-integrity guarantee hash-based lookup depends on (the same failure
mode discussed for mutable hash keys generally). A plain dict is mutable, so Python disallows
it as a key outright, raising a TypeError rather than allowing a subtly broken key.

Canonical serialization (deterministic JSON). Serialize each record with sort_keys=True so
two dicts with the SAME content but different key insertion order produce the IDENTICAL JSON
string, then use that string (or its hash) as the dedup key. This alone handles key-order
independence but does nothing yet about floating-point noise or missing-versus-null fields; those
need explicit normalization before serialization.

Sorted tuples. Convert sorted(record.items()) into a tuple, which is hashable as long as
every value inside it is also hashable (a nested dict or list value is NOT, so this approach
needs a recursive conversion for nested structures, which canonical JSON serialization handles
more naturally since JSON is already a recursive format).

Stable fingerprints (SHA-256). Hash the canonical serialization with a cryptographic digest
to get a fixed-size, directly comparable identifier, useful when records are large (the
fingerprint is small and constant-size regardless of record size) or when you want to persist the
dedup key separately from the record itself.

The three edge cases the question calls out, and how to actually handle each.

• Ordering: solved by sort_keys=True in JSON serialization, or by sorting the tuple's items
  before hashing; without this, two logically identical records with differently-ordered keys
  fingerprint differently and dedup silently fails to merge them.
• Floating point: two records can represent the SAME business value with different floating-
  point bit patterns (upstream arithmetic noise, different serialization precision), which
  fingerprint DIFFERENTLY unless floats are rounded to a fixed, deliberately chosen precision
  before serialization; skipping this rounding step causes dedup to under-merge (treat identical
  records as distinct).
• Missing fields: a field entirely ABSENT from a dict and the same field explicitly set to
  null/None are different things to a naive JSON serializer (json.dumps omits an absent key
  entirely but writes null for an explicit None), so normalize by explicitly filling every
  expected field via record.get(field, default) before serializing, or two logically identical
  records (one with a field omitted, one with it explicitly null) will fingerprint differently and
  fail to dedup.

Performance and correctness. Fingerprinting is O(record size) per record, done once; the
subsequent dedup itself is then an ordinary O(1) average hash-set membership check per record,
same as any other hash-based dedup. Correctness depends entirely on how faithfully the
normalization step (rounding, explicit field-filling, key sorting) captures "these two records
should count as the same," which is a judgment call specific to the data, not something the
serialization mechanism decides for you.

Worked example

import hashlib, json

fields = ["user_id", "amount", "region", "notes"]
a = {"user_id": "u1", "amount": 19.99, "region": "US", "notes": None}
b = {"region": "US", "notes": None, "amount": 19.99, "user_id": "u1"}       # reordered keys
c = {"user_id": "u1", "amount": 19.99, "region": "US"}                       # 'notes' key ABSENT
d = {"user_id": "u1", "amount": 19.99000000000001, "region": "US", "notes": None}  # float noise

# Confirm the premise: a raw dict cannot be a set element at all.
try:
    literal_set = {a}
except TypeError as e:
    print("TypeError on raw dict in a set literal:", e)

def canonical_fingerprint(record, expected_fields, ndigits=6):
    normalized = {}
    for field in expected_fields:
        value = record.get(field, None)
        if isinstance(value, float):
            value = round(value, ndigits)
        normalized[field] = value
    canonical_json = json.dumps(normalized, sort_keys=True)
    return hashlib.sha256(canonical_json.encode()).hexdigest()

print(canonical_fingerprint(a, fields) == canonical_fingerprint(b, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(c, fields))
print(canonical_fingerprint(a, fields) == canonical_fingerprint(d, fields))

# Confirm rounding is doing real work: a naive fingerprint WITHOUT rounding
# should fail to match a and d, even though the rounded version matches.
def naive_fingerprint(record, expected_fields):
    normalized = {f: record.get(f, None) for f in expected_fields}
    return hashlib.sha256(json.dumps(normalized, sort_keys=True).encode()).hexdigest()

print(naive_fingerprint(a, fields) == naive_fingerprint(d, fields))

Running this: attempting {a} (a literal set containing a plain dict) raises
TypeError: cannot use 'dict' as a set element (unhashable type: 'dict'), confirming the
premise. Record a (natural key order) and record b (identical content, shuffled key order)
fingerprint IDENTICALLY (True). Record c, where the notes key is entirely absent rather than
explicitly None, ALSO fingerprints identically to a (True), because both normalize through
record.get("notes", None) to the same value. Record d, where amount carries floating-point
noise (19.99000000000001 instead of 19.99), fingerprints identically to a (True) once
rounded. The final line confirms rounding is actually load-bearing: the naive (unrounded)
fingerprint of a and d comes out False, a false negative that would leave two logically
identical records undeduped if the rounding step were skipped.

Trade-offs and pitfalls

• Rounding precision for floats is a business decision, not a technical default. Too coarse a
  rounding (few digits) can merge genuinely different values; too fine (many digits) can leave
  float noise unresolved. Pick the precision that matches the field's real-world meaningful
  granularity (for a currency amount, cents is usually the right granularity).
• Silently defaulting missing fields to None can mask real data-quality problems if a field
  is SOMETIMES missing due to an upstream bug rather than legitimately absent; log or flag records
  that rely on the default rather than silently normalizing them away.
• Nested structures (a dict value containing another dict or a list) need the SAME
  normalization recursively applied, or a nested float or nested key-order difference reproduces
  the exact same bugs one level down.
• A fingerprint collision is theoretically possible but not the practical risk here: SHA-256's
  collision probability is negligible at any realistic ETL scale; the actual, common failure mode
  is a NORMALIZATION bug (missed rounding, missed default-fill, unsorted nested keys), not a hash
  collision.

Direct answer: For each business key in the staging table, rank its rows by effective_date descending with ROW_NUMBER() OVER (PARTITION BY custom_key ORDER BY effective_date DESC); the row that lands at rank 1 is the current version. A type 2 slowly changing dimension (a dimension table that keeps every historical version of a record instead of overwriting it, marking exactly one row per key as the current one) needs that current-row determination made once per load and then reconciled against what the dimension table already has: newly-current rows get inserted or flagged, and whatever row was previously flagged current for that key gets its flag cleared if a newer version has arrived.

Structured elaboration

1. Rank staging rows per business key. ROW_NUMBER() partitioned by custom_key, ordered by effective_date DESC, gives each row its recency rank within that key; rank 1 is the newest version as of this load.
2. Derive current_flag directly from the rank, rather than as a separate computed step: rn = 1 IS the definition of current.
3. Reconcile against the existing dimension table. The newly-current row for a key needs current_flag = TRUE inserted (a genuinely new version) or updated (if it already exists but wasn't flagged current before); any row in the dimension table that WAS flagged current for that key but is no longer the top rank needs current_flag = FALSE.

-- staging(custom_key, attr, effective_date)
SELECT custom_key, attr, effective_date,
  ROW_NUMBER() OVER (PARTITION BY custom_key ORDER BY effective_date DESC) = 1 AS current_flag
FROM dim_staging;

Worked example (executed in DuckDB). Key 1 has two staging rows (gold effective 2025-01-01, platinum effective 2025-03-01); key 2 has one row (silver effective 2025-02-01).

custom_key | attr     | effective_date | current_flag
1          | gold     | 2025-01-01     | false
1          | platinum | 2025-03-01     | true
2          | silver   | 2025-02-01     | true

Key 1's later row (platinum) is correctly the only one flagged current; the earlier gold row is retained (type 2 keeps history) but demoted. Key 2, with only one row, is trivially current.

Writing the upsert. The insert/update side depends on the engine. Where MERGE is available (SQL Server, Oracle, Snowflake, Postgres 15+), one statement can both insert genuinely new rows and update current_flag on rows that already exist:

MERGE INTO dim_table AS tgt
USING (
  SELECT custom_key, attr, effective_date,
    ROW_NUMBER() OVER (PARTITION BY custom_key ORDER BY effective_date DESC) = 1 AS current_flag
  FROM dim_staging
) AS src
ON tgt.custom_key = src.custom_key AND tgt.effective_date = src.effective_date
WHEN MATCHED THEN
  UPDATE SET current_flag = src.current_flag
WHEN NOT MATCHED THEN
  INSERT (custom_key, attr, effective_date, current_flag)
  VALUES (src.custom_key, src.attr, src.effective_date, src.current_flag);

-- Demote any row for a key that just received a new current version
UPDATE dim_table
SET current_flag = FALSE
WHERE current_flag = TRUE
  AND custom_key IN (SELECT custom_key FROM dim_staging)
  AND effective_date < (
    SELECT MAX(effective_date) FROM dim_staging s WHERE s.custom_key = dim_table.custom_key
  );

On engines without MERGE (or where the team prefers explicit control), the same outcome is two statements: an INSERT ... WHERE NOT EXISTS for genuinely new (key, effective_date) combinations, followed by an explicit UPDATE that sets current_flag = FALSE on every previously-current row whose key now has a newer version, and TRUE on the new one.

Trade-offs & pitfalls

• Late-arriving data (a row with an effective_date earlier than the current dimension row, but arriving after the load that made that row current) needs its own handling: naively re-running the rank-and-flag logic against the union of staging and existing dimension rows, not staging alone, is what correctly re-derives which row is current after a backdated insert.
• A tie on effective_date for the same key needs a secondary ORDER BY key (a load sequence number or ingestion timestamp), or which of two same-day versions ends up flagged current is the identical nondeterminism problem covered under dedup tie-breaking elsewhere in this topic.
• RANK() instead of ROW_NUMBER() would let two rows share rank 1 on an exact effective-date tie, which almost never matches the type 2 requirement of exactly one current row per key; use ROW_NUMBER() specifically, not RANK(), for this pattern.
• Don't forget an effective_end_date (or equivalent) column alongside current_flag: setting the previous row's end date to the new row's effective date at demotion time is what makes point-in-time historical queries ('what did this record look like on date X') possible, not just 'what is it now.'

Direct answer

Walk through long once with a single pointer, and advance a second pointer into short only when the current character of long matches the character short is currently waiting for. If the pointer into short reaches the end before long runs out, every character of short was found in order, so short is a subsequence of long.

Structured elaboration

Approach

def is_subsequence(short, long):
    i = 0
    if not short:
        return True
    for ch in long:
        if i < len(short) and ch == short[i]:
            i += 1
        if i == len(short):
            return True
    return i == len(short)

Only one pass over long is made, and the pointer into short never moves backward, so the total work is O(n) where n is the length of long, matching the question's explicit complexity requirement. No extra data structure is needed since matching only ever needs to compare the CURRENT position of short against the current character of long.

Application context (the question's explicit ask)

This same one-pass check is the building block behind approximate matching and fuzzy token mapping: for example, checking whether a user's typed abbreviation could plausibly expand to a longer canonical term ("gcm" as a subsequence of "google cloud monitoring"), or filtering a large candidate list down to the ones that could still match a partially typed query, before applying a more expensive scoring step only to that smaller candidate set.

Worked example

Executed with python3 s83.py, five pinned cases including two explicit edge cases (empty short, empty long):

is_subsequence('abc', 'ahbgdc')     = True  expected=True  match=True
is_subsequence('axc', 'ahbgdc')     = False expected=False match=True
is_subsequence('', 'anything')      = True  expected=True  match=True
is_subsequence('abc', '')           = False expected=False match=True
is_subsequence('ace', 'abcde')      = True  expected=True  match=True

'abc' is found in order inside 'ahbgdc' (a, then b, then c, each appearing later than the last), so it returns True. 'axc' fails because after matching 'a', no 'x' appears anywhere later in 'ahbgdc', so the pointer into short never reaches the end.

Trade-offs and pitfalls

• The empty-short-is-always-a-subsequence edge case (is_subsequence('', 'anything') returning True) is easy to get backwards if the loop logic is written slightly differently; the explicit if not short: return True guard above makes this an intentional decision rather than an accident of how the loop happens to terminate.
• If this check needs to run many times against the SAME long string with many different short candidates, a smarter structure (precomputing, for each position and character, the next occurrence of that character) avoids repeating the full O(n) scan per query, at the cost of O(n * alphabet size) preprocessing; that preprocessing trade is only worth it when the number of queries against the same long string is large.
• This only answers yes/no. If the caller also needs the actual matched positions in long (for example, to highlight which characters satisfied the match), track and return the index list as the pointer advances, rather than just the boolean.

Direct answer

With multiple parallel workers writing immutable objects into a data lake, the risk is not one worker crashing mid-write (that is the single-writer recovery problem), it is two workers both believing they own the same logical write and both producing an object for it, or one worker retrying and producing a second object for work it already completed. The fix combines a deterministic deduplication key (so retries are self-cancelling), an atomic commit manifest (so partial or duplicate work is never visible to readers), and a coordinator or distributed-idempotency-check layer (so two workers do not redundantly do the same logical work in the first place), plus a reconciliation approach that only checks what changed rather than rescanning the whole dataset.

Structured elaboration

Deduplication keys. Every object a worker writes is named deterministically from the logical unit of work it represents (a partition key plus a source-side version or a content hash), never from a worker-local counter or a fresh UUID per attempt. Two workers (or one worker retried) producing output for the SAME logical unit then produce the SAME object key, so the data lake's own overwrite-by-key semantics collapse them, exactly the same content-addressable pattern used for idempotent writes generally, applied at the granularity of "one worker's unit of work" rather than "one event."

Atomic commit manifests. Individual object writes to a data lake are not enough on their own, since a reader listing the target prefix mid-write sees an inconsistent, partial set of objects. A manifest (or a table format's transaction log, Delta/Iceberg being the standard examples) is written LAST, atomically, and enumerates exactly which objects constitute the current, complete, correct version. Readers consult the manifest, never the raw object listing, so partial or in-flight work from any worker is invisible until the manifest says it is done, this is the same atomic-manifest-commit mechanism a single job uses, extended here to many concurrent writers producing manifest entries.

Write-ahead logs or staging plus atomic rename. Before committing to the manifest, workers write to a staging area (a private prefix or a versioned object). This isolates in-progress work from the visible manifest entirely; a crashed worker's staged-but-uncommitted objects are simply orphaned data, cleaned up later by compaction, never something a reader could accidentally observe as "the current state."

Coordinator patterns versus distributed idempotency checks. Two structurally different ways to prevent redundant work:

• Coordinator pattern: a single component (a lock service, a leader-elected assignment table) decides which worker owns which unit of work before any writing starts, so at most one worker is ever actively producing output for a given logical unit at a time. Simple to reason about; the coordinator itself becomes a single point that must be highly available and must itself recover cleanly from a crash.
• Distributed idempotency check: no central assignment; any worker may attempt any unit of work, and correctness relies entirely on the deduplication key plus atomic commit to collapse duplicate attempts after the fact. No coordinator to keep available, but more redundant work is actually performed (multiple workers may compute the same output before one "wins" at commit time), which is wasteful of compute even though it stays correct.
  The right choice depends on how expensive redundant computation is: cheap transformations tolerate the distributed-idempotency-check approach's wasted work; expensive computations (a large join, an ML feature computation) usually justify paying for a coordinator to avoid redundant work outright.

Efficient reconciliation without reprocessing everything. Track, per logical unit, the source version it was derived from (the same version/timestamp used in the dedup key). A reconciliation pass compares the manifest's recorded source versions against the current source, and only reprocesses units whose source version has actually advanced, an incremental check bounded by what changed, not a full rescan of the entire dataset.

Worked example

10 parallel workers process a data lake write for 100,000 logical partitions (say, one partition per customer per day), using the distributed-idempotency-check approach (no coordinator). Assume a modest 2% rate of overlapping work due to dynamic task rebalancing (two workers both picking up the same partition before either commits):

Each of those 2,000 partitions is computed twice (4,000 total computations for 2,000 logical units), wasting roughly:

but produces exactly 100,000 manifest entries at commit time, since the deterministic dedup key means both workers' output for the same partition either lands on the identical object key (content-addressed) or the manifest-commit step accepts only the first writer to successfully append that partition's entry and the second's redundant object becomes an orphan for later compaction. Correctness is unaffected by the redundant computation; only compute cost is. Switching to a coordinator pattern for this same workload would eliminate the ~2% redundant compute at the cost of the coordinator's own availability and latency overhead, a real trade worth making explicitly rather than defaulting to either choice.

Trade-offs and pitfalls

• Common mistake: relying on "last writer wins" without a deterministic tiebreak. If two workers' output differs even slightly (a subtle nondeterminism in a downstream transformation, floating-point summation order), an arbitrary "whoever commits last" rule can silently pick an inconsistent result across runs; ties should be broken by an explicit, stable rule (a fixed worker ID ordering, or the manifest's own append-only compare-and-swap): the same discipline any deterministic tiebreak on a natural key plus source timestamp needs.
• Coordinator-pattern availability is a real production dependency, not free. A coordinator outage without a fallback either halts all writers (safe but stalls the pipeline) or, worse, tempts a "just proceed without coordination during the outage" shortcut, which reintroduces exactly the duplicate-work problem the coordinator exists to prevent.
• Reconciliation that skips "what changed" tracking degrades into a full rescan under scale. Without a recorded source version per manifest entry, incremental reconciliation cannot tell what needs reprocessing and either reprocesses everything (correct but wastes the exact efficiency this pattern is meant to provide) or trusts staleness silently (efficient but wrong).
• Immutable objects mean updates are new objects, not in-place edits. A "correction" to an already-committed partition is a new object plus a new manifest entry superseding the old one, not a mutation; forgetting this and attempting to overwrite an existing immutable object in place either fails outright (many data lakes reject overwrite) or, worse, silently succeeds and breaks any concurrent reader relying on that object's immutability.

30-day (Learn & Observe)
Knowledge goals:

• Understand company data domain, data products, pipelines, SLAs.
• Learn the team’s AWS account structure, VPCs, IAM roles, S3 layout, Redshift cluster config, and Spark job orchestration (Airflow/Glue/EMR).
  Hands-on tasks:
• Run local dev Spark job and a small ETL on dev cluster end-to-end.
• Access Redshift (read-only), run sample queries to validate schemas.
• Fix a small low-risk bug or add logging to an existing pipeline.
  Documentation to study:
• Onboarding README, architecture diagrams, data dictionary, runbooks, cost/ops playbooks, CI/CD pipeline docs.
  Ownership & boundaries:
• Read-only on prod; small, supervised changes to dev and staging environments.
  Mentor / checkpoint:
• Assigned buddy (senior DE) + weekly 1:1; end-of-30-day demo of what you ran and findings.

60-day (Contribute & Improve)
Knowledge goals:

• Deep dive into Spark tuning, Redshift distribution/sort keys, partitioning, and AWS cost drivers.
• Understand monitoring/alerting (CloudWatch, Datadog) and data quality checks.
  Hands-on tasks:
• Implement or optimize one ETL job (performance or cost), add unit/integration tests.
• Build a data quality check and alert for a critical pipeline.
  Documentation to study:
• Job templates, testing guide, performance tuning notes, security policies.
  Ownership & boundaries:
• Own one non-critical pipeline end-to-end (dev→staging→prod with peer review).
  Mentor / checkpoint:
• Biweekly sync with tech lead and peer review; present performance improvements and test coverage.

90-day (Own & Scale)
Knowledge goals:

• System-level understanding: scaling strategy, disaster recovery, schema evolution patterns.
• Influence roadmap: propose improvements to observability, partitioning, or cost optimizations.
  Hands-on tasks:
• Lead migration/optimization project (e.g., rewrite job to Spark SQL, change Redshift sort keys).
• Document runbook for your owned pipeline; onboard another teammate.
  Documentation to study:
• Architecture decision records, capacity planning docs, compliance/audit docs.
  Ownership & boundaries:
• Primary owner for critical pipeline(s) with responsibility for SLA, runbooks, and on-call for rotation.
  Mentor / checkpoint:
• 90-day review with manager, senior data engineer, and product stakeholder; agree on goals for next quarter and handoff notes.

General tips:

• Schedule weekly shadowing of on-call rotations first 60 days.
• Keep a running ramp-up doc: questions, discoveries, and proposed quick wins.
• Seek feedback after each checkpoint and iterate on ownership scope.

Direct answer

A lowest common ancestor (LCA) query in a general binary tree can be answered with a single postorder-style depth-first search (DFS, a traversal that explores each branch fully before backtracking) that returns node references bubbling up: if a subtree's search finds both target nodes on different sides, the current node is the LCA; if only one side finds anything, that result is passed further up. When the tree happens to be a binary search tree (BST), searching both subtrees isn't necessary at all: comparing the two target values against the current node's key, and walking down toward whichever side both targets agree on, is enough.

Structured elaboration

Approach: general binary tree

• Recurse into both children. At any node, if the node itself is one of the two targets, or if the node is None, return it directly (a None or a matched target both act as the "nothing more to find below here, here's what was found" signal).
• After the recursive calls return, if both the left and right calls found something non-None, the current node sits between the two targets, so it is the LCA; return it.
• If only one side found something, that result (the target itself, or an LCA found deeper down) is passed up unchanged, since the current node cannot be the answer.

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lca_general(root, p, q):
    """Lowest common ancestor in a general binary tree. p and q are TreeNode
    references known to exist in the tree."""
    if root is None or root is p or root is q:
        return root
    left = lca_general(root.left, p, q)
    right = lca_general(root.right, p, q)
    if left and right:
        return root
    return left if left else right

Approach: binary search tree

• In a BST, every node's key already encodes where its descendants live relative to it, so two arbitrary nodes don't require searching both subtrees.
• Starting at the root, compare both target values to the current node's key: if both are smaller, the LCA must be in the left subtree, so move left; if both are larger, move right; if they split (one on each side, or either target equals the current key), the current node is the LCA, since that's the first point where the two search paths diverge.
• This turns an O(n) full-tree traversal into an O(h) walk that only ever moves in one direction, without exploring both children at any step.

def lca_bst(root, p_val, q_val):
    """Lowest common ancestor in a binary search tree, using key comparisons
    instead of exploring both subtrees."""
    node = root
    while node is not None:
        if p_val < node.val and q_val < node.val:
            node = node.left
        elif p_val > node.val and q_val > node.val:
            node = node.right
        else:
            return node  # values split here (or one equals node.val): this is the LCA
    return None

Key points

• The general-tree version explores every node in the worst case, since it has no way to prune a subtree without checking it.
• The BST version needs no recursion into both sides at all; it reuses the same "which direction do both targets agree on" comparison as an ordinary BST search, walking a single path from the root.

Worked example

Building this tree:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

This tree also happens to satisfy the BST ordering property (every left descendant is smaller, every right descendant larger), so both functions can be run on it and compared directly. lca_general(root, node(2), node(8)) and lca_bst(root, 2, 8) both print 6 (the two nodes sit in different subtrees of the root). lca_general(root, node(2), node(4)) and lca_bst(root, 2, 4) both print 2 (node 2 is an ancestor of node 4). lca_general(root, node(3), node(5)) and lca_bst(root, 3, 5) both print 4 (they are siblings under node 4).

Trade-offs & pitfalls

Complexity

General binary tree: Time $O(n)$, visiting every node once in the worst case, since there's no way to prune a subtree that hasn't been checked. Space $O(h)$ for the recursion stack, where $h$ is the tree's height ($O(\log n)$ balanced, $O(n)$ degenerate).
Binary search tree: Time $O(h)$, a single downward walk with no backtracking. Space $O(1)$ with the iterative version shown, or $O(h)$ if written recursively.

Edge cases

• One of the two targets is an ancestor of the other: both approaches correctly return the ancestor itself as the LCA.
• p and q are the same node: returns that node.
• p or q is not actually present in the tree: both implementations shown assume presence and will return a plausible-looking but wrong answer rather than erroring; a production version should verify both nodes exist first, a separate O(n) or O(h) check, if that guarantee doesn't already hold elsewhere.
• A deeply skewed tree: the general-tree recursive version risks hitting the language's recursion limit; converting to an explicit iterative stack avoids that.

Applying the BST shortcut to a tree that is not actually a BST silently gives a wrong answer with no error, since the comparison-based walk assumes an ordering invariant that a general binary tree doesn't provide; always confirm which structure is actually in hand before choosing the approach. A second common mistake in the general-tree version is comparing node values instead of node identity when duplicate values are possible, which can match the wrong node entirely.

Direct answer

When historical source records lack a newly-required attribute, choose among backfilling from an independent historical source if one exists, inferring the value from a reliable proxy (like a product code pattern), leaving it explicitly NULL/unknown rather than guessing, or denormalizing a best-effort lookup table, and whichever is chosen, communicate the resulting historical data's confidence level to stakeholders rather than presenting inferred or missing history as equally certain as directly-recorded data.

Structured elaboration

• Backfill from another historical source: if a separate system (an old catalog export, an archived spreadsheet) independently recorded the missing attribute for the historical period, use it, since this is the only option that recovers genuinely accurate historical values rather than an approximation.
• Infer from product codes: if the attribute correlates reliably with something already in the historical data (a SKU prefix pattern that reliably indicates color), infer it, but validate the inference against a sample of KNOWN cases first and disclose the inference's error rate.
• Leave nulls: honest and safe when no reliable recovery method exists; downstream reports must then explicitly handle "unknown" rather than silently treating null as a specific category, and stakeholders should be told certain historical periods lack this attribute rather than left to assume completeness.
• Denormalize with lookup tables: for a small number of known values that can be manually or semi-automatically mapped, a curated lookup table is a middle ground between full inference and leaving nulls, at the cost of ongoing manual maintenance for edge cases.
• Communicating limitations: whichever method is chosen, document and communicate it (a footnote on reports, a data-quality flag on inferred rows) so stakeholders don't treat inferred or reconstructed historical data with the same confidence as directly-recorded data.

Worked example

product_color is newly required but missing for products loaded before 2025. A backfill job finds 60% of historical products have a reliable color code embedded in their SKU (validated against the 40% of products that DO have both a SKU code and a directly-recorded color, confirming the SKU-based inference matches 98% of the time on that known subset), so those 60% are backfilled via inference with a color_source = 'inferred' flag; the remaining 40% with no reliable signal are left NULL with color_source = 'unknown', and both flags are surfaced to any dashboard reporting on historical color-based metrics.

Trade-offs and pitfalls

The most damaging shortcut is silently filling missing historical values with a default or a guess with no confidence tracking, which makes an incomplete historical record LOOK complete, misleading anyone who later relies on it for analysis without realizing part of it is inferred or fabricated. Always preserve and surface the provenance (recorded, inferred, or unknown) of any backfilled attribute.

Direct answer

Defensive programming means writing code that assumes its inputs, callers, and environment will eventually misbehave, and that fails in a controlled, diagnosable way instead of silently corrupting state or crashing somewhere far from the actual mistake. The three patterns interviewers most want to hear are: guard clauses with fail-fast validation, fail-safe defaults, and circuit breakers.

Structured elaboration

Guard clauses and fail-fast validation. Check preconditions at the top of a function and return or throw immediately on invalid input, rather than nesting the happy path three levels deep inside conditionals. This prevents a class of bug where a function silently operates on partially-invalid data because the invalid case was never rejected, it was just never tested. The failure surfaces at the point of the bad input, with a clear message, instead of two call frames later as a confusing null pointer exception.

Fail-safe defaults. When a non-critical piece of configuration or a non-critical dependency is unavailable, degrade to a safe, conservative default rather than propagating the failure. A feature flag service that is down should default to the safest behavior (usually: feature off), not crash the request. This prevents an unrelated dependency's outage from becoming a full outage of your own service.

Circuit breakers. When a downstream dependency starts failing consistently, stop calling it for a cooldown window instead of retrying every request against a dependency that is already down. This prevents cascading failure: without a breaker, a slow or failing downstream call can pile up threads or connections in the caller until the caller itself falls over.

Worked example

Consider a checkout service that calls a fraud-scoring API before completing a purchase. Without defensive programming: the checkout handler passes the request straight to the fraud API, the fraud API starts timing out under load, checkout requests pile up waiting on the timeout, and the whole checkout service runs out of worker threads even though the actual defect is in the fraud API. With the three patterns applied: a guard clause rejects a checkout request with a missing user_id before it ever reaches the fraud API; if the fraud API is unavailable, a fail-safe default routes the order to manual review instead of blocking checkout entirely; and a circuit breaker stops calling the fraud API for 30 seconds once its failure rate crosses a threshold, so checkout degrades to manual review immediately instead of piling up timeouts. The outage that this avoids is a full checkout-service outage caused by a single downstream dependency, which is one of the most common real production incidents.

Trade-offs and pitfalls

Defensive checks are not free. Guard clauses that duplicate the same five checks in ten different functions become their own maintenance burden and are a sign you need a shared validator instead. Fail-safe defaults can hide a real problem if nobody monitors how often the default path is taken (a fraud check that silently defaults to manual review 40% of the time is itself an incident). Circuit breakers add a new failure mode of their own: badly tuned thresholds can trip on a brief blip and reject traffic the dependency could actually have served. The discipline is to add defensive checks at trust boundaries and for dependencies you do not control, not everywhere, and to monitor how often each defensive path actually fires.

Direct answer. A covering index includes every column a query needs, filter and output columns alike, so the planner can answer the query by reading only the index and never touching the underlying table.

Structured elaboration. A normal (non-covering) index scan finds matching entries in the index, then still has to fetch each matching row from the table itself to retrieve any column not stored in the index. If the index instead already contains every column the query filters on AND every column it returns (either as part of the indexed key or as extra "included" columns many engines let you attach without making them part of the sort order), that second table visit becomes unnecessary entirely, which is usually the single biggest win an index can offer for a read-heavy query.

Worked example. I verified this concretely with logs(user_id, event_type, created_at, payload) and the query SELECT user_id, event_type FROM logs WHERE created_at >= '2025-01-15' AND event_type = 'click':

CREATE INDEX idx_logs_covering
  ON logs (created_at, event_type)
  INCLUDE (user_id);

SELECT user_id, event_type
FROM logs
WHERE created_at >= '2025-01-15' AND event_type = 'click';

Running the equivalent query against a small hand-built table returned exactly the two matching rows for a user with two click events on or after that date, confirming the query's own filter and output columns line up with what the index above would need to store: created_at for the range filter, event_type for the equality filter and as an output column, and user_id as an output-only included column. With all three present, the planner has no reason left to visit the table at all.

Trade-offs and pitfalls. A covering index is bigger than the equivalent index on just the filtered columns, and every extra included column adds write cost on every INSERT and UPDATE that touches it; the win only pays for itself on a query that runs often enough, or is latency-sensitive enough, that avoiding the table visit is worth the extra storage and write overhead. It's also fragile to change: adding one more output column to the query, without updating the index, silently loses the covering property and falls back to a normal index scan.

Direct answer
Before presenting, think through the questions a skeptical, informed listener would actually ask, prioritizing the ones that probe your weakest assumption or your most surprising claim, and prepare a short, direct answer for each rather than hoping you'll improvise well.

Structured elaboration

1. Look for your weakest link first. Every piece of work has at least one assumption, data limitation, or judgment call that's more debatable than the rest; that's almost always where a sharp question comes from.
2. Look for your most surprising or counterintuitive claim. Anything that contradicts what people expected invites a "how do you know that's really true?" question.
3. Prepare a one-to-two sentence answer, not a rehearsed speech. A concise, direct answer reads as confident; a long, defensive one reads as though you're worried about the question.
4. It's fine to prepare an honest "we don't know yet" answer for a genuine gap, rather than inventing a more impressive-sounding answer under pressure; a confident admission of a limitation is usually better received than an unconvincing dodge.
5. Practice saying the answers out loud, not just thinking through them mentally; the gap between a mentally-rehearsed answer and one you can actually say smoothly under pressure is often bigger than expected.

Worked example
Presenting a recommendation to shift budget from one marketing channel to another based on eight weeks of data: anticipated tough questions might be "how confident are you this isn't just seasonal?", "what happens if the trend reverses next month?", and "did you control for the pricing change that happened in week 5?" Prepared answers: "We checked against the same period last year and saw a similar pattern, though eight weeks is admittedly a short window;" "if it reverses, the downside is limited since we're proposing a 20% shift, not the full budget;" "we did exclude the two weeks around the pricing change specifically to avoid conflating the two effects."

Each answer is short, direct, and, where there's a genuine limitation (the short time window), honestly acknowledged rather than glossed over.

Trade-offs and pitfalls

• Over-preparing for every conceivable question can lead to over-rehearsed, stiff-sounding answers; focus on the two or three questions most likely to actually come up, not an exhaustive list.
• Being defensive about a genuinely fair question damages credibility more than the limitation itself would; a calm, honest acknowledgment of a real gap usually lands better than an unconvincing justification.
• If a question comes up that you genuinely didn't anticipate and don't know the answer to, saying so plainly and offering to follow up is stronger than guessing in the moment.