Web Crawler
Web Crawler is a medium graphs problem solved with the bfs / dfs basics pattern.
The best approach, optimal (iterative bfs), runs in O(N + E) time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive dfs up.
Problem
You are given a starting address startUrl and an HtmlParser object. Calling htmlParser.getUrls(url) returns the list of links found on the page at url. You cannot see the pages any other way.
Crawl the web starting from startUrl and return every URL you can reach that has the same hostname as startUrl, including startUrl itself, in any order. Only follow links whose hostname matches; never crawl the same URL twice.
Every URL has the form http://hostname or http://hostname/path.... The hostname is the text between http:// and the next / (or the end of the URL). For example, http://news.site.org/a/b has hostname news.site.org, which is different from site.org.
Examples
Example 1
- Input
pages: http://shop.io -> [http://shop.io/cart, http://blog.shop.io], http://shop.io/cart -> [http://shop.io/help], http://shop.io/help -> [http://shop.io], startUrl = "http://shop.io"- Output
["http://shop.io", "http://shop.io/cart", "http://shop.io/help"]- Why
blog.shop.iois a different hostname, so it is skipped. The link from/helpback to the start page is not crawled a second time.
Example 2
- Input
pages: http://a.dev/x -> [http://b.dev, http://a.dev/y], http://b.dev -> [http://a.dev/z], startUrl = "http://a.dev/x"- Output
["http://a.dev/x", "http://a.dev/y"]- Why
http://a.dev/zshares the hostname, but the only way to reach it goes throughb.dev, which is never crawled.
Example 3
- Input
pages: http://solo.net/home -> [], startUrl = "http://solo.net/home"- Output
["http://solo.net/home"]- Why
- A page with no links: only the start page is returned.
Constraints
1 <= number of pages <= 1000,0 <= number of links <= 5000- Every URL starts with
http://, has no port, and is at most300characters long. - The hostname is the part between
http://and the next/(or the end of the URL); it has1to63lowercase letters, digits,.or-. startUrlis one of the pages;getUrlsmay return the same URL more than once or link a page to itself.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 9 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive DFS | O(N + E) | O(N) |
| Optimal (iterative BFS) | O(N + E) | O(N) |
1Recursive DFS
O(N + E)Each page is fetched once and each returned link is checked once (hostname extraction is bounded by the URL length).O(N)The seen set plus a recursion stack that can be as deep as the number of pages.Treat each page as a graph node. Starting from startUrl, recurse into every linked URL that has the same hostname and has not been seen yet. The seen set is also the answer.
- Compute the hostname of
startUrl; addstartUrltoseen. - dfs(url): for every link from
getUrls(url), if it is new and has the same hostname, add it toseenand call dfs on it. - Return the contents of
seen.
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = hostOf(startUrl);
Set<String> seen = new HashSet<>();
seen.add(startUrl);
dfs(startUrl, host, htmlParser, seen);
return new ArrayList<>(seen);
}
private void dfs(String url, String host, HtmlParser parser, Set<String> seen) {
for (String next : parser.getUrls(url)) {
if (!seen.contains(next) && hostOf(next).equals(host)) {
seen.add(next);
dfs(next, host, parser, seen);
}
}
}
private String hostOf(String url) {
int end = url.indexOf('/', 7);
return end == -1 ? url.substring(7) : url.substring(7, end);
}
}class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
host = self.hostOf(startUrl)
seen = {startUrl}
self.dfs(startUrl, host, htmlParser, seen)
return list(seen)
def dfs(self, url: str, host: str, parser: 'HtmlParser', seen: Set[str]) -> None:
for nxt in parser.getUrls(url):
if nxt not in seen and self.hostOf(nxt) == host:
seen.add(nxt)
self.dfs(nxt, host, parser, seen)
def hostOf(self, url: str) -> str:
end = url.find('/', 7)
return url[7:] if end == -1 else url[7:end]class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
string host = hostOf(startUrl);
unordered_set<string> seen;
seen.insert(startUrl);
dfs(startUrl, host, htmlParser, seen);
return vector<string>(seen.begin(), seen.end());
}
private:
void dfs(const string& url, const string& host, HtmlParser& parser, unordered_set<string>& seen) {
for (const string& next : parser.getUrls(url)) {
if (!seen.count(next) && hostOf(next) == host) {
seen.insert(next);
dfs(next, host, parser, seen);
}
}
}
string hostOf(const string& url) {
size_t end = url.find('/', 7);
return end == string::npos ? url.substr(7) : url.substr(7, end - 7);
}
};function crawl(startUrl, htmlParser) {
const host = hostOf(startUrl);
const seen = new Set([startUrl]);
dfs(startUrl, host, htmlParser, seen);
return [...seen];
}
function dfs(url, host, parser, seen) {
for (const next of parser.getUrls(url)) {
if (!seen.has(next) && hostOf(next) === host) {
seen.add(next);
dfs(next, host, parser, seen);
}
}
}
function hostOf(url) {
const end = url.indexOf('/', 7);
return end === -1 ? url.substring(7) : url.substring(7, end);
}2Optimal (iterative BFS)
O(N + E)Every page is dequeued and fetched once; every link is examined once.O(N)The seen set and the queue each hold at most N URLs.Same graph walk, but with an explicit queue instead of recursion, so a long chain of pages cannot overflow the call stack. A URL is marked as seen the moment it is queued, so no page is ever fetched twice.
- Compute the start hostname; put
startUrlinseenand in the queue. - Pop a URL, fetch its links; push each new same-host link and mark it seen.
- When the queue is empty, return
seen.
class Solution {
public List<String> crawl(String startUrl, HtmlParser htmlParser) {
String host = hostOf(startUrl);
Set<String> seen = new HashSet<>();
Deque<String> queue = new ArrayDeque<>();
seen.add(startUrl);
queue.add(startUrl);
while (!queue.isEmpty()) {
String url = queue.poll();
for (String next : htmlParser.getUrls(url)) {
if (!seen.contains(next) && hostOf(next).equals(host)) {
seen.add(next);
queue.add(next);
}
}
}
return new ArrayList<>(seen);
}
private String hostOf(String url) {
int end = url.indexOf('/', 7);
return end == -1 ? url.substring(7) : url.substring(7, end);
}
}class Solution:
def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
host = self.hostOf(startUrl)
seen = {startUrl}
queue = deque([startUrl])
while queue:
url = queue.popleft()
for nxt in htmlParser.getUrls(url):
if nxt not in seen and self.hostOf(nxt) == host:
seen.add(nxt)
queue.append(nxt)
return list(seen)
def hostOf(self, url: str) -> str:
end = url.find('/', 7)
return url[7:] if end == -1 else url[7:end]class Solution {
public:
vector<string> crawl(string startUrl, HtmlParser htmlParser) {
string host = hostOf(startUrl);
unordered_set<string> seen;
queue<string> q;
seen.insert(startUrl);
q.push(startUrl);
while (!q.empty()) {
string url = q.front();
q.pop();
for (const string& next : htmlParser.getUrls(url)) {
if (!seen.count(next) && hostOf(next) == host) {
seen.insert(next);
q.push(next);
}
}
}
return vector<string>(seen.begin(), seen.end());
}
private:
string hostOf(const string& url) {
size_t end = url.find('/', 7);
return end == string::npos ? url.substr(7) : url.substr(7, end - 7);
}
};function crawl(startUrl, htmlParser) {
const host = hostOf(startUrl);
const seen = new Set([startUrl]);
const queue = [startUrl];
for (let head = 0; head < queue.length; head++) {
for (const next of htmlParser.getUrls(queue[head])) {
if (!seen.has(next) && hostOf(next) === host) {
seen.add(next);
queue.push(next);
}
}
}
return [...seen];
}
function hostOf(url) {
const end = url.indexOf('/', 7);
return end === -1 ? url.substring(7) : url.substring(7, end);
}Edge cases to test
- The start page links to nothing
- Links that point back to pages already crawled (cycles)
- Hostnames that only share a suffix or a prefix (
shop.iovsblog.shop.iovsshop.io.evil) - A same-host page that is only reachable through another host
Hints
Hint 1
The pages and their links form a directed graph. Which traversal visits every reachable node exactly once?
Hint 2
Keep a set of URLs already seen and only follow a link when its hostname equals the start page's hostname.
Hint 3
Extract the hostname by cutting http:// (7 characters) and stopping at the next /.
FAQ
What is the best time complexity for Web Crawler?
Optimal (iterative BFS) runs in O(N + E) time and O(N) extra space. Every page is dequeued and fetched once; every link is examined once.
Which pattern does Web Crawler use?
It is a graphs problem that uses the bfs / dfs basics pattern. Other problems with the same pattern: BFS - Normal + Level by Level, DFS - Recursive + Iterative, Clone Graph.
Is there a brute force solution for Web Crawler?
Yes. Recursive DFS takes O(N + E) time and O(N) space. Treat each page as a graph node.
Which edge cases should I test for Web Crawler?
The start page links to nothing; Links that point back to pages already crawled (cycles); Hostnames that only share a suffix or a prefix (shop.io vs blog.shop.io vs shop.io.evil); A same-host page that is only reachable through another host.