Netflix Staff Backend Engineer Interview Preparation Guide

Direct answer

The core tension is that the backfill and the live sync are both consuming the same 10 requests/second budget from the same API, so the design has to explicitly partition that budget rather than let the two compete unpredictably, while making the backfill itself resumable and idempotent so a multi-day job surviving several restarts still converges on a correct, non-duplicated result.

Structured elaboration

Partitioning the rate-limit budget

• Reserve a fixed share of the 10 req/s for live sync (enough to keep it comfortably within its freshness service-level agreement (SLA)) and let the backfill use the remainder, rather than a naive "whoever gets there first" free-for-all between the two workloads.
• A shared, centralized rate limiter (not one limiter per worker) is required here: independent per-worker limiters cannot see each other's usage and will collectively exceed the source's real cap.

Parallelization strategy

• Parallelize across accounts, not within a single account's page sequence, since pages within one account's history typically must be walked in order for correct checkpointing, while different accounts are fully independent of each other.
• Size the worker pool to the rate-limit budget available to the backfill, not to raw compute capacity; more workers than the rate limit can support just means more of them sitting idle waiting for a token.

Checkpointing for resumability

• Checkpoint per account, independently: persist each account's furthest-completed page or cursor so a restart resumes only the accounts still in progress, not the ones already fully backfilled.
• Persist checkpoints frequently enough (after every page, not just at the end of an account) that a crash loses at most one page of already-fetched-but-uncommitted work per in-progress account.

Guaranteeing eventual consistency without duplicates

• Every record written by either the backfill or the live sync goes through the same idempotent upsert path, keyed on the record's own stable ID, so it does not matter which of the two processes writes a given record first or whether both happen to write it.
• Define a clear ordering rule for the rare case where both processes touch the same record concurrently (for example, "whichever write carries the later updated_at wins"), so the result is deterministic rather than a race.

Worked example

2,000 accounts need two years of history backfilled, at a shared 10 req/s budget, with 3 req/s reserved for live sync, leaving 7 req/s for the backfill. A pool of 7 backfill workers, each holding one token from a centralized rate limiter, is assigned accounts from a queue; each worker walks one account's full page history, checkpointing its cursor after every page, before picking up the next account from the queue. If the process crashes after 1,200 of the 2,000 accounts are fully done and a 1,201st is half-complete, a restart re-reads the checkpoint table, skips the 1,200 complete accounts entirely, resumes the 1,201st from its last saved cursor rather than page 1, and continues the remaining 799 from scratch. Throughout, both the backfill and the live sync write through the same upsert-by-record-ID path, so if live sync happens to ingest a very recent change to an account the backfill has not yet reached, the backfill's later arrival at that same record, carrying older data, does not overwrite the newer one, because the upsert conflict rule explicitly prefers the later updated_at.

Trade-offs & pitfalls

• Splitting the rate-limit budget statically (a fixed 3/7 split) is simple but can starve one workload if the actual demand shifts, for example if live sync traffic spikes; a smarter allocator that lets the backfill temporarily borrow idle live-sync capacity is more efficient but meaningfully more complex to build and reason about correctness for.
• Checkpointing at the account level but not the page level within an account means a crash can lose up to one full account's progress, not just one page; the finer-grained the checkpoint, the less repeated work a crash costs, at the price of more frequent writes to the checkpoint store.
• The "later updated_at wins" conflict rule assumes the source's own timestamps are trustworthy and consistent across accounts and over the two-year backfill window; if that assumption does not hold for some historical data, you need a different, explicit tie-breaking rule rather than silently trusting a timestamp that might be wrong.
• A single centralized rate limiter is also a single point of contention; at very high worker counts it can itself become a bottleneck, though at 7 concurrent workers against a 7 req/s budget this is not yet a real concern.

Making the case

I'd translate the backend risk into terms executives already care about: revenue and customer trust, not "tech debt." Rather than arguing abstractly for optimization, I'd show a concrete projection, for example: at the current growth rate, capacity headroom runs out in about six weeks, which lines up with a known peak sales period, and a breach there risks visible outages during the highest-revenue window of the year.

Data over assertion

I'd bring the actual numbers: current growth rate, current headroom, and the projected date of breach, so the ask isn't "trust me, this is risky" but "here's when this becomes a real outage if nothing changes."

Quantifying both sides

