Katkat
Back

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

AnthropicSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Build a web crawler that starts from one URL, follows links only on the same hostname, strips URL fragments and fetches each page once, first single-threaded and then concurrently. It tests graph traversal, URL normalization, a thread-safe visited set and correct termination of concurrent work.

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.

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.

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

Hints

Hint 1

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.

Hint 2

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.

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?