Spotify Software Engineer Interview Preparation Guide - Entry Level

Direct answer

Treat the correction as new information, not a verdict on your competence: acknowledge it in one sentence, apply it immediately, narrate the change briefly so the interviewer can follow your reasoning, and don't relitigate the original choice. In a timed session, incorporating the correction quickly matters more than justifying why you did it the first way.

Structured elaboration

1. Acknowledge in one short sentence, with no self-criticism and no debate: "good catch, let me fix that" or "that makes sense, switching to that now."
2. Apply the correction live and say what you're doing as you do it; interviewers are watching whether you can adapt mid-stream at least as much as whether the first pass was perfect.
3. Don't re-litigate the original choice. Spending two minutes explaining why your first approach was reasonable eats clock time and reads as protecting your ego rather than fixing the code.
4. If the correction changes scope meaningfully, resequence out loud: "given that, I'll skip the extra edge case I was about to add and focus on getting this passing first." That shows time management, not panic.
5. If the correction itself is unclear, ask one targeted clarifying question, not a chain of them, then move.

Worked example

Naming correction: the interviewer says "I'd rename that variable to something that describes what it holds." Response: "good call, renaming to visitedNodes," then continue without debating naming philosophy.

Bug correction: the interviewer says "that loop will run forever if the list is empty." Response: "you're right, I'm missing a base case," add the check live, note briefly "that would've broken on empty input," and move on rather than dwelling on how it was missed.

The same pattern holds for a data-focused live coding round: an interviewer flagging an off-by-one indexing bug or an inefficient join gets the same acknowledge-and-fix response as a general code correction. That's distinct from a live modeling exercise where the interviewer changes the underlying objective mid-way, which is a different kind of pivot with its own reasoning, not just a code fix.

Trade-offs and pitfalls

Silently agreeing with every note, even one that's actually a style preference rather than a correctness issue, without briefly stating your reasoning can look like you have no independent judgment; it's fine to say "I see the trade-off, I'll go with your suggestion since we're optimizing for readability here." Continuing with the original approach after a correction because you're mid-flow is the most common failure, and it reads as not having listened. If a correction opens genuinely large rework, say so and propose a scoped path rather than silently absorbing an unbounded scope change into an already-tight session.