I'd frame it explicitly as a trade: the cost of doing the optimization is two sprints of delay on the feature; the cost of not doing it is the risk of an outage during peak traffic, which usually carries a much larger, if less certain, cost in lost revenue and customer trust.

Middle ground if they won't fully agree

• Partial postponement: delay the feature by one sprint instead of two, and run a scoped-down version of the backend work in parallel rather than the full plan.
• Parallel tracks: bring in short-term help (a contractor or a borrowed engineer) to run both streams at once instead of sequencing them.
• Conscious risk acceptance: ship the feature as planned, but only with a documented risk, a hard-committed kill switch, and heavy monitoring so if things start to go wrong during peak, there's a fast, pre-planned way to pull back.

The key move

Rather than presenting this as an ultimatum, I'd get product and execs to co-own the risk assessment, walking through the projection together and asking them to help pick the trade-off, since a decision they helped shape is one they'll actually stand behind if things get tight later.

Direct answer

Build both functions on a level-order traversal, a breadth-first search (BFS) that visits nodes queue-first, one level at a time, and write an explicit null marker for every missing child slot, not just at leaves. That pairing is what makes reconstruction unambiguous: because every real node always contributes exactly two child slots (present or null) to the next level, the deserializer can walk the same queue-driven process and know exactly which token belongs to which parent's left or right slot, without storing any indices.

Structured elaboration

Why explicit nulls, and why for every missing child

A traversal that only records the values it visits (skipping null children silently) cannot be reversed: two different shapes can share the same sequence of present values. Recording a placeholder ('#' below) for every missing child slot removes that ambiguity, because it lets the deserializer track, level by level, exactly how many real nodes exist to enqueue next.

BFS vs. depth-first search (DFS) as the traversal choice

BFS (level-order) naturally maps to a flat array where each node's two children are the next two not-yet-consumed tokens, which is convenient to stream level-by-level and easy to reason about. A preorder depth-first search (DFS, visiting root then left subtree then right subtree) with the same null-marker convention works just as well and tends to produce a shorter string for skewed or sparse trees, since it never has to emit placeholders for an entire unexplored level, only along the path actually walked. The two are interchangeable in principle; BFS is used here because it composes naturally with only trimming trailing nulls (once the queue drains, nothing after it can matter).

What must be encoded about missing children

For every dequeued real node, both potential child slots must be represented, either a value token or the null marker, in a fixed, agreed order (left before right). Skipping this for anything but a genuinely empty subtree (where the marker sequence would just never be examined) breaks the correspondence between "the next unread token" and "the next child slot to fill."

Worked example

Approach

Serialize by BFS: push nodes onto a queue, emit each node's value or '#' for None, and enqueue both children (as None placeholders too) so the null markers land at the right position. Trailing '#' tokens can be trimmed since the deserializer's queue empties before it would ever need them. Deserialize by replaying the same queue discipline: read children two at a time for the next node pulled off the queue.

from collections import deque

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

def serialize(root):
    if root is None:
        return ''
    out = []
    q = deque([root])
    while q:
        node = q.popleft()
        if node is None:
            out.append('#')
            continue
        out.append(str(node.val))
        q.append(node.left)
        q.append(node.right)
    while out and out[-1] == '#':
        out.pop()
    return ','.join(out)

def deserialize(data):
    if not data:
        return None
    parts = data.split(',')
    root = Node(int(parts[0]))
    q = deque([root])
    i = 1
    while q:
        node = q.popleft()
        if i < len(parts) and parts[i] != '#':
            node.left = Node(int(parts[i]))
            q.append(node.left)
        i += 1
        if i < len(parts) and parts[i] != '#':
            node.right = Node(int(parts[i]))
            q.append(node.right)
        i += 1
    return root

def to_tuple(node):
    if node is None:
        return None
    return (node.val, to_tuple(node.left), to_tuple(node.right))

#        1
#       / \
#      2   3
#         / \
#        4   5
#           /
#          6
n6 = Node(6)
n5 = Node(5, n6, None)
n4 = Node(4)
n3 = Node(3, n4, n5)
n2 = Node(2)
n1 = Node(1, n2, n3)

s = serialize(n1)
print("serialized:", s)
print("round-trip matches:", to_tuple(deserialize(s)) == to_tuple(n1))

This prints:

serialized: 1,2,3,#,#,4,5,#,#,6
round-trip matches: True

