Multithreaded Web Crawler with Retries for a Failing Fetch API

Write a web crawler. Starting from one URL, it visits every page reachable by following links, using an API that fetches a page and returns the URLs that page links to. Implement it with a breadth-first or depth-first traversal, then make it multithreaded, then make it retry when the fetch API fails. ```python fetch_links(url: str) -> list[str] # a network call: slow, and it can raise an exception when it fails ``` ### Clarifying Questions - Which pages are in scope: only URLs on the start URL's host, or everything reachable? Is there a limit on depth or on the number of pages? - Which URLs count as the same page: should fragments, trailing slashes or letter case be normalized? - What should the crawler return: the set of URLs visited, the order of visits, or the link graph? - When `fetch_links` fails, does the error say whether a retry can help, and is there a rate limit or a concurrency limit on the API? ### Part 1 — Single-threaded crawl Implement `crawl(start_url)` with BFS or DFS, returning the pages it reached, and explain your choice of traversal. ```hint Mark before you fetch Think about when a URL should enter the visited set so that it is never fetched twice, even when many pages link to it. ``` #### What This Part Should Cover - The traversal, the visited set and URL normalization - Scope filtering, and the order in which BFS and DFS visit pages - Time and memory in terms of pages and links, and why DFS should use an explicit stack ### Part 2 — Multithreaded crawl Fetches dominate the running time. Use several threads to fetch pages concurrently, and return the same set of pages as the single-threaded crawl. ```hint When is the crawl finished An empty queue does not mean the crawl is over while other threads are still fetching pages that may add new links. ``` #### What This Part Should Cover - An atomic check-and-insert on the visited set - Correct termination when no URL is waiting and none is being fetched - Bounding concurrent fetches, and what happens to an exception raised in a worker thread ### Part 3 — Retries when the API fails `fetch_links` sometimes fails. Make the crawler retry failed fetches without fetching any page more often than needed and without crawling forever. ```hint Not every failure deserves a retry Separate errors that may succeed on a second attempt from errors that never will, and think about what a waiting retry does to a worker thread. ``` #### What This Part Should Cover - Which errors are retried, how many times, and with what delay - Keeping threads busy while a retry waits, and limiting the load on a failing host - What the result reports about pages that never succeeded ### What a Strong Answer Covers - Settles scope, URL normalization, the result and the failure model first - A correct traversal that fetches each page once per attempt - A concurrent design with atomic visited checks and a correct termination condition - Bounded retries with exponential backoff and jitter, limited to retryable errors - A result that separates crawled pages from pages that failed ### Follow-up Questions - The crawl covers billions of pages on many machines. How do you split the work and the visited set? - Some sites ask crawlers to slow down. How do you enforce a per-host request rate? - The crawler crashes halfway through. How does it resume without starting over? - Two different URLs serve the same content. How would you detect and skip the duplicates?