Web Crawler

Medium Graphs BFS / DFS Basics Original on LeetCode

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.io is a different hostname, so it is skipped. The link from /help back 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/z shares the hostname, but the only way to reach it goes through b.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 most 300 characters long.
  • The hostname is the part between http:// and the next / (or the end of the URL); it has 1 to 63 lowercase letters, digits, . or -.
  • startUrl is one of the pages; getUrls may 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.

00:00
Testcase

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.

ApproachTimeSpace
Recursive DFSO(N + E)O(N)
Optimal (iterative BFS)O(N + E)O(N)

1Recursive DFS

TimeO(N + E)Each page is fetched once and each returned link is checked once (hostname extraction is bounded by the URL length).
SpaceO(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.

  1. Compute the hostname of startUrl; add startUrl to seen.
  2. dfs(url): for every link from getUrls(url), if it is new and has the same hostname, add it to seen and call dfs on it.
  3. 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);
    }
}

2Optimal (iterative BFS)

TimeO(N + E)Every page is dequeued and fetched once; every link is examined once.
SpaceO(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.

  1. Compute the start hostname; put startUrl in seen and in the queue.
  2. Pop a URL, fetch its links; push each new same-host link and mark it seen.
  3. 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);
    }
}

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.io vs blog.shop.io vs shop.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.