1236. Web Crawler

Problem Description

The task is to implement a web crawler that crawls all URLs that are under the same hostname as the starting URL. A crawler is typically a program that systematically browses the Web or a website information to create an index of data. In this problem, you are given a starting URL and an HtmlParser interface with a getUrls method that, when called, returns all URLs found on a given webpage.

Here are the key requirements for the crawler:

• The crawler begins from the page specified by startUrl.
• It should call the HtmlParser.getUrls(url) method to retrieve all URLs from the webpage at the specified URL.
• The crawler should prevent visiting the same URL more than once to avoid infinite loops and redundant operations.
• Only URLs with the same hostname as the startUrl should be crawled. The hostname is the portion of the URL that usually includes the domain name and the top-level domain, but, for the purpose of this problem, it excludes subdomains, protocols (like http), and ports.
• While the question mentions that URLs with or without a trailing slash are considered different, it doesn't play a significant role in the implementation of the solution provided because the crawled URLs are obtained from the getUrls method, which should handle this distinction.

The description implies storing crawled URLs and making sure that new URLs are only crawled if they belong to the same domain and haven't been crawled before.

Intuition

The intuition behind the solution is to perform a depth-first search (DFS) on the URLs, starting from startUrl. Depth-first search is a recursive algorithm that uses the concept of backtracking. It involves exhaustive searches of all the nodes by going ahead, if possible, else by backtracking. This approach perfectly aligns with the nature of web crawling, where we dive deep into one link (node) before moving to adjacent links.

To implement DFS effectively and adhere to the key requirements, the following aspects are essential:

• A mechanism to determine the hostname from a given URL, so we can compare whether subsequent URLs belong to the same host as the startUrl.
• A data structure to keep track of the URLs that have already been visited. A set is ideal in this scenario to avoid duplicates efficiently.
• A recursive function that performs the DFS. It should:
  • Add the current URL to the list of visited URLs.
  • Retrieve all URLs linked from the current URL using the getUrls method.
  • For each retrieved URL, check if the hostname matches the startUrl's hostname and recurse only if the URL hasn't been visited yet.

This process creates a recursive traversal that explores each URL within the same hostname and builds up the set of all visited URLs, which is the final result.

The provided solution encodes this intuition. The host function extracts the hostname from the URL, the dfs function embodies the depth-first traversal logic, and the ans set maintains the record of visited URLs to ensure each URL is only crawled once.

Learn more about Depth-First Search and Breadth-First Search patterns.

Solution Approach

The solution is implemented using a classic DFS algorithm. Let's walk through the implementation step by step.

First, we define a helper function named host that parses a given URL to return its hostname. The function assumes that all URLs begin with "http://" (length 7 characters), so it strips this part before splitting the URL by '/' and returning the first part, which is the hostname:

1def host(url):
2    url = url[7:]
3    return url.split('/')[0]

Next, we define a recursive function dfs that performs the depth-first search. This function takes an url as an argument:

• It first checks if the URL is already in the set named ans, which is used to store crawled URLs. If the URL is already in the set, the function returns immediately to avoid processing the same URL twice.
• If the URL is not in the set, it's added to ans.
• Then, for each URL retrieved by the HtmlParser.getUrls(url) call, the function checks whether each of those URLs shares the same hostname as our original startUrl. If it does, the function is recursively called with the new URL.

1def dfs(url):
2    if url in ans:
3        return
4    ans.add(url)
5    for next_url in htmlParser.getUrls(url):
6        if host(url) == host(next_url):
7            dfs(next_url)

Finally, we define the set ans as an empty set, used to store the unique URLs:

1ans = set()

And we start the DFS crawl from the startUrl:

1dfs(startUrl)

After the DFS is complete, ans contains all the unique URLs that share the same hostname as the startUrl and have been crawled. As per the requirements, the function returns a list of these URLs:

1return list(ans)