Direct answer
Give the listener a short roadmap up front (what you're about to walk through and in how many steps), narrate one idea at a time in order, and periodically restate where you are relative to that roadmap, rather than free-associating through your thought process.

Structured elaboration

1. State the roadmap before diving in: "There are two things going on here: first the root cause, then the fix I'd propose. Let me start with the root cause." This gives the listener a mental container to place what follows.
2. Narrate conclusions and reasons, not raw stream-of-consciousness. Say what you're checking and why, not just what you're doing: "I'm checking the logs because I suspect this is a timeout, not a crash," rather than silently scrolling and occasionally muttering.
3. Signal transitions explicitly: "okay, that rules out X, so now let's look at Y," so the listener can track your position in the reasoning instead of having to reconstruct it after the fact.
4. Pause at natural checkpoints to check the listener is still following, especially before switching to a new sub-problem, rather than only checking in at the very end.
5. Name your assumptions out loud as you make them, since an unstated assumption is invisible to the listener and, if wrong, can make the rest of your reasoning look wrong for a reason they can't see.

Worked example
Unstructured: "Okay so let me look at this... hmm... yeah so there's this function... wait, let me check something else... okay so actually I think the issue might be... let's see... yeah I think it's the caching."

Structured: "I'm going to check three possible causes in order of likelihood: caching, a race condition, or a bad config value. Starting with caching, since it's the most common cause of this symptom... [checks] ...that rules out caching, the values are fresh. Moving to the race condition..."

The second version gives the listener the plan up front, tells them which hypothesis is being tested and why, and explicitly states when a hypothesis is ruled out, so they can follow the reasoning instead of just watching an unexplained sequence of actions.

Trade-offs and pitfalls

• Over-narrating every micro-step can slow you down and annoy a listener who just wants the conclusion; calibrate the level of narration to whether the audience needs to follow the reasoning (an interview, a mentoring session) or just wants the answer (a peer who trusts you and is short on time).
• It's easy to silently switch approaches mid-thought without saying so; if you change direction, say so explicitly ("actually, let me back up") rather than leaving the listener to notice on their own.
• This is a skill that degrades under real pressure or unfamiliar problems; it's worth practicing the "state the roadmap first" habit specifically, since it's the cheapest part to do consistently even when the rest of your thinking is genuinely uncertain.

Situation & goal: CPU profiling shows 30% of app CPU in (de)serialization. I'll propose a measurable, low-risk plan to reduce CPU usage while preserving correctness and compatibility.

1. Measure & validate hotspots

• Add end-to-end and micro profiling: flamegraphs (perf/async-profiler), eBPF, and language profilers (Java Flight Recorder).
• Instrument per-message metrics (deserialize_time, serialize_time, bytes) and sample stack traces to confirm which code paths (parsers, allocs, copies, string handling) dominate.
• Build microbenchmarks (JMH for Java, pytest-bench for Python) with representative payloads to iterate safely.

2. Optimization candidate list (with reasoning)

• Replace text formats (JSON) with compact binary (Protobuf/FlatBuffers/MessagePack) to avoid parsing overhead — FlatBuffers for zero-copy reads if schema is stable, Protobuf for strong typing/versioning.
• Use lazy parsing / schema-driven partial deserialization for messages where only a subset of fields are used.
• Avoid allocations and copies: use streaming parsers, ByteBuffer slices, mmap for large payloads.
• Consider lightweight compression only if network bandwidth is a bottleneck (CPU vs network trade-off).

3. Pooling & reuse

• Buffer pooling: use pooled ByteBuffers (Netty PooledByteBufAllocator or thread-local buffers). Example (Java):

// simple thread-local ByteBuffer reuse
private static final ThreadLocal<ByteBuffer> TL_BUF = ThreadLocal.withInitial(() -> ByteBuffer.allocateDirect(64*1024));
ByteBuffer buf = TL_BUF.get();
buf.clear();
// use buf for serialization to avoid allocations

• Object pooling only where allocation cost is proven high; prefer reuse of parser/serializer instances (stateless with reset) rather than complex object pools to avoid GC/lock overhead.
• Use off-heap or arena allocators for high-allocation workloads.

4. Compatibility & rollout strategy

• Maintain schema evolution rules (optional fields, numeric wiring, field IDs). Use versioned schemas stored in central registry.
• Backward/forward compatibility: deploy readers that can handle both old and new formats. Implement dual-read during transition: accept both formats; log and metric when older format seen.
• Dual-write / shadowing: for a full migration, producers can emit both formats (primary new + secondary old) to allow consumers to validate before switching.
• Canary deployment: enable new serializer on small % of traffic, compare correctness/perf, then ramp. Feature flags or runtime config to toggle per-service behavior.
• Fallback & monitoring: automatic fallback to old format on errors, track serialization errors, deserialization failures, latency and CPU per service.

5. Validation & rollback

• Run integration tests across services using both formats. Add end-to-end checksums or semantic tests to ensure wire compatibility.
• Observe CPU, latency, error rates. If CPU drops and errors stay flat, proceed with wider rollout.

Trade-offs

• FlatBuffers reduces CPU and copies but requires stricter schema discipline and more codegen management.
• Compression trades CPU for network savings — only beneficial if network latency/bandwidth dominates.

Expected impact

• Typical wins: switching JSON→Protobuf/FlatBuffers + buffer pooling often reduces CPU in (de)serialization by 3x–10x depending on workload. Quantify with your microbenchmarks before committing.

Direct answer

Pick a moment where the hard part was genuinely coordination, not execution, a point where two teams' assumptions conflicted or a handoff nearly broke, and show the specific mechanism you used to resolve it (a shared contract, a live triage session, a changed process) rather than a vague claim that you "kept everyone aligned."

How to structure the story

• Name the teams and the friction point precisely: "platform and security disagreed on X" is a real story; "I coordinated with several teams" is not.
• Show the mechanism, not just the meetings: what artifact or agreement made the coordination stick, a shared interface contract, a runbook, an escalation path, a single source of truth for status.
• Include one moment things actually went wrong: a pure "everyone got along" story doesn't demonstrate coordination skill, a story with friction and a specific resolution does.
• Close with what you changed afterward: strong coordination stories end with a process or artifact that made the next handoff easier, not just a one-time save.

Worked example (skeleton)

This one is an infrastructure scenario; swap in your own domain's equivalent friction point (a data-schema mismatch between two teams' pipelines, a conflicting design-system component, a scheduling conflict between two workstreams) while keeping the same shape: friction point, working session, concrete resolution, process change.