Key points

• Trimming only trailing '#' tokens is safe: everything after the last real node in level order can never be dequeued and read.
• Casting each token back to int(...) on the way in matters; leaving values as raw strings would silently change the tree's data type on round-trip.
• The same encoding handles duplicate values across nodes without issue, since reconstruction is positional, not value-based.

Complexity

Time: $O(n)$ for both serialize and deserialize, each node is visited once. Space: $O(n)$ for the queue and the output token list (the queue holds at most one level's worth of nodes at a time, bounded by $n$ in the worst case of a very wide tree).

Edge cases

• Empty tree: serialize(None) returns '', and deserialize('') returns None.
• Single node: no children tokens are emitted at all after trimming.
• Fully left-skewed (or right-skewed) tree: verified above with a 3-node left chain, serializing to 1,2,#,3 and round-tripping correctly, the intermediate '#' for each node's missing right child is essential here and is not trimmed because it is not trailing.

Trade-offs & pitfalls

If node values can themselves contain the delimiter character (a comma) or collide with the null marker's own text, the format breaks; production code should length-prefix each token or escape delimiters rather than assume values are delimiter-safe. A common wrong turn is marking nulls only for leaf children, or only at the very end of the traversal, either under-specifies the shape and produces silently wrong reconstructions for anything other than a perfect binary tree. For very large trees that cannot fit in memory as a single string, chunked, level-by-level I/O (write and read one level's tokens at a time) preserves the same logic while bounding memory to one level's width rather than the whole tree.

Direct answer
Culture fit asks whether you already share a team's existing norms and behaviors; culture add asks what you would bring that the team does not already have. I would describe myself mostly as a culture add: I share the fundamentals a team needs to trust me (reliability, candor, respect for other people's time), but the useful thing I offer beyond that is a genuinely different working background rather than a mirror of the team that is already there.

Structured elaboration

1. Define both terms precisely before answering for yourself. Culture fit is about alignment on shared behaviors and values: does this person operate the way we already operate. Culture add is about complementary difference: does this person's background, working style, or perspective fill a gap the team doesn't currently have.
2. Explain why the distinction matters, not just define it. A team optimized purely for fit tends toward groupthink: everyone reasons the same way, so blind spots go unchallenged and the same kinds of mistakes recur. A team that only adds without any shared fit becomes uncoordinated: people can't predict each other's reasoning enough to move fast together. The healthy target is fit on a small number of load-bearing behaviors (honesty, follow-through, respect) plus deliberate add on everything else.
3. Give a genuine, specific example of your own add, not a generic trait. Vague claims ("I bring diverse perspectives") are the single most common failure mode here; a strong answer names the concrete gap and the concrete evidence.
4. Anticipate the natural follow-up: how do you know your difference is actually useful, versus just different for its own sake. The answer is to point at a specific decision, disagreement, or piece of feedback that changed because of the difference you brought, not just a credential or background fact.

Worked example
Suppose your last two teams were both product engineering teams building consumer-facing features, and the team you're interviewing for is mostly staffed by engineers with that same background. Your own prior role was on a data-platform team, closer to the systems that feed those consumer features than to the features themselves. A concrete add-story: in a past project, a product team wanted to ship a new recommendation feature quickly; because of your platform background, you asked a question the rest of the team hadn't raised (whether the upstream data pipeline's freshness guarantees actually matched what the feature's UI implied to users), which surfaced a real gap between a 24-hour batch refresh and a UI copy that said "updated just for you." The team fixed the copy and adjusted the refresh cadence before launch rather than after a user complaint. That is a genuine add: a different background produced a question the existing team composition was less likely to ask on its own, and it changed a real outcome.

Trade-offs & pitfalls
The common failure is answering only the definitional half (correctly explaining fit versus add) and then, when asked for a personal example, retreating to generic self-description ("I'm a good communicator", "I care about quality") that any candidate could say and that does not actually demonstrate difference. A second pitfall is overcorrecting into implying you don't fit at all; the strongest answers are explicit that you also share the small set of behaviors every functioning team needs, and that add is about everything on top of that baseline, not a replacement for it.

Direct answer

For 10k events/sec with at-least-once delivery and per-user ordering across email and push, partition by user id so every event for a given user always lands on the same ordered partition and is processed by one consumer at a time. Deduplication, backpressure, and multi-region replication are then layered on top of that partitioning choice rather than around it.

