~/problems / Pools & pipelines / Thread pool / concurrent crawler

Concurrent web crawler

medium 3 levels ~55 min Anthropic

Level 1 Same-host crawler

You're given a parser object whose method parser.get_urls(url) -> list[str] fetches a page and returns the links on it. Treat it as slow network I/O.

Implement crawl(start_url: str, parser) -> list[str], returning every page reachable from start_url by following links, restricted to pages on the same hostname as start_url (urllib.parse.urlparse(url).hostname), including start_url itself.

  • Fragments don't make a new page. http://a.test/p#intro and http://a.test/p#end are both the page http://a.test/p. Strip the fragment (urllib.parse.urldefrag(url).url) before doing anything else with a URL, including start_url. Returned URLs have no fragment.
  • Fetch each page at most once, even when the link graph has cycles.
  • Never fetch a page on another host. Subdomains count as other hosts: blog.a.test is not a.test.
  • Return each page once, in any order.

Assume all links are absolute http:// URLs without port numbers, and that no other normalisation is needed.

# a.test/     links to  a.test/x, a.test/y#top, b.test/
# a.test/x    links to  a.test/, a.test/y
# a.test/y    links to  a.test/x#frag
crawl("http://a.test/", parser)
# ["http://a.test/", "http://a.test/x", "http://a.test/y"]  (any order)
Show hint

This level needs no concurrency yet: an ordinary graph traversal with a seen set will do.

Level 2 unlocks when level 1 passes.

Level 3 unlocks when level 2 passes.

Topic: Thread pool / concurrent crawler. ThreadPoolExecutor, asyncio, thread-safe visited set.

0:00
Ctrl ' run · Ctrl ↵ submit
esc