Interview conceptCoding & Algorithms

Graph Traversal With Cycle Detection

Asked of: Software Engineer

Last updated

A five-step BFS trace across a directed URL graph, showing visited-on-enqueue, queue state, duplicate suppression, and a detected cycle.

What's being tested

These exercises test graph traversal over an implicitly defined directed graph, where URLs are nodes and API-provided links are edges. You must demonstrate cycle detection with a visited set, correct BFS/DFS control flow, and resilient handling of transient HTTP failures, malformed JSON, timeouts, authorization, and termination conditions.

Patterns & templates

  • BFS uses `deque`; mark URLs visited when enqueued to prevent duplicate work and guarantee shortest-edge-path discovery, with O(V+E)O(V + E) traversal.
  • DFS uses recursion or an explicit stack; prefer an iterative stack for unbounded maze depth and avoid recursion-limit failures.
  • Maintain `visited`: set[str]; normalize URLs consistently before lookup, and distinguish a repeated node from a failed HTTP attempt.
  • Retry only transient failures such as 500, 502, 503, or 504, using bounded exponential backoff; never retry malformed success payloads indefinitely.
  • Parse and validate JSON defensively: confirm expected fields and types, treat invalid responses as errors, and preserve the original URL for diagnostics.
  • Propagate authorization headers or tokens on every request; configure connect/read timeouts so one slow endpoint cannot block traversal forever.
  • Stop immediately on the explicit success predicate, such as a congrats message; otherwise return a clear “not found” result after exhaustion.

Common pitfalls

Pitfall: Marking URLs visited only after processing allows cycles to enqueue duplicates repeatedly; mark them when discovered instead.

Pitfall: Treating every HTTP error as retryable can create infinite latency; use bounded attempts and classify permanent versus transient failures.

Pitfall: Assuming links are already absolute or JSON is well-formed; resolve relative URLs and validate the response schema before traversing.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.

Practice questions

Related concepts