Structured elaboration

Components. Ingress producers publish NotificationRequested events carrying user_id, channel (email or push), and the payload. A partitioned event bus, keyed on user_id, sits between producers and channel-specific consumer groups: one group for email, one for push, each scaled independently. Per-channel delivery workers call the respective provider. A dedup store and a cross-region replication layer sit alongside the bus.

Achieving per-user ordering. Hash user_id to a fixed number of partitions and route every event for that user to the same partition. Within a partition, a single consumer processes events strictly in arrival order, it does not start event N+1 until event N is acknowledged (or is using only a small bounded in-order window, not arbitrary concurrency). This gives ordering per user without requiring a global order across all 10k events/sec, which would be both unnecessary and a throughput bottleneck.

Deduplication strategy. At-least-once delivery means a consumer crash-and-retry, or a producer retry after a network timeout, can each cause a duplicate. Every event carries an idempotency key the producer assigns once at creation (a user id plus a monotonic sequence, or a UUID, a universally unique identifier, generated once and never regenerated on retry). Before a delivery worker actually sends, it performs a conditional check-and-set against a dedup store keyed on that id, with a time-to-live comfortably longer than the maximum expected redelivery delay. If the key already exists, the worker skips the send and still acknowledges the event, it has already been delivered from the pipeline's point of view.

Backpressure handling. Each channel's consumer group scales on its own lag metric, a slow push provider should not stall email delivery and vice versa, and a bounded per-partition in-flight window caps how many unacknowledged events a consumer holds at once. A stuck downstream call blocks further progress on that one partition (preserving order) without unboundedly growing memory across the whole system.

Multi-region replication. Replicate the partitioned bus across regions so a regional outage does not stop delivery, and keep two things consistent across the replica: the partition-key-to-partition mapping (so per-user ordering survives a failover) and the dedup store (replicated or shared, otherwise failing over to a region with a cold dedup cache reintroduces duplicates the local store would otherwise have caught).

Worked example

Targeting roughly 500 events/sec per partition, chosen so a single consumer with typical provider-call latency and a modest in-flight window can keep up without becoming the bottleneck, 10,000 events/sec needs at least:

Route by hash(user_id) mod 20. A user who generates a disproportionate share of the traffic becomes a hot key on their one partition; since ordering is a per-user contract, that user's partition assignment cannot be split further without breaking their own ordering guarantee. The standard remediation is to rate-limit at the producer for that one user (cap and shed excess volume) rather than to try to rebalance partitions around them.

Trade-offs and pitfalls

• Hashing on a low-cardinality key, say tenant instead of user, preserves ordering at the wrong granularity and creates much hotter partitions.
• At-least-once delivery plus no explicit idempotency key is the classic bug: it is tempting to dedupe on payload content, but two legitimately different events with identical payloads then collapse into one silently. Always dedupe on an explicit event id, not content.
• Blocking a whole partition on one slow user degrades every other user sharing that partition. A bounded in-flight window with a timeout and a dead-letter path prevents one pathological event from stalling the partition indefinitely.
• Replicating the event bus across regions but not the dedup store means a failover reintroduces duplicates exactly when the system is already under stress.

Direct answer: Make a service's consistency semantics explicit by putting them directly in the response contract, freshness/staleness indicators, versioning fields clients can compare across requests, and well-defined error codes for conflicting updates, so a client can reason about what it received without having to guess or assume strong consistency by default.

Structured elaboration

Staleness indicators. Every response that could be stale carries an explicit field or header stating how current it is, e.g. X-Data-As-Of: <timestamp> or a freshness_seconds: 12 field, so a client (or a human debugging an issue) never has to assume freshness, it's stated. For responses served from a cache or a lagging replica, this lets a client decide whether to trust the data as-is, prompt a refresh, or fall back to a stronger-consistency read for that specific case.

Versioning fields. Every mutable resource returns a version token (a simple counter, an ETag-style hash, or a causal/vector-clock-style token) that the client can carry forward, both to detect whether a resource has changed since it last saw it (comparing versions cheaply, without re-fetching full content) and to pass back on a write as an optimistic-concurrency check (a conditional update, "apply this change only if the version I'm updating from matches what you currently have").

