progress

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

Concurrent web crawler

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 3 levels ~55 min Anthropic

Level 1 Same-host crawler

crawl receives a parser object as its second argument: the tests make one and pass it in, so you don't write it. Its method parser.get_urls(url) -> list[str] fetches a page and returns the links on it. Treat it as slow network I/O.

To try your code yourself, any object with that method works:

class FakeParser:
    def __init__(self, links):
        self.links = links                     # {url: [links on that page]}

    def get_urls(self, url):
        return self.links.get(url, [])

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.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc