HTTP API Crawling and URL Mazes

What's being tested

These problems test graph traversal under an I/O contract: traverse a hidden graph exposed as HTTP links, detect termination, and avoid cycles while accounting for network faults. Interviewers probe algorithmic choices (BFS vs DFS), state management (visited/idempotency), and resilient HTTP client behavior.

Patterns & templates

• BFS traversal using a deque queue: guarantees shortest API-hop path to an exit; memory O(V), calls up to O(V+E).

• DFS (iterative stack) for lower memory in deep-but-sparse mazes; beware recursion limits and hidden cycles.

• Cycle detection / visited set — store canonicalized URLs (strip fragments/params if contract allows) to avoid infinite loops and duplicate calls.

• Retry with exponential backoff on transient HTTP 5xx errors, e.g., 100ms→200ms→400ms, cap retries to avoid long tails.

• Timeouts & overall budget — per-request timeout (e.g., 2s) plus global deadline; abort if cumulative time > budget to prevent blocking CI.

• HTTP client best-practices — reuse requests.Session or aiohttp connector, propagate Authorization header, and handle non-JSON bodies and unexpected status codes.

Common pitfalls

Pitfall: Repeatedly re-requesting the same URL without normalization; leads to infinite loops and flakey p99 latencies.

Pitfall: Retrying on client errors (4xx) instead of only transient server errors (5xx) — wastes budget and hides bugs.

Pitfall: Forgetting a global timeout — a slow endpoint can stall the whole traversal and fail the job.