Error codes for conflicting updates. When a write's version-based precondition fails (someone else updated the resource since the client last read it), the API returns a specific, well-documented error code (e.g. 409 Conflict with a machine-readable reason like version_mismatch), not a generic failure, distinguishing "your update conflicted with a concurrent change" from other failure classes (validation error, permission error, transient server error) that a client would want to handle very differently (retry with fresh data vs. surface a validation message vs. back off and retry the same request).

Dispute/reconciliation endpoints. For domains where a client (or the system itself) might detect an apparent inconsistency it can't resolve on its own (two replicas disagreeing, a value that looks wrong given what the client expects), a dedicated endpoint lets a client (or an internal reconciliation job) flag the specific record for investigation or force a fresh, strongly-consistent read to resolve the ambiguity, rather than the client having no recourse beyond guessing.

Worked example. A product-catalog API returns:

{
  "product_id": "P-4471",
  "price_cents": 2999,
  "version": "v17",
  "data_as_of": "2026-07-23T10:15:32Z",
  "freshness_bound_seconds": 30
}

A client updating the price sends PATCH /products/P-4471 with If-Version: v17 in the request; if another client updated it to v18 in the meantime, the server returns 409 Conflict {"reason": "version_mismatch", "current_version": "v18"}, and the client's UI can show "this item changed since you loaded it, refresh to see the latest" rather than silently overwriting the concurrent change or failing with an unhelpful generic error.

Trade-offs and pitfalls. A common mistake is exposing versioning and staleness fields but leaving the actual CONFLICT-HANDLING contract vague (just returning a generic error on any write failure), which pushes the hard decision of "how should I actually handle this" onto every client integrator individually, a well-designed API makes the intended CLIENT behavior clear from the error code and reason alone (retry with fresh data vs. surface to the user vs. treat as a genuine failure), not just the fact that something went wrong.

Direct answer

Treat each supported release as a frozen snapshot of the docs, keep one moving "latest" copy, and make every page announce which version it describes. Readers on old releases land on the docs that match what they run, and anything they might mistake for current carries a clear banner and points to the newer page. Version the reference and how-to pages by release, and keep conceptual overviews shared unless they truly diverge.

Structure

1. Docs live in the same repository as the code (docs-as-code, meaning documentation stored and built like source code). Each release branch or tag has its own docs, so a doc fix can be back-ported (copied onto older supported versions) with the code fix. A release branch is a long-lived branch holding one released version so it can still get fixes; a tag is a permanent label on one commit.
2. Publish a version selector and stable URLs. For example /docs/latest/, /docs/3.2/, /docs/3.1/. Tools built for this include Docusaurus (its docs:version command snapshots the current docs), mike for MkDocs (mike deploy publishes a version; MkDocs is a static site generator that turns Markdown into a website), and Read the Docs (a hosted service that builds docs from your branches and tags). The tool matters less than the rule. If you have no tool yet, Docusaurus is an easy start because versioning is built in; use mike if you already run MkDocs; Read the Docs suits open-source projects that want hosted builds.
3. Banners on old versions: "You are reading docs for 3.1. The latest version is 3.2." linking to the equivalent page if one exists.
4. Search-engine hygiene. Point old versions' canonical link (the tag telling search engines which URL is the preferred copy) at the latest page, or mark them noindex (an instruction telling search engines not to list the page), so a search does not land people on outdated instructions.
5. Support policy tied to docs. Fix errors in supported versions (say, the last two releases). Older versions are frozen, labelled archived, and not edited.
6. Migration path. Each release ships an upgrade guide (what changed, what breaks, how to migrate) and a changelog (the dated list of changes per release). Pages whose behaviour changed link to it.

Which content gets versioned

Worked example

Release 3.2 renames the setting max_conn to pool_size. In the 3.2 docs the reference page documents pool_size, and the how-to says "Set pool_size". The 3.1 snapshot still says max_conn, with the banner. The upgrade guide has an entry: "3.2: max_conn is renamed pool_size; the old name works until 4.0 and logs a warning." A reader on 3.1 googles max_conn, arrives at the 3.1 page, sees the banner, and finds the migration note one click away. Without versioning, they would see 3.2 text and set a name their release ignores.

Trade-offs and pitfalls

