1236. Web Crawler
Asked at Anthropic
Difficulty
Medium
Time
O(n + e)
Space
O(n)
Pattern
String
Companies
1
Problem
You are given a starting URL called startUrl and an object HtmlParser. That object has one method: getUrls(url) returns a list of all URLs that appear as links on the page at url.
Write a crawler that starts at startUrl and follows links. You may only visit pages that share the same hostname as startUrl. The hostname is the part right after http:// and before the next /. For example, in http://news.yahoo.com/news, the hostname is news.yahoo.com. Links pointing to any other hostname must be ignored, and you must never crawl the same URL twice.
Return the list of all URLs you visited, in any order. Note that a URL with a trailing slash is a different URL from the same URL without it, so http://news.yahoo.com and http://news.yahoo.com/ are two separate pages.
Crawl only inside one hostname
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 '-', and may not start or end with '-' - ●
There are no duplicate URLs in the library - ●
You may assume all URLs use http with no port number
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
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.
BFS with a visited set
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
O(n + e) timefrom 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 runs in O(n + e) 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?
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