Entry Level Backend Developer Interview Preparation Guide - FAANG Standards

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

A hash table stores key/value pairs so that lookup, insertion, and deletion all run in average-case
constant time, O(1), regardless of how many entries it holds. It does this by using a hash function
to convert each key into an integer, and using that integer (reduced modulo the table size) as the
index of an array where the entry lives.

Structured elaboration

The three moving parts.

• Keys are whatever you look things up by (a string, a number, a tuple of fields).
• Buckets are the slots of a fixed-size backing array. The number of buckets is the table's
  capacity.
• The hash function maps a key to an integer, and the table takes that integer modulo the
  capacity to get a bucket index. A good hash function scatters different keys roughly uniformly
  across the buckets, so no single bucket ends up disproportionately full.

Why O(1) is only an average, not a guarantee. If the hash function scatters n keys uniformly
across m buckets, each bucket holds about n/m keys on average, a small constant so long as the table
resizes to keep n/m bounded (this ratio is the load factor, covered by its own question). Looking a
key up means computing its bucket index once (O(1)) and then scanning that one small bucket, so the
whole operation is O(1) on average.

What breaks the average-case claim. The O(1) claim depends on the hash function actually
distributing keys uniformly over the keys you will actually see. It fails when:

1. The input is adversarial. An attacker who can choose the keys (e.g. form-field names, JSON
   object keys) can pick values that all hash to the same bucket, forcing every one of them into a
   single long chain, O(n) to look any of them up. This is a real, historically-exploited attack class (the mechanics and defenses are a deep topic in their own right).
2. Load factor is left unbounded. If the table never resizes as it fills up, buckets grow long
   even with an honest hash function.
3. The hash function itself is weak. A hash function with poor bit-mixing (e.g. one that only
   varies its low bits for common key patterns) can cluster "normal" keys into a few buckets even
   without any attacker.

Worked example

Take capacity m = 8 and insert three string keys using Python's built-in hashing:

# PYTHONHASHSEED=0 python3 this_file.py
# The seed is pinned ONLY so this example prints the same thing for you as it does here.
# Real deployments leave randomization ON: it is a hash-flooding defense.
keys = ["alice", "bob", "carol"]
m = 8
for k in keys:
    print(k, "-> bucket", hash(k) % m)

Output (actually run, PYTHONHASHSEED=0, reproducible across runs):

alice -> bucket 1
bob -> bucket 2
carol -> bucket 2

Note what actually happened: bob and carol both landed in bucket 2. Three keys into eight buckets collide more often than intuition suggests, and that is the point of this example rather than a flaw in it. alice is alone in bucket 1, so looking her up touches one bucket holding one entry. Looking up bob touches bucket 2, which holds two entries, so the table must compare against both. That is still O(1) on average, because the work per lookup depends on the length of ONE bucket, not on the size of the table.

If you run this without pinning the seed you will get different buckets every time, and on some runs all three keys share a bucket. If instead all three
happened to collide into the same bucket, the table would fall back to whatever collision-resolution
strategy it uses (chaining or open addressing, covered by their own question) and lookup would degrade
toward O(3) for that bucket, i.e. still fine at small n, but this is exactly the mechanism that turns
into O(n) at scale under bullet 1 or 2 above.

Trade-offs and pitfalls

A common junior mistake is to treat "hash tables are O(1)" as an unconditional fact rather than an
average-case property with named assumptions. A senior answer states the assumptions (uniform
hashing, bounded load factor, non-adversarial keys) up front and can point to at least one concrete
way each assumption can fail in production, which is exactly what separates this question from a
rote definition.

Direct answer

Assuming a prior middleware already authenticated the request and attached the caller's identity and role, this middleware's only job is authorization: does that role carry the required permission. Answer that from a local cache instead of a database round trip on the common path, and make sure the cache never serves a role's permissions past an explicit staleness bound once those permissions actually change.

Structured elaboration (approach)