• Copying the whole docs tree per release is simple but multiplies review work. Mitigate with a check that a fix to latest raises a "back-port?" prompt for supported versions.
• Conditional text ("in 3.1 only") on one page avoids duplication for small differences but gets unreadable past two or three variants. Snapshot when differences pile up.
• Broken links between versions are common; run a link checker (a tool that follows every link and reports ones that lead nowhere) per version in CI.
• What would change my call: for a hosted service with one live version, version only the API (by API version) and keep a dated changelog instead of full snapshots.

A 99.9% freshness SLA on derived dashboard metrics needs to be decomposed into SLIs that each capture a different stage where freshness could be lost, since a single blended "is it fresh" number hides WHERE in the pipeline a delay is actually occurring.

Structured elaboration

Four SLIs: (1) source-to-ingestion lag - time from the source event occurring to it landing in the raw ingestion layer; (2) ingestion-to-transform lag - time from raw ingestion to the derived-metric computation completing; (3) end-to-end freshness - the combined total, source event to dashboard-visible metric, which is the number that actually maps to the 99.9% SLA commitment; (4) computation success rate - proportion of scheduled metric-computation runs that complete successfully at all, since a freshness number computed only from SUCCESSFUL runs silently ignores runs that failed entirely, which is itself a freshness (and correctness) problem.

Worked example

SLO: 99.9% of end-to-end freshness measurements land under a defined threshold (e.g. under 10 minutes) over a 30-day rolling window, with the three component SLIs (source-to-ingestion, ingestion-to-transform, computation success rate) tracked as diagnostic breakdowns rather than separately-committed SLAs. If the end-to-end SLI degrades, the three component SLIs let you immediately localize whether the delay is happening at ingestion (a source-system problem) or at transform (a compute-pipeline problem), without which you'd only know "it's slow" with no actionable next step.

Trade-offs and pitfalls

Reporting only the end-to-end number without the component breakdown is fine for the customer-facing SLA report but nearly useless for diagnosing an actual regression internally; both views need to exist, aimed at different audiences. It's also worth being careful about how the computation-success-rate SLI interacts with the freshness SLI: a completely FAILED computation run has no freshness reading at all (there's no metric to measure the lag of), so it must be explicitly counted against the SLO as a worst-case freshness violation, not silently excluded from the freshness average simply because it produced no valid data point to measure.

Direct answer

A collection of n labeled nodes and a list of undirected edges forms a valid tree exactly when two conditions both hold: it has exactly $n - 1$ edges, and it is fully connected (every node reachable from every other). Either condition alone is insufficient (fewer than $n-1$ edges guarantees disconnection regardless of arrangement; exactly $n-1$ edges can still contain a cycle while leaving some other part of the graph disconnected), so the efficient check is: first reject immediately if the edge count is not exactly $n-1$, then use Union-Find to confirm both that no cycle exists (every union call actually merges two DIFFERENT sets) and, as a side effect, that the whole graph ends up as one connected component.

Structured elaboration

Why both conditions are needed, and why checking edge count first is a useful short-circuit. A tree on n nodes has exactly n-1 edges by definition (this is a standard graph-theory identity: a connected acyclic graph on n nodes always has exactly n-1 edges, and conversely any connected graph with exactly n-1 edges is automatically acyclic). Checking the edge count first is an $O(1)$ short-circuit: if len(edges) != n - 1, the input cannot be a tree no matter what the edges look like, so there is no need to run Union-Find at all in that case. Once the count matches, this identity guarantees that "connected" and "acyclic" become equivalent checks: given exactly n-1 edges, the input is a tree if and only if it is connected, and it is connected if and only if it is acyclic. That means a single Union-Find pass that fails on the first redundant union (an edge whose two endpoints are already in the same set, meaning it would create a cycle) is sufficient: if the graph is not fully connected while having exactly n-1 edges, at least one cycle must exist elsewhere in the edge list to "use up" an edge that a genuine spanning tree would have needed to reach every node, which the union-conflict check will catch.

Algorithm:

1. If len(edges) != n - 1, return False immediately.
2. Initialize Union-Find over n nodes.
3. For each edge (u, v): if u and v are already in the same set, a cycle exists (or u == v, a self-loop, which is a degenerate cycle), return False. Otherwise, union them.
4. If every edge unions successfully, return True.

Complexity. $O(n \cdot \alpha(n))$, or effectively $O(n)$, since there are exactly n-1 edges to process once the count check passes, each processed in amortized near-constant time.

Worked example

from typing import List

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