Situation: rolling out a shared platform required product, security, and network teams to align on a new deployment path.
Task: I owned the cross-team integration plan and was accountable when it broke at cutover.
Action: after cutover, API calls between two services started failing intermittently. I convened a short working session with network and platform engineers rather than routing the problem through separate tickets, traced it to a new subnet's (a segmented slice of the network with its own access rules) access rules blocking a port the service mesh (the layer that manages how services talk to each other, including security rules) needed, and had network update the rule while platform adjusted the mesh config in parallel.
Result: resolved within about 3 hours of the first alert, verified by the same monitoring dashboard returning to baseline, with no customer-facing outage. Afterward I added a network-policy check to the pre-cutover checklist so the same class of conflict gets caught before deployment instead of after.

Trade-offs and pitfalls

• Coordination stories with no real friction point read as generic project management, not a demonstrated skill, pick a moment where something actually had to be resolved.
• Taking credit for a resolution really driven by another team's engineer; be precise about your specific role versus who did the technical work.
• Skipping the "what changed afterward" close makes it a one-off save instead of evidence you improve the system, which is the stronger signal.

Direct answer

When legal or compliance flags a possible regulatory problem on something about to ship, that flag is new information, not an attack on the project. The first move is to separate the specific risk from the whole feature: find out exactly what triggers the concern, then look for a way to ship everything outside that blast radius (the specific data, users, or markets the flagged concern actually touches) while the risky piece gets handled properly. Treating the flag as either a full block to fight or a formality to route around are both weak answers; the senior move is to make the freeze as small as the actual risk.

Structured elaboration

1. Turn the flag into a scoped, written finding

Ask for the specific clause or regulation, the specific data flow or behavior it applies to, and which markets or user segments are affected. A flag that sounds like 'this violates a regulation' often narrows down to 'this one data field, in these two markets.' Until that scoping happens, nobody can reason about mitigation, they can only argue about the abstract freeze.

2. Sort what's actually blocked from what's just slow

Once scoped, most flags fall into three buckets: genuinely unsafe to ship anywhere (rare, but real, treat it as a hard stop); unsafe in specific markets or for specific data (the common case, often scoped out with a flag or market-level rule); or unsafe as currently designed but fixable with a smaller change than a full freeze (needs a scoped rework, not a blanket delay).

3. Bring a mitigation, not just a constraint

Offer a concrete option: disable the flagged behavior for the affected markets, gate it behind a feature flag (a toggle that turns a piece of functionality on or off without a new deployment), or ship a version that omits the specific data flow while the rest proceeds. This turns the conversation from 'can we go or not' into 'does this mitigation satisfy the concern,' which moves much faster.

4. Get joint, written sign-off before proceeding

Both the business owner and compliance need to agree in writing on what shipped, what did not, the remaining risk, and who owns closing it. This protects everyone if the interpretation is questioned later and prevents the same argument from recurring next release.

5. If a real freeze can't be avoided, negotiate the timeline explicitly

Sometimes there is no safe scoped path and the freeze has to hold for the affected piece. Here the negotiation shifts to: what's the minimum change needed to clear the concern, who is assigned to it, and can the review be fast-tracked with a dedicated reviewer instead of sitting in a general queue. A freeze with a committed, shrinking timeline is a very different conversation from an open-ended one.

Worked example

A team is about to ship a feature that logs a new field for product analytics, and legal flags that collecting that field may violate a data-protection rule in one region. Scoping the flag shows the issue is narrow: one field, one region. Instead of freezing the whole release, the team ships everywhere else immediately, and for the flagged region ships the same feature with that one field's collection disabled behind a config switch. Legal signs off on the scoped version in writing. The team opens a follow-up item, with an owner and a target date, to redesign how that field is collected (for example, aggregating it instead of storing it per user), so the region isn't stuck without the feature indefinitely.

Trade-offs and pitfalls

