Web Crawler Multithreaded
Asked at Anthropic
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.
Asked At
| 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).
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
import 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.