1. Upstream auth assumption. request.user is already populated by an earlier layer; this decorator never authenticates, it only authorizes against an identity it trusts was already verified.
2. Permission check. Look up the required permission in the cached permission set for request.user's role; allow if present, deny otherwise.
3. Local cache. A dictionary keyed by role, storing the permission set alongside when it was fetched and which global version it was fetched under.
4. Cache invalidation, two strategies combined. TTL expiry bounds staleness even if an invalidation signal is ever missed. A monotonically increasing global version counter, bumped whenever any role's permissions change, gives near-immediate consistency: every cache entry is stamped with the version it was fetched under, and a version mismatch on read forces a refetch even before the TTL expires. The version approach also solves a subtler problem TTL alone doesn't: a permission change to a parent role in a hierarchy affects every role that inherits from it, and enumerating which cache keys that touches is error-prone, while bumping one counter invalidates all of them in one step.

Worked example (executed)

import time


class PermissionDenied(Exception):
    pass


class RolePermissionCache:
    def __init__(self, db_lookup, ttl_seconds: int = 60):
        self._db_lookup = db_lookup
        self._ttl_seconds = ttl_seconds
        self._entries = {}   # role -> (permissions, fetched_at, version)
        self._version = 0
        self.db_lookup_count = 0  # test instrumentation only

    def invalidate_all(self):
        # Call this from wherever a role's permissions actually change.
        # O(1): no need to know which cache keys are affected, including
        # transitively through role inheritance.
        self._version += 1

    def get_permissions(self, role: str) -> frozenset:
        now = time.monotonic()
        cached = self._entries.get(role)
        if cached is not None:
            permissions, fetched_at, version = cached
            fresh_enough = (now - fetched_at) < self._ttl_seconds
            version_current = version == self._version
            if fresh_enough and version_current:
                return permissions

        self.db_lookup_count += 1
        permissions = frozenset(self._db_lookup(role))
        self._entries[role] = (permissions, now, self._version)
        return permissions


def requires_permission(permission: str, cache: RolePermissionCache):
    def decorator(handler):
        def wrapped(request):
            role = request.user["role"]
            permissions = cache.get_permissions(role)
            if permission not in permissions:
                raise PermissionDenied(f"role={role!r} lacks permission={permission!r}")
            return handler(request)
        return wrapped
    return decorator


def run_demo():
    fake_db = {"editor": {"posts:read", "posts:write"}, "viewer": {"posts:read"}}

    def db_lookup(role):
        return set(fake_db.get(role, set()))

    cache = RolePermissionCache(db_lookup, ttl_seconds=60)

    class Request:
        def __init__(self, role):
            self.user = {"role": role}

    @requires_permission("posts:write", cache)
    def create_post(request):
        return "post created"

    results = []

    r1 = create_post(Request("editor"))
    results.append(("first call succeeds and hits DB once",
                     r1 == "post created" and cache.db_lookup_count == 1))

    r2 = create_post(Request("editor"))
    results.append(("second call is served from cache (no extra DB hit)",
                     r2 == "post created" and cache.db_lookup_count == 1))

    # Revoke posts:write from editor, then invalidate. Without invalidate_all(),
    # this next check would incorrectly still pass: the cache entry is only a
    # moment old, nowhere near the 60s TTL.
    fake_db["editor"].discard("posts:write")
    cache.invalidate_all()

    denied = False
    try:
        create_post(Request("editor"))
    except PermissionDenied:
        denied = True
    results.append(("after revocation + invalidate_all(), next call is denied",
                     denied and cache.db_lookup_count == 2))

    all_pass = True
    for name, passed in results:
        print(f"[{'PASS' if passed else 'FAIL'}] {name}")
        if not passed:
            all_pass = False
    print(f"\ndb_lookup_count={cache.db_lookup_count}")
    print(f"ALL_PASS={all_pass}")


if __name__ == "__main__":
    run_demo()

Output, from an actual run (python3 rbac_middleware.py):

[PASS] first call succeeds and hits DB once
[PASS] second call is served from cache (no extra DB hit)
[PASS] after revocation + invalidate_all(), next call is denied

db_lookup_count=2
ALL_PASS=True

The third case is the one that actually proves the invalidation works, not just that the happy path returns a plausible-looking answer: the permission is revoked in the fake database, invalidate_all() is called, and the very next request is denied without the cache dictionary ever being cleared by hand. If invalidation were broken, that call would incorrectly still succeed, since the entry is nowhere near its 60-second TTL.

Complexity and edge cases

A warm-cache permission check is O(1) average (one dictionary lookup, one set membership test). A cold cache or a post-invalidation lookup costs exactly one call to the underlying database lookup function, never more, regardless of how many permissions that role carries. Edge cases demonstrated above: a cold-cache miss, a warm-cache hit that provably skips the database, and a revoke-then-immediately-recheck sequence that provably does not skip it.

Trade-offs and pitfalls

• TTL alone leaves a real staleness window, up to the full TTL, after any permission change. Version-based invalidation alone leaves you exposed if the invalidation event itself is ever missed, for example a process that crashed before receiving a pub/sub message, or a race at deploy time. Combining both, as above, gives a hard upper bound on staleness from the TTL and fast propagation in the common case from the version check.
• In a real multi-instance deployment, invalidate_all() bumping an in-process counter only helps the one process where the change happened. The version needs to live somewhere shared, a version key in a fast external store like Redis, or a pub/sub broadcast that every instance subscribes to, or every other instance keeps serving stale permissions until its own local cache entries individually expire via TTL.
• This cache is keyed only by role, which is only correct if permissions genuinely depend on role alone. The moment permissions need to vary by tenant or by a specific resource for the same role, the cache key has to widen to include that dimension, or two tenants will silently share one cache entry meant for only one of them.

Direct answer

I treat it as a bounded bet rather than a leap of faith: size the learning cost against the expected payoff and how reversible adopting it would be, then run the cheapest possible probe before committing more time than that.

Structured elaboration

Sizing the bet: how many hours would it realistically take to learn enough to know if it works, versus what it could save, and is adopting it a one-way door (hard to back out of once other things depend on it) or easily reversible.

The cheap probe before committing: a strict, short timebox, often half a day, spent reproducing the actual problem I'm trying to solve and trying the new approach against it, not reading marketing material or a polished demo.

Comparing on a fixed, reproducible basis: running the same workload or test case against both the current approach and the new one, and writing down the setup and results so the comparison can be repeated later rather than relying on a vague impression of "it felt faster."

What I weigh beyond headline capability: integration cost, ongoing maintenance, and the noise it adds (a new dependency to patch, a new failure mode someone has to learn to recognize), since those often outweigh the exciting part of the pitch.

Kill criteria decided in advance: a specific condition that means I walk away, set before I start the probe, so I'm not tempted to rationalize a sunk-cost decision partway through.

Judging afterward whether it earned its place: at a set review point later, checking whether the original headline capability actually held up once it was running under real, not staged, conditions.

Worked example

I found a caching library that looked like it could fix a performance problem I was chasing. I gave myself a half-day timebox and reproduced the exact slow workload against both the current approach and the new library, writing down what I set up and what happened rather than trusting my memory of it. The result was mixed: it visibly reduced duplicate calls in the trace, but it added a dependency with thin documentation on its failure behavior. I'd decided my kill criterion in advance: if I couldn't get a reliable read on its failure modes within the timebox, I wouldn't adopt it before the deadline I was working against. I hit that limit, so I deferred adoption rather than rushing it in, but kept my notes so a future re-evaluation wouldn't start from zero.

Trade-offs and pitfalls

The most common failure here is letting the exploratory phase quietly run past its own timebox because the tool is interesting, or trusting a vendor's or blog's benchmark instead of reproducing it yourself on your own workload. The other is fixating on the headline capability and ignoring integration and maintenance cost until after you're already committed to it.

Direct answer. EXPLAIN shows you the plan the optimizer WOULD use and its estimated costs, without running the query. EXPLAIN ANALYZE actually executes the query and reports both the estimates and the real, observed numbers (actual rows, actual time, loop counts) side by side, which is what lets you see where the optimizer's model of the data was wrong.

Structured elaboration. Because EXPLAIN alone doesn't execute anything, it is safe to run against any query, including a write query or one you suspect might be catastrophically slow, and it costs essentially nothing. EXPLAIN ANALYZE actually runs the query end to end (some databases support a dry-run or rollback mode for writes, but by default assume it executes), so it takes as long as the query itself and has the query's real side effects. You reach for EXPLAIN ANALYZE specifically when you need the actual numbers, most commonly to compare "estimated rows" against "actual rows" at each node: a large gap there is one of the single strongest signals that statistics are stale, a predicate is more selective or correlated than the optimizer assumed, or a data distribution has shifted.

Worked example. For a query that filters on created_at in the last 7 days, EXPLAIN might estimate 5,000 matching rows from an index scan. Running EXPLAIN ANALYZE against the same query might show the same index scan node actually returning 500,000 rows. That gap (5,000 estimated vs. 500,000 actual) tells you the optimizer under-costed this branch of the plan and likely chose a downstream join algorithm (say, a nested loop) that only makes sense for the small estimate, not the real volume, which is a very different diagnosis than "the index scan itself is slow."

Trade-offs and pitfalls. Running EXPLAIN ANALYZE against an expensive query in production has a real cost: it fully executes the query, so a query that would normally time out or that writes data is not safe to blindly EXPLAIN ANALYZE without thinking about it first (a SELECT read against a replica, or wrapping a write in an explicit transaction you roll back, are common ways to make this safe). It's also worth remembering that EXPLAIN ANALYZE's timing numbers include the overhead of instrumentation itself, so absolute numbers can be slightly inflated versus a bare run of the query; the RELATIVE comparison between nodes, and between estimated and actual, is what actually matters.

Direct answer

In a checkout flow, keep synchronous only the sub-steps whose outcome the user or the next step must know before the transaction can be considered complete: inventory availability check and payment authorization. Everything that does not gate the "did this order succeed" answer, such as sending the confirmation email and recording analytics events, should be asynchronous, published as events once the order is durably created.

Structured elaboration

Apply a single test to each sub-step: "if this step fails or is slow, must the user's checkout fail or wait?" Payment authorization fails the test: if the card is declined, the order must not be placed, so it has to complete (or definitively fail) before the checkout response returns. Confirmation email and analytics both pass the test in the other direction: if the email provider is down, the order is still valid and the customer should not see an error; if the analytics pipeline is backed up, that has zero bearing on whether the customer got their item.

Effects of this split:

• User experience. The customer sees a fast, honest response: "order confirmed" as soon as payment clears, not "order confirmed, email pending" or a spinner while a marketing analytics call finishes. Moving email/analytics off the critical path directly lowers perceived latency, since the response no longer waits on the slowest of several unrelated systems.
• System correctness. Correctness now hinges only on the synchronous steps actually being atomic or safely retryable: payment authorization must be idempotent (a network retry must not double-charge) and the order record must not be marked "placed" unless payment is confirmed. The asynchronous steps cannot violate correctness of the order itself, because they consume from an event that is only published after the order is already valid; at worst, a failed email send means a customer does not get a receipt email, not that they have a wrong order.
• Error handling. Synchronous steps need explicit user-facing error handling (declined card, out-of-stock) because the user is waiting on the answer. Asynchronous steps need consumer-side error handling instead: retries with backoff, and a dead-letter queue (DLQ, a queue that holds messages a consumer could not process after exhausting retries) for a persistently failing email send, which an on-call engineer or automated remediation job can drain later without ever bothering the customer.
• Eventual consistency guarantees. The order itself is strongly consistent the moment checkout returns (it either happened or it did not). The order's "surrounding" state, such as "has the customer been emailed" or "has this purchase been counted in today's revenue dashboard," becomes eventually consistent: it will be true within some bounded window (seconds to low minutes, driven by consumer lag) but is not guaranteed true at the instant checkout returns. That gap needs to be a conscious guarantee you can state, not an accident: e.g., "confirmation email delivered within 5 minutes of order placement, monitored via consumer lag on the notifications topic."

