Web Crawler Multithreaded
Asked at Anthropic
Difficulty
Medium
Time
O(N * F)
Space
O(N)
Pattern
Depth-First Search
Companies
1
Problem
You are given a starting URL startUrl and an object HtmlParser. That object has one method, getUrls(url). It returns every link found on the page at url. This call blocks: it waits until the page is fetched, but it always finishes within 15ms.
Write a multi-threaded crawler. Start at startUrl, call getUrls on each page you visit, and follow the links you find. Two rules limit what you follow: never visit the same URL twice, and only follow links whose hostname equals the hostname of startUrl. Links to other hosts are ignored.
Return the list of all URLs you crawled, in any order. The list must include startUrl itself. A single-threaded crawler is too slow for the time limit, so you must fetch pages from several threads at the same time.
Which links may we follow?
Constraints
- ●
1 <= urls.length <= 1000 - ●
1 <= urls[i].length <= 300 - ●
startUrl is one of the urls - ●
Hostname labels are 1 to 63 characters, using only a-z, 0-9 and '-' - ●
A hostname may not start or end with '-' - ●
All URLs use http with no port - ●
There are no duplicate URLs in the library
Examples
urls = ["http://news.yahoo.com","http://news.yahoo.com/news","http://news.yahoo.com/news/topics/","http://news.google.com","http://news.yahoo.com/us"]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl ["http://news.yahoo.com","http://news.yahoo.com/news","http://news.yahoo.com/news/topics/","http://news.yahoo.com/us"]urls = ["http://news.yahoo.com","http://news.yahoo.com/news","http://news.yahoo.com/news/topics/","http://news.google.com"]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = "http://news.google.com"["http://news.google.com"]Asked At
1 companies| Company | Difficulty | |
|---|---|---|
| Anthropic | Medium | View all Anthropic questions → |
How to Think About It
The core algorithm is BFS: start from the seed URL, fetch the page, extract all links, add unvisited links to a queue, and repeat. The multithreading part is running multiple BFS workers concurrently.
Data structures: a queue (thread-safe) for URLs to visit, a set for visited URLs (to avoid duplicates and cycles), and a list for results. The queue is shared across threads.
Thread safety: the visited set and queue are shared state. Use a lock (mutex) to protect concurrent access. Alternatively, use thread-safe data structures like ConcurrentHashMap in Java or queue.Queue in Python.
BFS with thread pool: create a fixed number of threads (e.g., equal to CPU cores or a small constant). Each thread loops: grab a URL from the queue (under lock), fetch the page, extract links, add new links to queue (under lock), mark as visited.
Stopping condition: when the queue is empty and all threads are idle, stop. Use a threading.Event or Condition to signal completion. Each thread checks if the queue is empty before proceeding.
Complexity: time is O(N * F) where N = number of URLs, F = average fetch time. Space: O(N) for visited set and queue. The threading does not change Big-O but reduces wall-clock time by a constant factor.
Optimal Approach
Use BFS with a thread pool. Maintain a thread-safe queue of URLs to visit and a set of visited URLs.
Algorithm:
- Initialize: queue = [startUrl], visited = {startUrl}, results = [].
- Create N worker threads (e.g., 4).
- Each worker thread loops:
a. Lock and check if queue is empty. If yes, break.
b. Dequeue a URL.
c. Fetch the page and extract all links.
d. For each link with the same hostname:- Lock and check if not in visited.
- Add to visited and enqueue.
e. Add the URL to results.
- When all threads finish, return results.
Walkthrough with startUrl = "http://example.com":
- Queue: ["http://example.com"]. Visited: {"http://example.com"}.
- Thread 1 dequeues "http://example.com", fetches it, finds links: ["http://example.com/a", "http://example.com/b"].
- Both are same hostname, add to visited and queue.
- Queue: ["http://example.com/a", "http://example.com/b"].
- Thread 1 dequeues "http://example.com/a", fetches, finds ["http://example.com/c"].
- Thread 2 dequeues "http://example.com/b", fetches, finds nothing.
- Continue until queue is empty.
Time: O(N * F) where N = URLs, F = fetch time. Space: O(N).
Shared queue, many workers
What Trips People Up in Real Interviews
Not using proper synchronization on the shared visited set. If two threads check the same URL simultaneously, both might add it. Use a lock around the check-and-add operation, or use a concurrent set.
Creating too many threads. The thread pool should be fixed-size (e.g., 4-8 threads). Creating a new thread per URL causes thread explosion and context-switching overhead.
Forgetting to handle the case where the queue is empty but threads are still working. Use a condition variable or event to signal all threads to stop when no more URLs remain.
Not handling fetch failures gracefully. If a URL fails to fetch (timeout, 404, etc.), skip it and move on. Do not let one failed fetch block the entire crawler.
Confusing BFS with DFS. BFS is preferred for crawling because it explores breadth-first (closer pages first) and naturally terminates when the queue is empty. DFS can get stuck in deep chains.
Solution Code
O(N * F) timeimport threading
from urllib.parse import urlparse
class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> list[str]:
hostname = urlparse(startUrl).hostname
visited = set()
visited.add(startUrl)
queue = [startUrl]
lock = threading.Lock()
results = []
done = threading.Event()
def worker():
while True:
url = None
with lock:
if queue:
url = queue.pop(0)
else:
done.wait(timeout=0.1)
if queue:
url = queue.pop(0)
elif done.is_set():
return
else:
continue
pages = htmlParser.getUrls(url)
with lock:
results.append(url)
for link in pages:
if urlparse(link).hostname == hostname:
with lock:
if link not in visited:
visited.add(link)
queue.append(link)
threads = [threading.Thread(target=worker) for _ in range(4)]
for t in threads:
t.start()
for t in threads:
t.join()
done.set()
return resultsFrequently Asked Questions
What is the Web Crawler Multithreaded problem?
Design a multithreaded web crawler that starts from a given URL and crawls all URLs within the same hostname. The crawler should use multiple threads to fetch pages concurrently and return a list of all crawled URLs. This problem tests your ability to combine BFS with thread pool management.
How do you solve Web Crawler Multithreaded?
The optimal approach runs in O(N * F) time and O(N) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Web Crawler Multithreaded?
Web Crawler Multithreaded is asked at Anthropic. It is a medium difficulty problem.
What are common mistakes on Web Crawler Multithreaded?
- Not using proper synchronization on the shared `visited` set. If two threads check the same URL simultaneously, both might add it. Use a lock around the check-and-add operation, or use a concurrent set.
- Creating too many threads. The thread pool should be fixed-size (e.g., 4-8 threads). Creating a new thread per URL causes thread explosion and context-switching overhead.
- Forgetting to handle the case where the queue is empty but threads are still working. Use a condition variable or event to signal all threads to stop when no more URLs remain.
- Not handling fetch failures gracefully. If a URL fails to fetch (timeout, 404, etc.), skip it and move on. Do not let one failed fetch block the entire crawler.
- Confusing BFS with DFS. BFS is preferred for crawling because it explores breadth-first (closer pages first) and naturally terminates when the queue is empty. DFS can get stuck in deep chains.