def validTree(n: int, edges: List[List[int]]) -> bool:
    if len(edges) != n - 1:
        return False
    dsu = DSU(n)
    for u, v in edges:
        if not dsu.union(u, v):
            return False  # cycle (or self-loop when u == v)
    return True

if __name__ == "__main__":
    cases = [
        (5, [[0,1],[0,2],[0,3],[1,4]], True),        # valid tree
        (5, [[0,1],[1,2],[2,3],[1,3],[1,4]], False), # cycle 1-2-3, and 5 edges != n-1=4
        (4, [[0,1],[2,3]], False),                   # disconnected, edge count also short
        (3, [[0,1],[1,2],[2,0]], False),              # cycle, caught by the count check first (3 edges != n-1=2)
        (1, [], True),                                # single node, no edges: valid
        (2, [[0,0]], False),                          # self-loop; count matches n-1=1 but union fails
    ]
    for n, edges, expected in cases:
        got = validTree(n, edges)
        print(f"n={n} edges={edges} -> {got} (expected {expected})")

Output:

n=5 edges=[[0, 1], [0, 2], [0, 3], [1, 4]] -> True (expected True)
n=5 edges=[[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]] -> False (expected False)
n=4 edges=[[0, 1], [2, 3]] -> False (expected False)
n=3 edges=[[0, 1], [1, 2], [2, 0]] -> False (expected False)
n=1 edges=[] -> True (expected True)
n=2 edges=[[0, 0]] -> False (expected False)

All six cases match the expected verdicts, including the two boundary cases (a single isolated node with zero edges IS a valid tree by definition, and a self-loop is always invalid regardless of n).

Trade-offs and pitfalls

• Common mistake: checking connectivity without also checking the edge count, which wrongly accepts a graph with $n-1$ or fewer edges as connected without noticing that FEWER than $n-1$ edges makes full connectivity on n nodes mathematically impossible in the first place, wasting a traversal on an input that could have been rejected in $O(1)$.
• Common mistake: checking acyclicity (via Union-Find or DFS back-edge detection) without also checking connectivity, which wrongly accepts a graph that is a valid FOREST (multiple disjoint acyclic components) as a single tree; the edge-count precondition is what makes "acyclic" and "connected" collapse into the same check for this specific problem, and skipping the precondition breaks that equivalence.
• Self-loops and duplicate edges are the sharpest edge cases: n=100000 with a self-loop (k, k) still has the right edge count to pass a naive check, and a naive set-based "have I seen this edge before" duplicate check would miss (u,v) followed later by (v,u) unless edges are normalized (for example, always stored as (min(u,v), max(u,v))) before deduplication; Union-Find sidesteps both traps automatically, since find(u) == find(v) is True for a self-loop (u == v) and for any duplicate or reversed-order repeat of an edge already processed.
• At n up to 100,000, an $O(n \log n)$ or even $O(n^2)$ naive approach (for example, running a fresh DFS from every node to check full connectivity, or comparing every edge pair for duplicates) would likely still finish, but the Union-Find approach is worth defaulting to regardless, since it costs no more to write correctly and removes any risk of a naive approach's hidden quadratic blowup on adversarial input.

Direct answer

Consistent hashing gives even load distribution and cheap rebalancing but destroys query locality, forcing every range scan or join into a scatter-gather across many nodes; range-based partitioning gives excellent locality for exactly those queries but creates hotspot risk on skewed keys and makes rebalancing expensive. For a datastore that genuinely needs both complex range queries and elastic scaling, the answer is a hybrid: partition coarsely by range on an attribute that preserves most query locality, then hash within each coarse range to spread load and avoid hotspots inside it.

Structured elaboration

What consistent hashing actually is, before comparing properties. Consistent hashing places both data keys and node identifiers as points on a circular numeric range, called a ring, typically by hashing each one with the same hash function. Each key is then owned by whichever node's point is the first one reached going clockwise from the key's own point on the ring. That single mechanism is what produces both properties compared below: rebalancing is cheap because adding or removing one node only reassigns the keys between it and its ring neighbors, not the whole dataset the way a plain modulo hash (hash(key) mod N) would when N changes; and locality is poor because two keys that are numerically close in the original ID space, like adjacent order IDs, get hashed to essentially random, unrelated points on the ring, so there is no guarantee they land near each other, or on the same node, at all.

Consistent hashing

