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:

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)

Mastery checklist

Check	Why it matters
Mark a URL visited when enqueuing it, not when dequeuing	Mark-on-dequeue lets the same URL sit in the frontier multiple times, so it gets fetched more than once
In the concurrent version, the check-and-add on `visited` is one locked step	`if url not in visited` then `visited.add(url)` are two ops; the GIL can release between them and two workers both fetch the same URL
Strip the fragment before the dedup check, not after	Otherwise `/p#x` and `/p#y` look distinct and the page is fetched twice
Catch exceptions from `get_links` per page	One unreachable page raising must not abort the whole crawl; the page is still recorded as discovered
Depth gate compares `depth + 1` against `max_depth` before enqueuing	Off-by-one here either fetches one level too deep or stops one level short; `max_depth=0` must yield only the seed
Rate limiter stamps the clock after sleeping, under the lock	Stamping before the sleep lets a burst of workers compress past the intended interval
The GIL does not make the shared-set update safe by itself	The classic misconception; the lock is what serializes the compound check-and-add

Patterns used

Foundations primers this challenge draws on.

Loading editor…

Premium content

The live editor for this challenge unlocks with Premium.

0/0 passed