Fewest Link Clicks Between Two Wiki Pages, Then Scale the Search

On a wiki, every page links to other pages. Given a start page and a target page, find the fewest link clicks needed to get from the start to the target, and the pages along the way. The interview then pushed on speed: run the search in parallel, search from both ends at once, and cache what has been fetched. Assume a helper that fetches a page and returns the titles it links to: ```python get_links(title: str) -> list[str] # a network call; slow compared with local work ``` ```text start = "Coffee", target = "Philosophy" Coffee -> Caffeine -> Chemistry -> Philosophy # 3 clicks ``` ### Constraints - The wiki has about a billion pages, and a breadth-first search fans out enormously from one level to the next. The search must cut the work needed to build a shortest path, and the visited set and parent records must still work at that size. ### Clarifying Questions - Should the answer be the number of clicks, one shortest path, or every shortest path? - What should be returned when the target cannot be reached? - Is there a way to list the pages that link to a given page, or only the links out of it? - Can two titles refer to the same page, for example through redirects or different capitalization? - How many requests per second may the search send, and is there a limit on the total number of pages fetched? ### Part 1 — Fewest clicks Implement `fewest_clicks(start, target)` returning a shortest path as a list of titles. ```hint Every click is one level Think about which search order guarantees that the first time you reach the target, no shorter route exists. ``` #### What This Part Should Cover - The search, the visited set and how the path is rebuilt - Correctness: why the first path found is a shortest one - Cost in fetched pages, and the start-equals-target and unreachable cases ### Part 2 — Parallel search Each `get_links` call takes a noticeable amount of time. Speed up the search by fetching many pages at once. ```hint Keep the levels Ask what must still be true about the order in which pages are expanded for the answer to stay shortest. ``` #### What This Part Should Cover - How fetches are issued concurrently while keeping shortest-path correctness - Shared state: the visited set and parent pointers under concurrency - Bounding concurrency, handling failed fetches, and stopping early ### Part 3 — Search from both ends Search forward from the start and backward from the target at the same time. ```hint Two smaller balls Compare how many pages a search of depth d touches with two searches of depth d/2, and what the backward search needs from the wiki. ``` #### What This Part Should Cover - What the backward search needs and how it gets it - When the two searches have met, and how to confirm the path is shortest - Which side to expand next ### Part 4 — Caching Many searches run over time. Add caching. ```hint What is worth keeping Decide which results are reused across searches and how stale they may become. ``` #### What This Part Should Cover - What is cached and for how long - How the cache is shared between concurrent searches - Memory bounds and invalidation when pages change ### What a Strong Answer Covers - Settles the return value, unreachable targets, link direction and title normalization - A correct BFS with path reconstruction and an argument for shortest-path correctness - Level-synchronous parallel fetching with bounded concurrency and retries - Bidirectional search with a correct meeting rule and an honest note about inbound links - A cache design with expiry, sharing and memory limits, and the cost model in fetched pages - Visited and parent bookkeeping sized for a billion pages, with the memory per page estimated ### Follow-up Questions - Pages change while a search is running. Does that matter for the answer you return? - Return every shortest path instead of one. What changes in the bookkeeping? - Only a fixed number of fetches is allowed per search. How do you spend them? - The search runs on many machines. How do they share the frontier and the visited set? - `get_links` is a call to a remote service, and a network partition cuts the search off from it, briefly or for a long time. How do timeouts and retries work, how does the result stay truthful when some pages could not be expanded, and how does the search pause and resume? - Across a graph of about a billion pages, many paths may connect the start and the target. How do you optimize further in that case?