• Treating every compliance flag as either a full block or a nuisance to route around is the most common mistake here; both extremes erode trust with the compliance function over time.
• Scoped mitigations (flags, market gating, field exclusions) are good short-term tools but can quietly become permanent if nobody owns the follow-up fix. The sign-off should name an owner and a date, not just describe a workaround.
• Escalating past compliance to force a ship date, without addressing the underlying concern, tends to resurface later as a bigger problem: a real violation or a regulator inquiry. Speed gained by skipping the process rarely survives contact with the risk it was protecting against.
• The strongest signal of seniority isn't how fast the team got to yes, it's whether the final decision is something both sides would still defend the same way months later.

Direct answer. GraphQL fits this scenario better, because the defining constraint is a client that needs a variable, deeply-nested subset of data over a connection where extra round trips are expensive; but recommend it with the specific downside named up front: server-side complexity moves from "design good endpoints" to "prevent expensive, unbounded queries," and that cost has to be paid deliberately, not assumed away.

Payload efficiency. With REST, the dashboard either over-fetches (calls a generic endpoint returning the full nested resource and discards most of it client-side) or the backend team hand-builds a bespoke aggregation endpoint per dashboard view. GraphQL lets the client request exactly the fields and nested relations it needs in ONE query, which is a direct, structural win for a client whose data needs vary by screen and change over time without backend involvement.

Caching gets harder, not easier. REST's cacheability comes from the URL identifying the resource; a single GraphQL endpoint (almost always one POST URL) defeats that entirely. Caching a GraphQL response requires either per-field or per-query caching logic (hashing the query+variables as a cache key) built specifically for this purpose, which is real, ongoing engineering cost that a REST API gets close to free from HTTP infrastructure.

Server-side complexity. This is the honest cost side of the trade. A GraphQL server has to guard against a client asking for an intentionally or accidentally expensive query (deeply nested relations causing an N+1 explosion of database calls — one query to fetch a list of N items, then one MORE query per item to fetch its related data, N+1 queries total instead of a single batched one — or a query requesting an enormous result set with no natural limit), which means investing in query complexity analysis, depth limiting, and a batching layer (DataLoader-style — DataLoader is a widely-used library pattern that collects all the individual lookups requested during one round of resolving a query into a single batched database call, instead of firing one query per item) as a genuine, ongoing engineering cost, not a one-time setup. A REST endpoint's cost is bounded by what the endpoint's own code does; a GraphQL schema's cost is bounded by what any VALID query against it could ask for, which is a fundamentally larger and harder-to-bound surface.

Error handling differs structurally. REST maps naturally onto HTTP status codes (a 404, a 403) for the whole request. GraphQL, being POST-based with a single endpoint, typically returns 200 OK even when part of the requested data failed to resolve, with errors reported inside the response body per-field; a client has to check the response body's errors array explicitly rather than relying on the HTTP status code, which is a real ergonomic difference client teams need to be told about explicitly, not discovered the hard way.

Mitigating the main downside. Invest in query complexity scoring (rejecting a query whose estimated cost exceeds a threshold before executing it at all) and DataLoader-style batching for the N+1 problem from day one, not as a later fix; both are well-established, known-necessary parts of running GraphQL in production, not optional hardening.

Approach

Use an array of buckets (a fixed-size list), where each bucket is itself a small list of (key, value) pairs. To find a key, hash it, reduce it modulo the number of buckets to pick a bucket index, then scan that one short list for a matching key (separate chaining: collisions are handled by letting multiple entries share one bucket, rather than probing elsewhere in the array). Track how full the table is (the load factor, live entries divided by bucket count) and double the bucket array once it crosses 0.75, redistributing every existing entry into the new, larger array so buckets stay short.

Code

