Lyft Backend Developer Interview Preparation Guide - Mid Level (2-5 Years)

Direct answer
Systematize defensive coding across a large codebase with a layered set of automated checks (static analysis rules, pre-commit hooks, CI gates, runtime canaries) rolled out incrementally, so the safety net is enforced consistently rather than depending on every engineer remembering every rule on every PR.

Structured elaboration

• Static analysis rules: catch common defect classes mechanically (bare except:, unchecked return values, missing resource closures) before a human ever reviews the diff; these are the cheapest checks to run and should gate every PR.
• Pre-commit hooks: catch the same class of issue even earlier, locally, before it's even pushed, at the cost of needing to be fast enough not to annoy developers.
• CI gates: run the full, slower analysis (deeper static analysis, integration tests exercising failure paths) that's too slow for a pre-commit hook but must still block a merge.
• Runtime canaries: for invariants that can't be checked statically (a value actually stays within a valid range at runtime), a sampled runtime assertion in a canary deployment catches what static analysis structurally cannot.
• Incremental rollout: introduce a new rule in WARN-only mode first, measure how many existing violations it flags, fix the worst offenders, THEN flip it to blocking; a rule that blocks immediately on a codebase with thousands of pre-existing violations either gets disabled in frustration or trains everyone to add a suppression comment reflexively.

Worked example
A team wants to eliminate silently-swallowed exceptions across a large polyglot codebase (Python and Go services). Static analysis (a custom lint rule, see the companion swallowed-exception-detector question) flags every except Exception: pass and every ignored Go err. Rolled out: first in CI as a WARN, generating a dashboard of ~800 existing violations; the team triages and fixes the highest-risk 50 in the first sprint; the rule flips to BLOCKING for new code only (existing violations are grandfathered with a suppression comment that includes a tracking ticket, not silently ignored); a slow, steady backlog-burn-down continues alongside normal feature work.

Trade-offs and pitfalls
The balance to get right is between developer productivity and safety: a rule that's too aggressive too fast burns trust and gets bypassed (developers learn to add # noqa reflexively rather than actually fix the issue); a rule introduced too gently never actually gets enforced and the WARN-only phase becomes permanent. Measuring adoption (violation count trending down, not just 'the rule exists') and developer sentiment (are suppression comments increasing faster than real fixes?) are both necessary to know whether the rollout is working, not just whether the tooling is installed.

Clarify first
I would ask whether the product manager wants a time-based window or a calendar window. A 168-hour window means the last 7 times 24 hours from each event timestamp. A calendar window means the current day plus the previous 6 calendar days in the store's business timezone. Those are not the same at midnight boundaries.

Implementation choices

• If they want 168 hours, use a timestamp window.
• If they want calendar days, aggregate by date first, then roll up daily counts.

-- Calendar-day version
WITH daily AS (
  SELECT
    store_id,
    CAST(order_ts AS date) AS order_date,
    COUNT(*) AS orders
  FROM orders
  GROUP BY store_id, CAST(order_ts AS date)
)
SELECT
  store_id,
  order_date,
  SUM(orders) OVER (
    PARTITION BY store_id
    ORDER BY order_date
    ROWS BETWEEN 6 PRECEDING AND CURRENT ROW
  ) AS rolling_7_day_orders
FROM daily;

Boundary example
An order at 2025-01-08 00:05 UTC is inside the calendar-day window for Jan 8 through Jan 2, but in a strict 168-hour window it depends on the exact timestamp cutoff. I would document that choice in the metric definition so analysts get the same answer.

Direct answer

A credible estimate for a bounded piece of owned technical work is never a single number. It is a range built from a real decomposition of the work, with the assumptions and risk factors named out loud rather than folded silently into padding. Strong candidates separate "the work I can size confidently" from "the unknowns that could blow this up" and present both.

Structured elaboration

