Graph Traversal With Cycle Detection
Asked of: Software Engineer
Last updated

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 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, or504, 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
congratsmessage; 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
- Find the Exit of an HTTP URL Maze Despite Flaky 503s and Bad JSONRamp · Software Engineer · Technical Screen · medium
- Crawl an HTTP-served maze to its exit with 503 retries, dead ends and cyclesRamp · Software Engineer · Technical Screen · medium
- Find an Exit in a URL MazeRamp · Software Engineer · Technical Screen · medium
- Find final URL by crawling until “congrats”Ramp · Software Engineer · Technical Screen · hard
- Find exit URL via BFS API callsRamp · Software Engineer · Technical Screen · medium
- Navigate maze via HTTP APIRamp · Software Engineer · Technical Screen · medium
Related concepts
- Graph Traversal And Shortest PathsCoding & Algorithms
- DFS/BFS Tree, Graph, And Grid TraversalCoding & Algorithms
- BFS, DFS, Graph, And Grid TraversalCoding & Algorithms
- BFS/DFS Graph and Tree Traversal and Shortest PathsCoding & Algorithms
- Cycle DetectionCoding & Algorithms
- Topological Sort And Cycle DetectionCoding & Algorithms