Wiki Page Shortest-Click Path

Use a linked-page API to traverse an implicit web graph. Variants ask either for the shortest click distance to a target or for every reachable page, followed by a multithreaded traversal discussion. Requirements A helper API is provided: get_linked_pages(uri: str) -> List[str] returns every page that the page at uri links out to. Implement: shortest number of clicks from start_uri to target_uri. Returning only the count is sufficient; the path itself is optional. The graph is implicit (only revealed by the API); pages can link back to each other, so the BFS must dedupe visited URIs. Some loops add a simulator follow-up: write your own toy get_linked_pages that serves from an in-memory adjacency dict, so the BFS implementation can be tested end-to-end. Examples get_linked_pages("A") -> ["B", "C"] get_linked_pages("B") -> ["D"] get_linked_pages("C") -> ["D", "E"] get_linked_pages("D") -> [] shortest_clicks("A", "D") # → 2 Notes Canonical BFS: queue holds (uri, distance), a visited set prevents re-enqueueing the same URI. Return distance the first time target_uri is dequeued. Don't forget the special case start == target → 0 clicks. The API is the only way to read edges, so each get_linked_pages call is the expensive operation; minimizing the number of API calls is the natural complexity target. BFS calls the API exactly once per visited URI. Edge cases: target unreachable (return -1 or None per the interviewer's convention), cycles, self-link, target equals start. Bidirectional BFS is a reasonable optimization to mention but rarely required in the screen; it does help if both reverse-link enumeration and forward-link enumeration are available, which is typically not the case here. Alternate canonical variant — crawl all reachable pages Given one starting webpage and an API that returns its outgoing links, return every reachable page rather than a shortest-click count to a target. Explain the failure modes of a depth-first traversal and why a breadth-first traversal may be preferable for this version. Follow-up: parallelize the breadth-first traversal across multiple threads while preserving deduplication. Use a shared frontier queue and a thread-safe visited structure; make the visited check-and-add atomic before enqueueing so two workers cannot schedule the same page. Track queued plus in-flight work (or use an equivalent queue-completion primitive) for global termination; an empty queue alone is insufficient while workers may still discover links. Preparation Implement the BFS with an explicit visited set and (uri, distance) queue. Write a toy get_linked_pages backed by a dict-of-lists adjacency, run BFS on a hand-built 6-node graph, and verify against expected click counts. Be ready to discuss what changes if the API is rate-limited (batching, caching the linked-pages result) — Snowflake interviewers sometimes ask this as a soft follow-up. Implement the crawl-all variant with a bounded worker pool on a graph containing both a cycle and a diamond; assert that each URI is expanded exactly once and that workers terminate after all in-flight discoveries finish.