Worked example

Sequence for a $75 order: (1) synchronously reserve inventory for the SKU and authorize payment for$75; if either fails, return an error to the user immediately and nothing else happens. (2) On success, write the order row and, in the same database transaction (or via the transactional outbox pattern, where an "OrderPlaced" row is written to an outbox table in the same commit and a separate relay publishes it), emit an "OrderPlaced" event. (3) Return "order confirmed" to the user at this point, without waiting on anything downstream. (4) A notifications consumer subscribed to "OrderPlaced" sends the confirmation email, retrying up to 3 times with backoff on transient send failures before landing the message in a DLQ. (5) An independent analytics consumer subscribed to the same event increments the day's revenue counter. Steps 4 and 5 run in parallel, are unaware of each other, and neither can block or fail step 1 through 3.

Trade-offs and pitfalls

The main pitfall is drawing the line by "which steps feel slow" rather than "which steps the user's success/failure outcome depends on"; a fast email send is still a UX and correctness bug if it is on the synchronous path, because it adds a dependency the checkout does not need. The opposite pitfall is making payment authorization asynchronous "to be consistent" with the rest of the flow: that forces the UI into an awkward "we'll email you when your payment clears" pattern for something users expect an immediate answer to, and it reopens the question of what state the order is in while payment is pending. A senior answer also flags that moving a step asynchronous introduces a durability requirement: if the order write and the event publish are not atomic, a crash between them can silently drop confirmation emails and analytics events for orders that did place successfully, which is exactly the failure mode the outbox pattern exists to close.

Direct answer

Analytics and business intelligence (BI) queries tolerate minutes of staleness in exchange for large latency and cost wins, so lean on materialized views and result caching aggressively, choosing the caching granularity (whole report, per-tile, per-query-result) based on how the dashboard is actually consumed.

Structured elaboration

• Materialized views: precompute and store the results of expensive aggregations on a schedule (or triggered by upstream data changes), so a dashboard read is a fast lookup against already-computed results rather than a live, expensive query against raw data.
• Result caching layers: cache the results of specific, frequently-run queries (a query-result cache keyed by the query and its parameters) for dashboards where the underlying data does not change often enough to justify a full materialized-view pipeline.
• Cache granularity: report-level caching (the whole dashboard's output) is simplest but coarse (any change forces a full recompute); tile-level (each widget/chart cached independently) allows partial invalidation when only some underlying data changed; query-result-level is the finest grain, useful when many different reports share underlying queries.
• Invalidation strategies for BI: time-to-live (TTL) is often sufficient here, since most BI use cases genuinely tolerate a bounded staleness window (minutes, sometimes hours); event-based invalidation (triggered by an upstream data-pipeline completion) is worth the added complexity specifically for dashboards where "as fresh as the last data load" matters more than a fixed time window; manual invalidation (an explicit refresh button) suits ad-hoc analysis tools where users want on-demand control.
• Cache warming/pre-computation: for dashboards viewed at predictable times (a morning operations review, a weekly business report), precomputing results just before that predictable access window avoids making the first viewer of the day pay the full, uncached computation cost.
• Balancing freshness, latency, and cost: the right TTL and caching granularity should map directly to how the business actually uses the dashboard, an operational dashboard checked continuously wants near-real-time and can justify more compute cost; a monthly strategic report tolerates hours of staleness and should be cached aggressively to save cost.

Worked example

A BI platform serving semantic-layer queries: for a query-result cache keyed by the query and its parameters, a report combining multiple underlying queries can serve most of its content from cache (queries that have not changed) while only recomputing the specific queries whose underlying data actually changed, rather than invalidating and recomputing the entire report on any single data update; this per-query granularity captures much of the tile-level caching benefit without needing the dashboard rendering layer itself to be cache-aware.

Trade-offs and pitfalls

Caching at the coarsest (whole-report) granularity for convenience, when the underlying data actually changes at different rates for different parts of the report, wastes the caching opportunity for the parts that rarely change and forces unnecessary staleness or unnecessary recomputation for the rest; choose granularity deliberately based on the actual update-rate heterogeneity within the report. Setting one TTL policy across every dashboard regardless of how it is actually used (operational versus strategic) either wastes freshness-driving compute cost where it is not needed, or under-serves freshness where it genuinely matters; tie the TTL choice to actual usage patterns.

Requirements: atomic transfer across shards at scale, prevent double-spend, high throughput.

Recommended protocol: hybrid of 2PC with optimistic concurrency and idempotent prepared operations.

Protocol outline:

1. Prepare phase (reservation): debit service obtains a distributed lock or creates a 'pending-debit' record on source shard and decreases available_balance via conditional update (WHERE available >= amount AND version=V). This is an optimistic operation with CAS.
2. Write enqueue: write a transfer intent event to a durable transaction log (or message queue) with idempotent transfer_id.
3. Commit phase: consumer executes credit on destination shard and then marks transfer_id committed; finally source finalizes by marking pending-debit committed and subtracting reserved funds from balance.
4. If failure before commit, compensation: if debit reserved but not committed within timeout, a compensator cancels reservation (releases funds) after verifying idempotency.

Prevent double-spend:

• Use unique transfer_id and conditional updates (optimistic concurrency) on both shards; source reservation prevents reuse.
• Persist transfer state centrally or via quorum to avoid lost intents.

Throughput considerations:

• Avoid synchronous 2PC blocking: make prepare local to source (fast), enqueue event, and let background workers finalize commit asynchronously but atomically with idempotence guarantees.
• Parallelize by sharding and batching reconciliations; use non-blocking distributed locks (short TTLs).

Rollback & recovery:

• On coordinator failure, workers detect stale 'in-progress' transfers by timeout and retry/compensate using idempotent APIs.
• Periodic reconciliation job scans transfer log and repairs incomplete transfers.

This hybrid preserves atomicity via reservation + idempotent commit, avoids long two-phase locks, and scales by batching and asynchronous commit with robust recovery.

Situation & summary
For a backend developer designing a cloud-managed DB with millions of records and frequent inserts + range scans, pick between B-tree, skip-list, and append-only/compaction (LSM-style) by trading read/write latency, maintenance, and operational cost.

B-tree (e.g., Postgres B-tree)

• Read/write: Balanced disk-oriented tree — good random reads and reasonable writes. Inserts update tree pages; random writes and occasional page splits.
• Maintenance: Requires page splits, rebalancing, and VACUUM to reclaim space; careful WAL tuning.
• Range-scan latency: Excellent — contiguous leaf pages give low-latency sequential scans.
• Cloud suitability: Mature, predictable performance; works well for transactional workloads and cloud-managed RDBMS.

Skip-list (in-memory or on-disk variants)

• Read/write: Very fast in-memory inserts/reads (O(log n)); on-disk variants less common, random I/O cost similar to B-tree.
• Maintenance: Simpler concurrency (lock-free implementations), lower code complexity for in-memory indexes; persistence needs compaction or snapshots.
• Range-scan latency: Good for in-memory contiguous traversals; on-disk can be fragmented.
• Cloud suitability: Great for in-memory caches (Redis uses skip-list for sorted sets). Less ideal as primary durable on-disk index.

Append-only sorted logs + periodic compaction (LSM, e.g., RocksDB, LevelDB)

• Read/write: Excellent write throughput (sequential WAL and memtable flushes); write amplification from compaction.
• Maintenance: Compaction is the main cost (CPU, I/O); background compaction tunable but can cause CPU/I/O spikes and tail-latency.
• Range-scan latency: Good when data is compacted into large sorted SSTables; reads may need merging across levels causing higher point-read latency unless bloom filters and caches used.
• Cloud suitability: Excellent for high-ingest workloads, time-series, and tiered storage in cloud-managed NoSQL stores; requires operational tuning for compaction and resource isolation.

Trade-offs & recommendation

• If low-latency range scans and predictable transactional consistency are primary: B-tree.
• If write-heavy, high-throughput ingestion with acceptable compaction overhead: LSM.
• If mostly in-memory sorted sets or simple concurrency needs: skip-list.
• In cloud-managed DBs, prefer LSM for scale/write throughput (used by managed NoSQL) or B-tree for OLTP (managed RDBMS). Plan for compaction QoS, caching, and monitoring.

Direct answer

Process the iterator in fixed-size chunks and accumulate counts into a single running hash map (a Counter) that lives for the whole run, rather than ever materializing the full token sequence as a list. Peak memory becomes proportional to the chunk size plus the number of distinct tokens (not the total number of tokens processed), which is exactly what "cannot keep all tokens in memory simultaneously" requires. For scale beyond a single machine's memory even for the running counts themselves, the same idea extends outward: spill partial counts to disk or a database and merge them, or hand the aggregation to an external tool built for exactly this.

Structured elaboration

Why a single running counter, not per-chunk lists, is the key move. The chunk size controls how many raw tokens are held at once, but the thing that actually needs to survive across chunks is the aggregate count, not the raw tokens themselves. A Counter accumulated with .update(chunk) after each chunk keeps memory bounded by the chunk size (transient) plus the number of distinct tokens seen so far (persistent, but typically far smaller than the total token count for realistic text), which is the same "count of distinct values, not count of total values" property that makes hash-map-based counting memory-efficient in general.

Code patterns for the streaming read itself. In Python, this looks like iterating the source with for chunk in iterator_of_chunks: ... rather than list(iterator) up front; if the source is a file, pandas.read_csv(path, chunksize=N) or a plain line-by-line file read serves the same purpose, only ever holding one chunk in memory. The point is structural: never call an operation that forces the entire stream to materialize (a bare list(...), a sort() over the whole thing, or a pandas.concat of every chunk) before counting.

External tools for when even the running counts don't fit, or true big-data scale is needed. A few standard building blocks, worth naming by name since the question explicitly asks for external tools:

• The classic Unix pipeline sort tokens.txt | uniq -c performs exactly this kind of streaming aggregation using external (disk-backed) sort, which is how shell tooling has solved "count occurrences in a file too big for memory" for decades.
• A disk-backed key-value store (Python's shelve or dbm modules, or a lightweight embedded database like SQLite) can hold the running counts on disk instead of in a Python dict, trading memory for disk I/O when even the distinct-token count is too large to fit in RAM.
• For a genuinely distributed, multi-machine scale, a framework like Apache Spark or Dask expresses the same map-then-reduce shape (count within each partition, then merge partition-level counts) across a cluster instead of a single process's chunks.

Scoping the "at massive scale" framing honestly. For inputs that must merely avoid holding everything in memory AT ONCE on one machine (the question's actual framing), chunked accumulation into one running Counter is sufficient and is the answer worth leading with. Approximate, sub-linear-memory structures (like a Count-Min Sketch, which trades exact counts for a small, fixed memory footprint with bounded overcounting error) exist for the harder case of needing frequency estimates over a token universe too large even to enumerate distinctly, but designing such a structure is its own topic (owned by the hashing-and-hash-tables domain, not this one); it is worth naming as the next tier of solution if pressed, without building one here.

Worked example

Full runnable code with a pinned random seed and pinned parameters, comparing the chunked streaming approach against materializing the whole stream (the latter only possible here because the demo stream is deliberately small; this is exactly the comparison the chunked approach exists to avoid needing at real scale):

import random
from collections import Counter

random.seed(42)  # pinned so a reviewer re-running this gets the same stream

VOCAB = [f"tok{i}" for i in range(20)]  # small closed vocabulary for a reproducible demo


def token_stream(n_tokens):
    """Simulates a stream too large to hold in memory as a list: a generator
    that yields one token at a time, pinned by the seed above."""
    for _ in range(n_tokens):
        yield random.choice(VOCAB)


def chunked_frequency_count(stream, chunk_size):
    """Bounded-memory frequency counting: accumulate counts in a single
    running Counter (O(vocabulary size) memory, not O(stream length)),
    processing the stream in fixed-size chunks so peak memory never holds
    more than `chunk_size` raw tokens plus the running counter at once."""
    running_counts = Counter()
    chunk = []
    chunks_processed = 0
    for tok in stream:
        chunk.append(tok)
        if len(chunk) == chunk_size:
            running_counts.update(chunk)
            chunk.clear()
            chunks_processed += 1
    if chunk:
        running_counts.update(chunk)
        chunks_processed += 1
    return running_counts, chunks_processed


if __name__ == "__main__":
    n_tokens = 10_000
    chunk_size = 500

    random.seed(42)
    ground_truth = Counter(token_stream(n_tokens))

    random.seed(42)
    chunked_result, n_chunks = chunked_frequency_count(token_stream(n_tokens), chunk_size)

    print(f"n_tokens={n_tokens} chunk_size={chunk_size} chunks_processed={n_chunks}")
    print("chunked result matches ground truth:", chunked_result == ground_truth)
    print("peak resident tokens per chunk (bounded):", chunk_size, "vs full stream:", n_tokens)
    print("top 5 by frequency (chunked):", chunked_result.most_common(5))
    print("top 5 by frequency (ground truth):", ground_truth.most_common(5))

Output (actual run):

n_tokens=10000 chunk_size=500 chunks_processed=20
chunked result matches ground truth: True
peak resident tokens per chunk (bounded): 500 vs full stream: 10000
top 5 by frequency (chunked): [('tok14', 533), ('tok2', 525), ('tok4', 523), ('tok15', 523), ('tok17', 515)]
top 5 by frequency (ground truth): [('tok14', 533), ('tok2', 525), ('tok4', 523), ('tok15', 523), ('tok17', 515)]

With n_tokens=10,000 and chunk_size=500, only 20 chunks of 500 raw tokens each were ever held at once, yet the chunked result is bit-for-bit identical to counting the entire materialized stream at once (both random-seeded identically for a fair comparison), which is exactly the property that justifies using the chunked approach instead of the simpler materialize-then-count version at real scale.

Trade-offs and pitfalls

• Materializing the full stream first (list(iterator) then Counter(...)) is simpler to write and was used above only as a ground-truth cross-check; it is precisely what the question rules out, since it requires holding every token in memory at once.
• The running Counter itself still grows with the number of DISTINCT tokens seen, not the total count; if the vocabulary itself is unbounded or extremely large (arbitrary user-generated strings rather than a fixed token vocabulary), the running counter can itself become the memory bottleneck, which is exactly where spilling partial counts to disk or reaching for an approximate structure becomes necessary rather than optional.
• Choosing a chunk size is a real tuning knob: too small and the per-chunk overhead (function calls, dict updates) dominates; too large and peak memory creeps back up toward the full-stream size. The right answer depends on available memory and token size, and naming this trade-off explicitly (rather than picking an arbitrary chunk size and moving on) is part of a complete answer.
• External sort-based tools like sort | uniq -c guarantee correctness regardless of scale but at the cost of an O(n log n) sort rather than the O(n) a hash-based running count achieves; they are the right choice specifically when memory (not time) is the binding constraint, or when the tool is already part of an existing pipeline.
• Approximate structures (Count-Min Sketch and similar) trade exact counts for fixed memory and bounded error; naming that this trade-off exists is appropriate depth for this question, but designing the structure itself belongs to a different topic.