Web Crawler
Asked at Anthropic
Problem
Design a web crawler that given a starting URL, crawls all URLs reachable within the same domain up to a maximum depth. The crawler should return all unique URLs visited. This problem tests your ability to design a system with BFS/DFS traversal, URL normalization, and duplicate detection.
Asked At
| Company | Difficulty | |
|---|---|---|
| Anthropic | MEDIUM | View all Anthropic questions → |
How to Think About It
Use BFS with a queue to crawl URLs level by level up to the given depth
Maintain a visited set to avoid crawling the same URL twice
Parse the HTML to extract all href links from anchor tags
Filter URLs to only include those belonging to the same domain as the start URL
Normalize URLs to handle trailing slashes, fragments, and relative paths
Optimal Approach
Use BFS starting from the seed URL. Maintain a queue of (url, depth) pairs and a visited set. At each step, dequeue a URL, fetch its HTML content, and extract all links using regex or an HTML parser. Normalize each extracted URL and filter to keep only those in the same domain. For unvisited URLs within the depth limit, enqueue them. The visited set prevents re-crawling. BFS ensures fair coverage and prevents deep recursive crawls that could get stuck. URL normalization handles edge cases like trailing slashes and relative paths.
What Trips People Up in Real Interviews
Clarify whether you need to handle redirects or just static pages
Ask about the depth limit: does depth 0 mean only the start URL?
Discuss how to extract links from HTML (regex vs parser)
Mention rate limiting and politeness considerations in production
Talk about scaling: distributed crawling, BFS preferred over DFS for fairness
Solution Code
from collections import deque
class Solution:
def crawl(self, startUrl: str, htmlSnippets: callable) -> list[str]:
def get_hostname(url):
return url.split('/')[2]
def get_links(html, base_url):
import re
links = set()
for match in re.findall(r'href=["\']([^"\']*)["\'']', html):
if match.startswith('/'):
match = base_url.split('/')[0] + '//' + base_url.split('/')[2] + match
elif not match.startswith('http'):
match = base_url.rsplit('/', 1)[0] + '/' + match
links.add(match.split('#')[0])
return links
hostname = get_hostname(startUrl)
visited = set([startUrl])
queue = deque([(startUrl, 0)])
result = []
while queue:
url, depth = queue.popleft()
result.append(url)
if depth >= 10:
continue
html = htmlSnippets(url)
for link in get_links(html, url):
if link not in visited and get_hostname(link) == hostname:
visited.add(link)
queue.append((link, depth + 1))
return resultFrequently Asked Questions
What is the Web Crawler problem?
Design a web crawler that given a starting URL, crawls all URLs reachable within the same domain up to a maximum depth. The crawler should return all unique URLs visited. This problem tests your ability to design a system with BFS/DFS traversal, URL normalization, and duplicate detection.
How do you solve Web Crawler?
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?
Web Crawler is asked at Anthropic. It is a medium difficulty problem.
What are common mistakes on Web Crawler?
- Clarify whether you need to handle redirects or just static pages
- Ask about the depth limit: does depth 0 mean only the start URL?
- Discuss how to extract links from HTML (regex vs parser)
- Mention rate limiting and politeness considerations in production
- Talk about scaling: distributed crawling, BFS preferred over DFS for fairness