class ChainingHashMap:
    def __init__(self, capacity=8):
        self._capacity = capacity
        self._size = 0
        self._buckets = [[] for _ in range(self._capacity)]

    def _index(self, key):
        return hash(key) % self._capacity

    def put(self, key, value):
        idx = self._index(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # update in place
                return
        bucket.append((key, value))
        self._size += 1
        if self._size / self._capacity > 0.75:
            self._resize()

    def get(self, key):
        idx = self._index(key)
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        return None

    def remove(self, key):
        idx = self._index(key)
        bucket = self._buckets[idx]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self._size -= 1
                return True
        return False

    def _resize(self):
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._size = 0
        for bucket in old_buckets:
            for k, v in bucket:
                self.put(k, v)

    def __len__(self):
        return self._size


if __name__ == "__main__":
    m = ChainingHashMap(capacity=4)
    m.put("apple", 1)
    m.put("banana", 2)
    m.put("cherry", 3)
    print("get apple ->", m.get("apple"))
    print("get missing ->", m.get("no_such_key"))

    m.put("apple", 99)
    print("get apple after overwrite ->", m.get("apple"))

    removed = m.remove("banana")
    print("remove banana ->", removed, "| get banana after remove ->", m.get("banana"))

    for i in range(20):
        m.put(f"key{i}", i * 10)
    print("size after 20 more inserts ->", len(m))
    print("capacity after growth ->", m._capacity)
    all_correct = all(m.get(f"key{i}") == i * 10 for i in range(20))
    print("all 20 post-resize keys still correct ->", all_correct)
    print("cherry survived resize ->", m.get("cherry") == 3)
    print("get on never-inserted key returns None ->", m.get("zzz_absent") is None)

Output (executed as shown, capacity starts at 4):

get apple -> 1
get missing -> None
get apple after overwrite -> 99
remove banana -> True | get banana after remove -> None
size after 20 more inserts -> 22
capacity after growth -> 32
all 20 post-resize keys still correct -> True
cherry survived resize -> True
get on never-inserted key returns None -> True

Key points

• put on an existing key overwrites its value in place rather than appending a duplicate entry; that scan-then-overwrite check is what makes put idempotent for repeated keys.
• remove returns False for a key that was never present instead of raising, so callers can check the result rather than wrapping every call in a try/except.
• The resize walks the old buckets and calls self.put again for every surviving entry, which is what re-distributes entries across the new, larger bucket count (a key's bucket index depends on capacity, so it generally changes when capacity changes).
• hash(key) % self._capacity is only safe because the prompt guarantees hashable keys; a custom class used as a key would need a correct __hash__/__eq__ pair (equal objects must hash equally) for this to behave correctly.

Complexity

• Average case, all three operations: (O(1)). With a good hash function and a load factor kept under 0.75 by resizing, each bucket holds a small constant number of entries on average, so scanning one bucket is constant time.
• Worst case: (O(n)), if every key collides into the same bucket (a pathological or adversarial hash function), the table degrades to one long list and every operation becomes a linear scan.
• Resize: (O(n)) when it happens (copies every entry), but it happens only when size crosses a growing threshold, so the amortized cost added to any single put stays (O(1)) averaged over a sequence of inserts.

Edge cases

• Updating an existing key: handled by the in-bucket scan in put, which finds the match and overwrites rather than duplicating.
• Removing a key that is not present: returns False rather than raising, verified above (remove is only demonstrated on a present key here, but the loop structure is identical to get's not-found path, which the test above confirms returns None).
• Getting a key that was never inserted: returns None, confirmed by the final assertion in the demo.
• Two different keys landing in the same bucket: correctness still holds because the bucket scan compares full keys with ==, not just the bucket index; only performance degrades, not correctness.
• Resizing mid-lifecycle: the demo forces a resize (capacity grows from 4 to 32) and confirms every one of the 22 live keys, old and new, still resolves correctly afterward.

Direct answer

An array gives O(1) random access because an index maps directly to a memory address via arithmetic, but inserting or deleting anywhere except the very end requires shifting every following element, an O(n) operation. A singly linked list gives O(1) insert or delete once you already hold a reference to the relevant node, but finding that node in the first place (including "the middle") costs O(n), since there is no arithmetic shortcut, only following pointers one at a time.

Structured elaboration

• The "O(1) insert" caveat, worth stating explicitly. A linked-list insert or delete is only O(1) when you ALREADY have a reference to the right node, typically because you're iterating and acting as you go. If you're only given a numeric position (say, "insert at index 500,000"), you still have to walk there first, which costs O(n); claiming a flat "O(1) insert" without that condition is the single most common oversimplification of this comparison.
• Concrete scenario favoring the array. A lookup table mapping millions of user IDs to profile records, queried by index or key extremely frequently: O(1) random access is the whole point, and the data is rarely inserted into at arbitrary positions.
• Concrete scenario favoring the linked list. An eviction-order list for a cache, where an arbitrary, already-known node is frequently removed from the middle and a new node re-inserted at the front; both operations are O(1) once you hold the node reference, with no shifting cost regardless of list size.

Worked example

Consider inserting one new element at the FRONT of a collection holding 1,000,000 items. On an array, every one of the 1,000,000 existing elements must shift one position to make room, an O(n) cost that scales with however large the array has grown. On a singly linked list, the operation is exactly two pointer writes (the new node's next pointer, and the head pointer), regardless of whether the list holds 10 elements or 10,000,000: the cost does not grow with list size at all. This is the concrete shape of the O(n)-versus-O(1) difference in the table above, not just an abstract notation.

Trade-offs & pitfalls

• Memory overhead and cache locality. Each linked-list node carries at least one extra pointer (8 bytes on a 64-bit system) beyond its payload, and nodes are not stored contiguously in memory. For an iteration-heavy workload, an array is often noticeably faster IN PRACTICE despite both being asymptotically O(n), because sequential array access is cache-friendly while pointer-chasing a linked list typically is not; this is a constant-factor, hardware-driven effect, not a difference in asymptotic complexity.
• The most common oversimplification is stating "linked-list insert/delete is O(1)" without the caveat that this assumes the relevant node reference is already in hand; always confirm whether the scenario gives you the node or just a position.
• Singly linked lists only walk forward. Anything that needs "delete the node before this one" or other backward movement needs either a doubly linked list, or tracking a trailing pointer while iterating forward.
• Don't confuse this with dynamic-array append. A dynamic array (Python's list, Java's ArrayList) amortizes appending at the END to O(1) via geometric growth, which is a different operation from inserting at an ARBITRARY position; conflating the two is a common mistake when reasoning about array costs.

Situation: At my last job I joined a product team mid-sprint where the engineering culture emphasized heavy pair-programming, daily demo-driven standups, and a strict "merge only via small PRs" rule—different from my previous, more solo workflow.

Task: I needed to onboard quickly, contribute meaningful code that met the team's standards, and build credibility so reviewers trusted my changes.

Action:

• Spent the first 3 days observing standups, reading previous PRs, and asking targeted questions about coding conventions and release criteria.
• Paired with a senior engineer on two tickets to learn their testing and commit-message norms.
• Kept my initial PRs very small, added thorough tests and clear descriptions, and proactively asked for feedback in person rather than only via comments.
• Volunteered to own a small refactor to demonstrate adherence to style and testing expectations.

Result: Within two weeks I merged five PRs with minimal rework, my average review time dropped from 48 to 12 hours as reviewers trusted my quality, and I became a go-to for one subsystem. Lesson: rapid observation, intentional pairing, and conservative first contributions build credibility faster than trying to "prove" competence with large, risky changes.

Direct answer

In an undirected graph, DFS with a tracked parent argument detects a cycle by treating an edge to an already-visited node as a cycle, EXCEPT when that already-visited node is the immediate parent, since every undirected edge is stored twice (once in each endpoint's adjacency list), so walking straight back along the edge you just arrived on would otherwise look identical to a genuine cycle. Passing the parent explicitly and skipping exactly that one edge is what makes the check correct.

Structured elaboration

Why the parent check exists at all. An undirected edge $(u, v)$ is represented as $v \in \text{graph}[u]$ AND $u \in \text{graph}[v]$, both directions stored. A DFS that goes from $u$ to $v$ will, when examining $v$'s neighbors, immediately see $u$ again, the edge it just came from. Without a parent check, this looks exactly like discovering an already-visited node, indistinguishable from a real cycle, even on a simple two-node graph with a single edge and no cycle at all. Recording the parent and explicitly skipping the edge back to it removes this false signal while leaving every genuine cycle (an edge into a visited node that is NOT the immediate parent) correctly detected.

Worked example

from typing import Dict, List

def has_cycle(graph: Dict[int, List[int]]) -> bool:
    visited = set()

    def dfs(u: int, parent: int) -> bool:
        visited.add(u)
        for v in graph.get(u, []):
            if v == parent:
                continue  # the edge back to where we came from, not a cycle
            if v in visited:
                return True  # a back-edge to an already-visited, non-parent node: a cycle
            if dfs(v, u):
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False

if __name__ == "__main__":
    tree = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}  # a genuine tree, no cycle
    print("tree (no cycle):", has_cycle(tree))

    triangle = {0: [1, 2], 1: [0, 2], 2: [0, 1]}
    print("triangle (cycle):", has_cycle(triangle))

    disconnected_with_cycle = {0: [1], 1: [0], 2: [3, 4], 3: [2, 4], 4: [2, 3]}
    print("disconnected, cycle only in 2nd component:", has_cycle(disconnected_with_cycle))

    isolated = {0: [], 1: [], 2: []}
    print("all isolated nodes:", has_cycle(isolated))

    self_loop = {0: [0]}
    print("self-loop:", has_cycle(self_loop))

    def edges_from_adj(adj):
        seen = set()
        edges = []
        for u in adj:
            for v in adj[u]:
                if (v, u) not in seen:
                    edges.append((u, v))
                    seen.add((u, v))
        return edges

    def brute_force_has_cycle(adj):
        # Independent ground truth via plain union-find (correct here since
        # this check is over UNDIRECTED edges, where union-find is valid).
        nodes = list(adj.keys())
        idx = {n: i for i, n in enumerate(nodes)}
        parent = list(range(len(nodes)))
        def find(x):
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
        for u, v in edges_from_adj(adj):
            ru, rv = find(idx[u]), find(idx[v])
            if ru == rv:
                return True
            parent[ru] = rv
        return False

    for name, g in [("tree", tree), ("triangle", triangle), ("disconnected", disconnected_with_cycle), ("isolated", isolated)]:
        print(f"cross-check {name}:", has_cycle(g) == brute_force_has_cycle(g))

Output (actually executed with python3):

tree (no cycle): False
triangle (cycle): True
disconnected, cycle only in 2nd component: True
all isolated nodes: False
self-loop: True
cross-check tree: True
cross-check triangle: True
cross-check disconnected: True
cross-check isolated: True

Every DFS-with-parent result is cross-checked against a completely independently implemented union-find (correct for THIS undirected-only use case, unlike the directed case where union-find is unsound). The self_loop case (0: [0]) is correctly reported True: when DFS at node 0 examines its own self-loop edge, the neighbor is 0 itself, which is already in visited (added at the start of the call) and is NOT equal to parent (which is $-1$ for the root call), so it correctly falls through to the cycle-detected branch.

Complexity

Time $O(|V|+|E|)$: each vertex is visited at most once (guarded by visited), and each edge is examined at most twice total (once from each endpoint), a constant factor that does not change the asymptotic bound. Space $O(|V|)$ for visited and the recursion stack.

Edge cases

• Disconnected graph: the outer loop restarts DFS from every unvisited node, so a cycle in any component is found regardless of which component happens to be explored first.
• Isolated nodes (no edges at all): trivially no cycle, handled without any special-casing since the inner loop over graph.get(u, []) simply does nothing.
• Self-loop (v == u): correctly detected as a cycle, as traced above; note that v == u is NOT the same check as v == parent, so a self-loop is never accidentally treated as "the edge back to my parent" even on the very first call where parent starts at a sentinel value.
• Parallel edges between the same pair (the same undirected edge listed twice): would be misreported as a cycle by this implementation, since the second occurrence of the neighbor is not equal to parent on the SECOND time it is examined even though it is the same physical edge; a graph representation that can contain true parallel edges needs an explicit edge-id (not just a node-id) comparison to skip correctly, which this simple adjacency-list version does not attempt to solve.

Trade-offs and pitfalls

• Common mistake: omitting the parent parameter entirely and using a plain "is this neighbor visited" check, which reports every single edge in an undirected graph as a cycle, since the edge back to the immediate parent always looks like a revisit.
• Common mistake: comparing against a set or list of ALL ancestors instead of just the immediate parent. For an undirected graph this is unnecessary extra work, since only the single edge just traversed needs to be excluded, not the whole ancestor chain, that distinction (immediate parent only, versus the full ancestor set) is precisely what separates undirected cycle detection from the analogous directed case, where the full "on the current path" (gray/inStack) set genuinely is needed.
• Why this technique is undirected-specific. The parent-skip trick exists purely because undirected edges are stored bidirectionally; a directed graph never has this "walking back along the same edge looks like a revisit" problem in the first place, since a directed edge $u \to v$ has no automatic reverse entry, which is why directed cycle detection needs the gray/inStack (full active-path) mechanism instead of a simple single-parent exclusion.