1. Define done first. Before sizing anything, pin down what "done" actually means (what gets tested, what gets deployed, who signs off). An estimate against a fuzzy definition of done is not an estimate, it is a guess.
2. Decompose into small stages. Break the work into pieces small enough that each one is individually estimable (roughly a day to a few days each), not one lump. Small stages make errors easier to catch and let you re-forecast partway through instead of waiting until the end to discover you were wrong.
3. Name your assumptions explicitly. Write down what you are assuming about scope, existing tooling, data availability, and team support. These assumptions are exactly what turns out to be wrong later, so writing them down is what lets you catch it early.
4. Identify the risk factors that could blow up the estimate, separately from the baseline work itself: unfamiliar technology, an external dependency you do not control, environment or data-access delays, and any stage that depends on something you have not verified yet. The biggest risk to a technical estimate is almost always one of these, not the raw coding effort.
5. Estimate each stage as a range (an optimistic case if nothing goes wrong, and a likely case), then add contingency sized to the risk factors you named, rather than a flat percentage applied blindly everywhere.
6. Present timeline, resourcing, and confidence as one package: the stage breakdown, the range with a stated confidence level, the top two or three named risks that could move the number, and the checkpoint at which you will re-confirm the estimate once the biggest unknown is retired.

Worked example

Take automating a regression suite. Decomposition: audit the existing manual suite and select which cases to automate (2 days), extend the automation framework (3 days), author automated tests for 30 selected cases at roughly half a day each (15 days), stabilize flaky tests and wire into CI (continuous integration, the automated pipeline that runs tests on every code change) (3 days). Baseline sum: 2 + 3 + 15 + 3 = 23 days.

The two named risk factors: the automation framework may need real rework if the underlying application's UI changes mid-project, and test-environment access could be delayed. Contingency for those two risks adds roughly 3 days, giving a likely estimate of 26 days. Optimistic case (framework needs no rework, stabilization goes smoothly): 21 days. Pessimistic case (environment access is delayed by a full week): 26 + 5 = 31 days.

What I would present to stakeholders: "roughly 5 to 6 weeks (about 26 working days) at medium confidence, with a realistic range of 21 to 31 days depending on two named risks: framework rework and environment access. I will check back in at day 10, once the framework and audit stages are done, and re-confirm or revise the range."

The same shape applies just as directly to a reporting-dashboard build for a Business Intelligence or Data Analyst: decomposition might run source-data validation (2 days), query and metric-definition build (4 days), visual build and stakeholder review cycles (5 days), and a final accuracy reconciliation against a known source of truth (2 days), for a baseline of 13 days. The named risk factors shift to data-quality gaps discovered during reconciliation and a slow stakeholder review turnaround, rather than framework rework, but the same discipline holds: present a range with a stated confidence level, name the top risks, and set a checkpoint (for example, after the query and metric-definition stage) to re-confirm the estimate rather than wait until the deadline.

Trade-offs and pitfalls

Padding the number silently instead of naming the actual risk teaches stakeholders nothing about what to watch. Giving a single point estimate as if it were a fact invites a commitment you cannot actually make good on. Not re-forecasting at a natural checkpoint means the first time anyone learns the estimate was wrong is at the deadline. And anchoring the estimate to the requester's preferred date, then reverse-engineering a plan to fit it, is the fastest way to lose credibility the next time you estimate anything.

Situation & goal
High tail latency on a read-heavy microservice; objective is to add Redis caching to reduce P99 reads without breaking correctness.

1) Diagnose before change

• Profile requests (flamegraphs, p99/p95, op durations) to confirm DB / serialization / network are root cause.
• Identify hot endpoints, traffic patterns, request sizes, and read-after-write consistency requirements.
• Measure current QPS, cacheable ratio, and write frequency.

2) Cache placement

• Start with a remote managed Redis cluster (single-region) for operational simplicity.
• If latency still dominated by network, move to co-located cache instances (sidecar or local Redis) per AZ with replication for failover.
• Consider client-side in-process LRU for ultra-hot tiny objects.

3) Cache key design

• Use deterministic, namespaced keys: service:v1:resource_type:resource_id:fields_hash
• Include version and user-scoped identifiers where relevant; avoid storing unbounded queries (use normalized query signature).
• Keep keys <= 512 bytes; use hashes (sha256) for long query signatures but preserve readable prefixes.

