Web Crawler

PracticalhardPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

A search engine starts from a seed URL and walks the web, following links page to page without fetching the same page twice. You are given a helper get_links(url) that fetches a page and returns the absolute links on it; it is injected at construction and may raise on a network error. You never implement get_links - you build the crawl on top of it: traverse the link graph, dedup, scope the crawl, parallelize it, then bound it with depth and rate limits.

The link graph has cycles and pages that link to each other, so naive recursion never terminates. The crawl must visit each URL at most once and survive a page whose fetch raises.

Level 1 - BFS with deduplication

Implement crawl(seed_url) returning every URL reachable from the seed, including the seed, with no duplicates.

Follow every link get_links returns (no filtering yet).
Visit each URL at most once; cycles and self-loops must terminate.
If get_links(url) raises, skip that page and continue - one dead link does not abort the crawl.
Return order is unspecified (a sorted list is fine).

Example:

graph: a -> [b, c], b -> [d], c -> [d], d -> []
crawl("a") -> {a, b, c, d}      # d discovered via two paths, fetched once

Level 2 - Same-domain filter and fragment stripping

Add two optional behaviors to crawl:

def crawl(self, seed_url, same_domain=False, max_depth=None,
          max_workers=1, requests_per_second=None) -> list[str]


- `same_domain=True`: only visit URLs whose host (netloc) matches the seed's. A subdomain (`sub.a.com`) is a different host.
- Fragment stripping is always on: `a.com/p#x` and `a.com/p#y` both normalize to `a.com/p` and are fetched once. The seed is always in the result.
- `max_depth`, `max_workers`, and `requests_per_second` are part of the signature now but unused until later levels.

**Example:**
```text
crawl("http://a.com/", same_domain=True)
  with a -> [a.com/page, b.com/other]
  -> {http://a.com/, http://a.com/page}   # b.com filtered out

Level 3 - Concurrent crawl

Add crawl_concurrent(...) with the same signature and the same observable results as crawl, but fetch pages in parallel with a thread pool.

The visited set is shared across workers and must be guarded so the same URL is never fetched twice, even when two workers discover it at the same moment.
All Level 1 and Level 2 behavior (dedup, same_domain, fragment stripping, error skipping, termination on cycles) must hold exactly.

Example:

crawl_concurrent("a", max_workers=4) on the diamond a->b,c; b,c->d
  -> visits {a, b, c, d}; d fetched exactly once

Level 4 - Depth and rate limits

Make crawl_concurrent honor the last two parameters (and max_depth in crawl too, for parity):

max_depth: the seed is depth 0; its direct links are depth 1. max_depth=0 visits only the seed. None means unlimited.
requests_per_second: a global minimum interval of 1 / requests_per_second between calls to get_links, across all workers. None means no throttling.

Example:

crawl_concurrent("a", max_depth=1) on a -> b -> c
  -> {a, b}          # c is depth 2, never followed
 
crawl_concurrent(chain of 4, max_workers=1, requests_per_second=10)
  -> takes at least ~0.3s (3 gaps x 0.1s)

Patterns used

Foundations primers this challenge draws on.

BFS

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed