Same-Host Web Crawler: Single-Threaded, Then Concurrent with a Thread-Safe Visited Set

Implement a web crawler. You are given a start URL and an `html_parser` object. Calling `html_parser.get_urls(url)` fetches the page at `url` and returns the list of absolute URLs that page links to. The call blocks while it fetches, can be slow, and is the only way to discover links. The method name is an assumed stand-in for the interface the interviewer provides. Return every URL reachable from the start URL by following links, subject to these rules: - Only crawl URLs whose hostname is the same as the start URL's hostname. Links to other hostnames are neither returned nor fetched. - Strip the fragment (everything from `#` onward) from every URL before you compare, store or fetch it, so `http://news.example.org/a#top` and `http://news.example.org/a` are the same page. - Fetch each distinct page at most once, even when pages link to each other in cycles. The order of the returned URLs does not matter. The interviewer will test your code with links to other hostnames, URLs that differ only in their fragment, and link graphs containing cycles. ### Clarifying Questions - Does "same hostname" include the port and the scheme, so that `http` and `https` versions of a page are distinct? Are subdomains such as `blog.example.org` a different hostname from `example.org`? - Should hostname comparison ignore letter case? - Are query strings part of a page's identity (is `/a?x=1` a different page from `/a`)? - Is the start URL itself included in the result, and should its own fragment be stripped too? - What should happen when `get_urls` raises an error or times out for one page? - Is there a limit on how many requests may be in flight at once, or on the request rate to the host? ### Part 1 — Single-threaded crawler Write the crawler with one thread: traverse the link graph from the start URL, applying the hostname and fragment rules, and return the set of pages found. ```hint Normalize once, at the boundary Decide on a single normalization function and apply it to every URL the moment you see it, before any comparison or set lookup. ``` #### What This Part Should Cover - A correct graph traversal that terminates on cycles - URL normalization: fragment removal and hostname extraction with a real URL parser rather than string splitting - Handling of the start URL, other hostnames and duplicate links - Time and space complexity in terms of pages and links ### Part 2 — Concurrent crawler `get_urls` is slow, so fetching one page at a time wastes almost all of the wall-clock time. Rewrite the crawler so that many pages are fetched concurrently. Explain how you keep the set of visited URLs correct when several threads discover the same link at the same moment, and how the crawler knows it has finished. ```hint Two threads, one link Walk through the exact interleaving in which two workers both find the same new URL; the fix lives in how "check whether seen" and "mark as seen" relate to each other. ``` #### What This Part Should Cover - A thread-safe visited set in which checking and marking a URL are one atomic step - A correct termination condition that neither exits early nor hangs - Bounded concurrency and error handling for failed fetches - Why threads (rather than processes) fit this workload, and the alternatives ### What a Strong Answer Covers - The single-threaded version written first and cleanly, then evolved rather than rewritten from scratch - Edge cases handled explicitly: other hostnames, fragments, cycles, self-links and the start URL - A precise explanation of the race on the visited set and why the chosen fix removes it - Awareness of politeness toward the target host and of failure handling ### Follow-up Questions - How would you distribute the crawl across many machines while still fetching each URL once? - The site has millions of pages. What changes about how you store the visited set? - How do you respect a per-host rate limit when many workers share one host? - Two different URLs serve the same content. How would you detect and skip duplicate content?