4) Partitioning / sharding

• Use Redis Cluster with key-hash slotting for scalability.
• Ensure key prefixes for related sets map to same shard when you need atomic multi-key ops.
• For client-side sharding, use consistent hashing library.

5) Cache warming and population

• Warm critical hot keys during deploy using background jobs that read DB and write cache.
• Gradual ramp: start with low percentage of traffic routed to cached path (feature flag), use shadow reads (write-through or read-through) to populate without affecting users.
• TTLs: set sensible expirations and use jitter to avoid stampedes. Implement mutex/locking (singleflight) or probabilistic early refresh.

6) Monitoring & alerts

• Track cache hit rate, miss rate, latency (P50/P95/P99) for cache vs DB paths, Redis latency, memory usage, evictions, error rates, and load on origin DB.
• Add dashboards and alerts: hit rate drop, eviction spikes, increased DB QPS, P99 read latency > baseline.

7) Rollback criteria & runbook

• Rollback if:
  • P99 latency doesn't improve or worsens beyond threshold
  • DB load increases unexpectedly (cache miss storm)
  • Data-staleness causing customer-facing errors (consistency violations)
  • Redis errors/evictions causing failures
• Rollback steps: toggle feature flag to disable cache reads/writes, allow TTL expirations, revert deployment config, and run origin warming if needed.

Notes / Best practices

• Prefer read-through/write-through for simplicity; write-back only if safe.
• Add metrics and traces before flip; use canary and gradual rollout.

Direct answer
Proving blameless postmortems causally reduce recurrence, rather than assuming it, requires comparing incident outcomes between groups that did and did not receive the full blameless-postmortem treatment, while controlling for the fact that incidents are relatively rare, which makes a small, underpowered comparison unreliable.

Structured elaboration

• Define the primary metric precisely. Incident recurrence rate for the same or closely related failure category within a defined window (say, six months) after a postmortem, and mean-time-to-recovery for any recurrence that does happen, are both reasonable primary outcomes.
• Form comparison groups given low incident frequency. A staggered rollout across teams (some teams adopt full blameless postmortems now, others adopt a few months later) gives you a natural comparison without denying anyone the practice indefinitely, and it's more feasible than a strict randomized controlled trial in most organizations. Alternatively, compare incident classes that received a full postmortem against similar-severity incident classes from before the practice was adopted, using the organization's own history as the comparison.
• Account for low frequency directly. Because a single team's incident count is small, aggregate across many teams or many incident categories to get enough statistical power, and be honest that with genuinely rare, high-severity incidents, you may only be able to speak confidently about a proxy (like recurrence of the underlying vulnerability class in code review or testing) rather than recurrence of an actual outage.
• Control for confounders explicitly. Teams that adopt blameless postmortems early are often also the teams already investing more broadly in reliability practices, so any observed improvement could be due to that general investment rather than the postmortem practice specifically; a staggered rollout across otherwise-similar teams helps isolate this, and tracking a secondary metric less directly tied to postmortems (like general code quality trends) as a check helps rule out a confound affecting everything at once.
• Report the honest limitation. Even a well-designed study in this space will likely have wide confidence intervals given how rare severe incidents genuinely are; report that uncertainty rather than overstating confidence in a clean causal result.

Worked example
An organization with 40 teams rolls out mandatory blameless postmortems to half the teams (chosen to be broadly similar in size and incident history) starting this quarter, with the other half adopting the practice three months later. Primary metric: recurrence rate of a related incident category within six months of any postmortem-eligible incident. After the study window, teams in the early-adoption group show a lower recurrence rate than the later-adoption group during the period before the second group adopted the practice, and the gap narrows once the second group also adopts it, which is more convincing evidence of a causal effect than a simple before-and-after comparison on a single group would have been, since it rules out a general org-wide trend as the sole explanation.

Trade-offs and pitfalls
The most common mistake is treating a simple before-and-after comparison on one group as proof of causation, when it's equally consistent with unrelated organizational improvements happening over the same period. A second is understating how much statistical power genuinely rare, severe incidents cost you, and presenting a result with far more confidence than the small sample size actually supports.

