Mid/Senior
Web Crawler Multithreaded
Given a starting URL startUrl, crawl all URLs that are reachable from it and belong to the same hostname as startUrl.
A URL has the form http://hostname/path, where the path may be empty. The hostname is the part after http:// and before the next /, if any.
In the original problem, you are given an HtmlParser interface where HtmlParser.getUrls(url) returns all URLs linked from url. For this problem entry, the web graph is represented by:
urls, a list of unique URLs.edges, where each edge[i, j]meansurls[i]links tourls[j].
Starting from startUrl, return all URLs that can be reached by repeatedly following links, but only include and continue crawling URLs whose hostname is the same as the hostname of startUrl.
Your crawler must:
- Never crawl the same URL more than once.
- Ignore URLs with a different hostname from
startUrl. - Return the reachable same-hostname URLs in any order.
- Be designed so that visits to shared state would be thread-safe in a multithreaded implementation.
Example 1
Input
start_url = "http://news.yahoo.com/news/topics/", 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]]Output
["http://news.yahoo.com/news/topics/","http://news.yahoo.com","http://news.yahoo.com/news","http://news.yahoo.com/us"]Starting from the topics page, the crawler can reach the Yahoo URLs with the same hostname, but it must ignore the Google URL.
Example 2
Input
start_url = "http://news.google.com", 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 = [[0,2],[2,1],[3,2],[3,1],[0,4]]Output
["http://news.google.com"]The start URL is on the Google hostname, and the only reachable same-hostname URL is the start URL itself.
Constraints
- 1 <= urls.length <= 1000
- 1 <= urls[i].length <= 300
- 0 <= edges.length <= 5000
- edges[i].length == 2
- 0 <= edges[i][0], edges[i][1] < urls.length
- startUrl is one of the values in urls
- All urls are unique
- Each url begins with "http://" and contains a hostname followed by an optional path
- Hostnames consist of lowercase English letters, hyphens, and dots