The beauty of this approach is its simplicity and effectiveness. Using DFS allows us to deep dive into each path of linked URLs while keeping track of visited URLs through the ans set to avoid revisits, which could lead to infinite loops. Filter URLs with the same hostname ensures that we're adhering to the crawling boundaries set by the problem.

This solution effectively uses basic string manipulation for URL parsing, recursive DFS for navigating through links, and a set data structure to manage visited URLs.

Example Walkthrough

Let's walk through a small example to illustrate how the solution operates. Suppose we have the following web pages and links between them and are provided with the starting URL "http://example.com/a":

• "http://example.com/a" links to ["http://example.com/b", "http://example.com/c"]
• "http://example.com/b" links to ["http://example.com/a"] (back-link to a)
• "http://example.com/c" links to [] (no links)

The HtmlParser.getUrls method simulates the links as follows for each URL:

1def getUrls(url):
2    links = {
3        "http://example.com/a": ["http://example.com/b", "http://example.com/c"],
4        "http://example.com/b": ["http://example.com/a"],
5        "http://example.com/c": []
6    }
7    return links[url]

Applying the solution:

1. We begin with the dfs function called on the startUrl which is "http://example.com/a".
2. First, we use the host function to determine the hostname. For "http://example.com/a", the hostname is "example.com".
3. Since this URL has not been visited yet, we add it to the ans set.
4. We call HtmlParser.getUrls("http://example.com/a") and receive two URLs: "http://example.com/b" and "http://example.com/c".
5. For each of these URLs, we check the hostname using the host function and compare it to our start URL's hostname "example.com". They match, so we proceed to call dfs recursively on these URLs.
6. The dfs call on "http://example.com/b" adds this URL to the ans set and then calls HtmlParser.getUrls on this URL, which only returns "http://example.com/a". However, since "http://example.com/a" is already in the ans set, it doesn't recurse on it to avoid a loop.
7. Similarly, the dfs call on "http://example.com/c" adds the URL to the ans set. HtmlParser.getUrls("http://example.com/c") returns an empty list, so there are no further URLs to process.
8. At the end of this process, the ans set contains {"http://example.com/a", "http://example.com/b", "http://example.com/c"}, which are the unique URLs that were crawled.
9. We return the list form of the ans set, giving us our final result: ["http://example.com/a", "http://example.com/b", "http://example.com/c"].

This walkthrough demonstrates the DFS-based crawling, visiting each unique URL starting from the startUrl and respecting the same hostname constraint without visiting any URL more than once.

Solution Implementation

Time and Space Complexity

The given Python function implements a Depth-First Search (DFS) to crawl web pages. Here's the analysis of the time complexity and space complexity:

Time Complexity

The time complexity of the code is governed by the number of URLs that are visited and the number of out-links that each URL contains. If we assume there are N unique URLs and each URL could have at most D out-links we will visit:

• Each URL is processed once, and for each URL, the getUrls method of HtmlParser could be called. This operation is O(1) for each URL since we are just processing the URL and not actually parsing HTML (parsing in reality would depend on the HTML content size).
• However, each URL could link out to D other URLs. In the worst case where all URLs point to all other URLs, each edge (link) would effectively be visited once.

Therefore, the time complexity is O(N + N * D), which simplifies to O(ND) as each URL is expanded once and then each out-link is explored.

Space Complexity

The space complexity comprises the memory required for the recursive call stack when performing DFS as well as the memory required to store the set of visited URLs:

• The recursive DFS could go as deep as N if there is a URL that leads to a long chain of other URLs. This contributes O(N) to the space complexity.
• The ans set is used to store unique URLs that are visited. In the worst-case scenario where all URLs are accessible from the starting URL, this set contributes O(N).

Combining the two gives us O(2N), which simplifies to O(N) space complexity.

In summary:

• Time Complexity: O(ND)
• Space Complexity: O(N)

Learn more about how to find time and space complexity quickly using problem constraints.