Direct answer
A distributed counter aggregating per-node counters into a global total needs three test layers targeting three distinct bug classes: unit tests for the merge logic's off-by-one and overflow behavior in isolation, integration tests that exercise the merge under realistic node-restart and network-partition conditions, and chaos/incident-style tests that inject those faults into a running system and assert the same invariants hold end to end. The core invariant to assert throughout is that the global total is monotonically non-decreasing from the perspective of any single observer, even while individual node-local counters reset.

Structured elaboration

Off-by-one from node restarts. When a node process restarts, its local counter resets to zero and climbs again; a merge function that naively treats every reported value as an absolute delta will double-count the node's pre-restart contribution. The correct merge tracks each node's last-seen value and only takes the raw value as the delta when it is smaller than the last-seen value (a reset signal), otherwise takes the difference.

Overflow from aggregation. Even if every per-node counter individually fits in 32 bits, the SUM across many nodes can exceed it; this is a distinct bug class from per-node overflow and needs its own boundary tests sized to the actual node count and per-node rate the system expects, not to a single node's range.

Invariants to assert. Monotonic non-decrease of the global total between any two observations by the same client (never decreasing, since counters only increment); conservation, meaning the global total after a merge equals the sum of each node's true lifetime contribution, independent of the order partial values arrived in; and idempotence, meaning re-merging a value already incorporated does not double-count it (needed because retries under partition are common).

Simulating node restarts and partitions. For restarts, drive the merge function directly with a crafted event sequence containing a reset (a later value smaller than an earlier one from the same node), which is deterministic and needs no real process management. For network partitions, at the integration/chaos layer, actually partition the network between nodes and the aggregator (via a proxy that can drop or delay traffic, or namespace-level packet blocking in a test cluster) and assert that once the partition heals, buffered/retried updates land at the correct total rather than being lost or double-applied, since partition-then-heal is exactly when retry-driven double-counting shows up.

Property-based testing for subtle counter bugs. Generate random sequences of per-node events (increments, resets, out-of-order arrivals, duplicate deliveries) and assert the three invariants above hold after every event, not just at the end; this catches sequences a human would not think to write by hand, such as a reset immediately followed by a duplicate delivery of the pre-reset value.

Worked example (executed)

def naive_merge(events):
    total, last_seen = 0, {}
    for node, value in events:
        total += value  # BUG: treats every snapshot as an absolute delta
        last_seen[node] = value
    return total

def correct_merge(events):
    total, last_seen = 0, {}
    for node, value in events:
        prev = last_seen.get(node, 0)
        delta = (value - prev) if value >= prev else value  # reset detected
        total += delta
        last_seen[node] = value
    return total

# node A counts 0->5->9, restarts (local counter resets to 0), counts 0->2->3
events = [("A", 5), ("A", 9), ("A", 2), ("A", 3)]
print(naive_merge(events))    # -> 19
print(correct_merge(events))  # -> 12 (true lifetime contribution: 9 before restart + 3 after)

Actual output: naive_merge returns 19, correct_merge returns 12, matching the true lifetime contribution of 9 (before restart) plus 3 (after restart). The aggregate-overflow case was checked separately with a pinned seed: 50 simulated nodes (random.seed(20260724)), each contributing a value uniformly sampled in [40,000,000, 50,000,000], summed to a true total of 2,247,438,431, which exceeds INT32_MAX (2,147,483,647). A checked-summation implementation raised OverflowError: global total 2154010351 exceeds INT32_MAX (2147483647) after adding node value 44617210, correctly flagging it mid-sum; an unchecked 32-bit wrapping summation of the same 50 values silently produced -2,047,528,865, a large positive true total reported as a large negative number with no error at all.

Trade-offs and pitfalls
The most common mistake is testing the reset-handling logic and the overflow-handling logic as if they were independent, when in production they compound: a node that restarts frequently under load is also a node likely to be near a rate spike, so a bug in reset detection can mask or interact with an overflow bug in ways neither isolated test catches, which is the specific argument for chaos-level tests that inject restarts and high throughput simultaneously rather than as separate scenarios. A second pitfall is asserting only the final global total after a fault-injection run; because monotonic non-decrease is an invariant over the WHOLE observation sequence, a test that only checks the end state can miss a transient dip (a decrease at some intermediate point) that a real client observing at that moment would have seen and acted on incorrectly.

