Web Crawler Multithreaded
Medium · Design · Breadth-First Search · Depth-First Search · Concurrency
Problem
Given a start URL startUrl and an object htmlParser whose method getUrls(url) returns the links found on a page, crawl using multiple threads and return every URL reachable from startUrl that has the same hostname as startUrl, in any order.
Rules for the crawl:
- Start at startUrl and follow the links getUrls returns.
- Never fetch the same URL twice.
- Only fetch and return URLs whose hostname equals that of startUrl. The hostname is the part between http:// and the next / (or the end). All URLs use http with no port, and a URL ending in / differs from the same URL without it.
In a real crawler getUrls is a slow network call, so fetches should run concurrently, with shared state kept safe. getUrls may be called from many threads at once.
In the tests, urls and edges describe the link graph ([i, j] means page urls[i] links to urls[j]); your code only sees startUrl and htmlParser. The grader checks the result, not the threading: the set of URLs you return, that no page was fetched twice, and that no page on another host was fetched.
Examples
Input: urls = ["http://docs.acme.io/start","http://docs.acme.io/guide","http://blog.acme.io/post","http://docs.acme.io/api"], edges = [[0,1],[0,2],[1,3],[2,0]], startUrl = "http://docs.acme.io/start" Output: ["http://docs.acme.io/api","http://docs.acme.io/guide","http://docs.acme.io/start"]
blog.acme.io is another hostname, so that page is neither fetched nor returned. The output is shown sorted; any order is accepted.
Input: urls = ["http://a.com/x","http://b.com/y","http://a.com/z"], edges = [[0,1],[1,2]], startUrl = "http://a.com/x" Output: ["http://a.com/x"]
a.com/z is linked only from b.com, which is never fetched, so it is never reached.
Constraints
- 1 <= len(urls) <= 1000
- 1 <= len(urls[i]) <= 300
- startUrl is one of urls
- Hostnames are 1 to 63 characters of letters, digits and hyphens, joined by dots
- No URL appears twice in urls
Approaches
- Breadth-first search, one fetch at a time — time O(V + E) work, V fetches in sequence, space O(V)
Follow-up
What if the crawl ran on many machines? seen can no longer live in one thread: it becomes a shared store, and URLs are usually partitioned by hostname hash so each machine owns some hosts and forwards the rest. Politeness limits (fetches per host per second) then matter more than thread counts.
Related problems
Start free on Cariara · Coding problems · System design studio