• Query locality: poor. Related keys are scattered pseudo-randomly across nodes by design, so a range scan or a join across a key range has to fan out to many (potentially all) nodes and merge results, a scatter-gather pattern that is expensive and has a tail-latency cost equal to its slowest participant.
• Rebalancing: cheap. Adding or removing a node (especially with virtual nodes) only moves a small, bounded slice of the keyspace.
• Scaling: straightforward; new capacity absorbs a proportional share of load automatically.

Range-based partitioning

• Query locality: strong. Keys that are close in sort order live on the same node, so range scans and joins over a contiguous key range are single- or few-node operations, and storage engines benefit from sequential I/O and better compression on sorted data.
• Rebalancing: expensive. A skewed key distribution concentrates load on one range, and fixing it means splitting or merging large contiguous chunks of data, a much bigger operation than moving a handful of hash buckets.
• Scaling: harder to automate; adding capacity typically requires a deliberate split-planning step rather than capacity absorbing load on its own.

Hybrid approach

1. Choose a coarse partitioning attribute that captures most of the locality your queries need (a time window, a tenant id range, a geographic region) and range-partition on it. This keeps queries that filter or join on that attribute confined to a small number of coarse partitions.
2. Within each coarse range, sub-partition by consistent hashing (or a hash of a secondary key) into several sub-shards spread across physical nodes. This is what prevents a single popular coarse range from becoming a hotspot: instead of one range living on one node, it's spread across the sub-shard set.
3. Maintain a lightweight metadata/routing layer mapping coarse range to its set of sub-shard endpoints, so the query planner knows which sub-shards a given range maps to without a full scatter.
4. Handle skew with adaptive split/merge scoped to the coarse range: if one coarse range's sub-shards are overloaded, split that range's sub-shard count, an operation that only touches that range's data, not the whole dataset.

flowchart TD
    Q[Incoming query: range filter] --> P[Router: which coarse ranges match?]
    P --> R1[Coarse range 1]
    P --> R2[Coarse range 2]
    R1 --> H1[Hash sub-shard a]
    R1 --> H2[Hash sub-shard b]
    R2 --> H3[Hash sub-shard a]
    R2 --> H4[Hash sub-shard b]
    H1 --> M[Merge results]
    H2 --> M
    H3 --> M
    H4 --> M

This bounds scatter-gather to the coarse ranges a query actually overlaps, times the sub-shard fan-out within each, instead of every shard in the cluster.

Worked example

A metadata/search index over 1 billion objects needs to support both point/range lookups by ingestion time and elastic scaling as volume grows. The team range-partitions coarsely by ingestion week, giving roughly 100 coarse ranges for two years of retained data (a stated design choice, not a derived figure), and hash-partitions each coarse range into 50 sub-shards to spread load evenly within the week, giving $100 \times 50 = 5{,}000$ total shards across the cluster. A typical query filtering on a 3-week window touches only the 3 matching coarse ranges, fanning out to $3 \times 50 = 150$ sub-shards, or $150 / 5{,}000 = 3\%$ of the cluster, instead of a full scatter-gather across all 5,000 shards that pure consistent hashing on object id would require for the same query. A query that needs a single object by id, with no time filter, still does a targeted hash lookup within whichever coarse range the object's timestamp maps to, so point lookups stay single- or few-shard regardless of the hybrid layout.

Trade-offs & pitfalls

• The hybrid scheme adds a real second layer of metadata and routing logic (which coarse ranges exist, which sub-shards belong to each) that a pure hash or pure range scheme doesn't need; that complexity has to be justified by an actual mixed workload of range queries plus elastic-scaling needs, not adopted by default.
• Choosing the coarse partitioning attribute poorly (one that doesn't align with how queries actually filter) gives you the rebalancing cost of range partitioning without recovering the locality benefit that was the whole point of choosing it.
• A coarse range that itself becomes hot (a recent, actively-written time window, for instance) still needs the adaptive split/merge step; sub-sharding by hash inside it helps distribute load but doesn't eliminate the need to watch for a coarse range outgrowing its allocated sub-shard count.
• Cross-coarse-range joins (joining two objects that fall in different weeks, say) are not free just because the hybrid scheme handles range queries well; that join still fans out across whichever coarse ranges and sub-shards are involved, so it's worth being explicit about which query shapes the hybrid design is actually optimizing for.