Direct answer

Shard the cache by a hash of the key across many independent LRU (least-recently-used, an eviction policy that discards the item that has gone longest without being accessed) instances, each with its own lock, so concurrent threads mostly contend only with other threads hitting the same shard rather than one another. Fairness across tenants on top of that sharding needs an explicit per-tenant admission or capacity policy (blending recency with frequency, or capping each tenant's share of a shard), since plain LRU alone lets one tenant's access pattern evict another tenant's entries with no notion of "whose entry this is."

Structured elaboration

Why a single lock does not scale

A single shared lock around one LRU's map and linked list serializes every get and put across every thread and every tenant: at high throughput, that lock becomes the bottleneck regardless of how fast the underlying O(1) LRU operations are individually, since only one thread can hold the lock at a time.

Sharding for concurrency

Splitting the keyspace into S independent shards, each with its own map, its own recency-ordering structure, and its own lock, means two threads touching different shards never contend at all. A cheap, uniform hash of the key selects the shard. This trades strict global recency ordering (there is no longer one true "least recently used across everything") for a large reduction in lock contention; each shard's local eviction order is still correct within that shard.

flowchart TD
    A[Client request] --> B[hash of key]
    B --> C1[Shard 1: LRU + lock]
    B --> C2[Shard 2: LRU + lock]
    B --> C3[Shard N: LRU + lock]
    C1 --> D1[Per-tenant quota check]
    C2 --> D2[Per-tenant quota check]
    C3 --> D3[Per-tenant quota check]

Fairness across tenants

Sharding solves throughput, not fairness: within a single shard, a noisy tenant issuing far more requests than another will still fill the shared LRU list with its own entries and evict the quieter tenant's entries purely by volume. Three structural fixes, in increasing order of sophistication:

1. Per-tenant sub-capacity within each shard: give every tenant a fixed maximum slot count inside each shard (or a global per-tenant cap enforced across shards), so one tenant's volume cannot starve another's regardless of access pattern.
2. CLOCK-style approximate recency: rather than a strict doubly-linked recency list (which needs a lock on every access just to reorder), a CLOCK algorithm (a circular buffer of entries with a reference bit, advancing a "clock hand" that evicts entries whose bit is unset and clears bits it passes over) approximates LRU with cheaper, more concurrency-friendly bookkeeping, since a read only needs to set a bit rather than acquire a lock to splice a linked list.
3. Frequency-aware admission (SLRU/TinyLFU-style): a segmented or frequency-sketch-based admission policy (for example, an SLRU splitting each shard into a probationary and a protected segment, or a TinyLFU admission filter that only lets a new entry in if it is estimated to be accessed more often than the entry it would evict) protects a tenant's frequently-reused entries from being evicted by another tenant's one-off scan, which pure recency-based LRU cannot distinguish.

Worked example

Consider two tenants sharing one shard with capacity 4: tenant A accesses the same 2 keys repeatedly (a steady, high-frequency pattern), while tenant B does a one-time scan through 100 distinct keys. Under plain LRU with no per-tenant accounting, tenant B's scan evicts tenant A's 2 keys almost immediately, since LRU only tracks recency, not frequency or tenant identity, and every one of B's 100 accesses is more recent than A's last access. Under a per-tenant sub-capacity of 2 slots each within that shard, A's 2 keys never leave A's own reserved slots regardless of how large B's scan is, and B's scan only ever competes for eviction within its own 2 reserved slots.

Trade-offs & pitfalls

Sharding by hash gives up strict global LRU ordering: the item evicted first is the least-recently-used within its shard, not necessarily across the whole cache, which is an approximation, not a bug, as long as shard sizes are reasonably balanced. A concentrated hot key still funnels all its traffic to one shard's lock no matter how many shards exist, so key-level hotspot skew needs its own handling (for example, splitting an extremely hot key across multiple shard slots) rather than being solved by sharding alone. The most common wrong turn on the fairness half of this question is treating "add more shards" as if it also solved fairness: more shards reduce lock contention but do nothing about one tenant's volume crowding out another's entries within whichever shard both tenants happen to land on; fairness needs an explicit tenant-aware policy layered on top of, not instead of, sharding.

Direct answer. Extract the common shape (try/fetch, 404 handling, error handling) into one small higher-order function, and let each caller supply only the piece that actually differs: how to map the fetched row into a response body.

Before

async function getUser(req, res, db) {
  try {
    const row = await db.find('users', req.params.id);
    if (!row) return res.status(404).json({ error: 'not found' });
    res.status(200).json({ id: row.id, name: row.full_name, email: row.email_address });
  } catch (e) {
    res.status(500).json({ error: 'internal error', detail: e.message });
  }
}
// getOrder duplicates the same try/404/500 shape with a different mapping

After

function makeGetByIdHandler(db, table, mapRow) {
  return async function handler(req, res) {
    try {
      const row = await db.find(table, req.params.id);
      if (!row) return res.status(404).json({ error: 'not found' });
      res.status(200).json(mapRow(row));
    } catch (e) {
      res.status(500).json({ error: 'internal error', detail: e.message });
    }
  };
}
const getUser = (db) => makeGetByIdHandler(db, 'users',
  (row) => ({ id: row.id, name: row.full_name, email: row.email_address }));
const getOrder = (db) => makeGetByIdHandler(db, 'orders',
  (row) => ({ id: row.id, total: row.total_amount, status: row.order_status }));

Verified against a fake db/response harness: both the success path (200 with mapped body) and the not-found path (404) produce byte-identical responses before and after the refactor.

Why an abstraction, not just a copy-paste tweak

The part that varies (table name, row-to-response mapping) is passed IN as data/functions; the part that's identical (control flow: try, 404 check, catch, 500) lives in exactly one place. If the error-handling shape needs to change later (say, adding a request ID to the 500 response), it changes once, and every endpoint built on makeGetByIdHandler gets the fix automatically instead of needing the same edit copy-pasted into every handler.

Preserving clarity per caller

Each concrete handler (getUser, getOrder) still reads as a short, self-contained declaration of WHAT it maps, not HOW the request/response machinery works -- the abstraction doesn't hide the caller's own logic, only the boilerplate every caller would otherwise repeat.

Trade-offs and pitfalls

• This is a good abstraction only because the two callers' DIFFERENCES (the mapping function) are cheap to express as a parameter; if the endpoints started needing genuinely different control flow (one needs a second DB lookup, one needs caching), forcing them through the same higher-order function would make the abstraction leak and become harder to read than the duplication it replaced.
• Watch for the abstraction picking up special-case parameters over time ('handle table X differently') -- that's the sign the shared function is trying to do two things and should split back into two.
• Extracting too early, on the FIRST occurrence of similar code (rather than the second or third), risks guessing wrong about which parts are truly invariant.

I would use caching selectively, with different rules for each data type.

Cache strategy

• Listing metadata: good candidate for cache-aside because it changes relatively infrequently.
• Host profile: also cacheable, usually with a medium TTL.
• Availability summary: cache very cautiously, with a short TTL or event-based invalidation, because stale availability can cause incorrect booking decisions.

Key design
I would build cache keys from stable identifiers and versioning, for example listing ID plus a data version or locale. That helps avoid collisions and makes invalidation safer after edits.

Invalidation

• On listing edits or host profile updates, publish an update event and evict or rewrite the related cache entries.
• On booking or hold creation, invalidate availability immediately or update it atomically.
• For high-risk data, prefer short TTLs plus invalidation instead of long-lived caching.

What I would never cache blindly

• Final booking authorization state
• Inventory counts that must be exact for correctness
• Any response that decides whether a slot is still bookable

For booking flows, I would rather pay a small latency cost than serve stale availability and create double-booking risk. Caching should improve read performance, not weaken correctness.

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.