Learning On the Way

1242. Web Crawler Multithreaded

Given a url startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl.

Return all urls obtained by your web crawler in any order.

Your crawler should:

• Start from the page: startUrl
• Call HtmlParser.getUrls(url) to get all urls from a webpage of given url.
• Do not crawl the same link twice.
• Explore only the links that are under the same hostname as startUrl.

As shown in the example url above, the hostname is example.org. For simplicity sake, you may assume all urls use http protocol without any port specified. For example, the urls http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while urls http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

interface HtmlParser { // Return a list of all urls from a webpage of given url. // This is a blocking call, that means it will do HTTP request and return when this request is finished. public List getUrls(String url); } Note that getUrls(String url) simulates performing a HTTP request. You can treat it as a blocking function call which waits for a HTTP request to finish. It is guaranteed that getUrls(String url) will return the urls within 15ms. Single-threaded solutions will exceed the time limit so, can your multi-threaded web crawler do better?

Follow up:

Assume we have 10,000 nodes and 1 billion URLs to crawl. We will deploy the same software onto each node. The software can know about all the nodes. We have to minimize communication between machines and make sure each node does equal amount of work.

• How would your web crawler design change?
• What if one node fails or does not work?
• How do you know when the crawler is done?

from concurrent import futures

class Solution:
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        hostname = lambda url: url.split('/')[2]
        seen = {startUrl}
    
        with futures.ThreadPoolExecutor(max_workers=16) as executor:
            tasks = deque([executor.submit(htmlParser.getUrls, startUrl)])
            while tasks:
                for url in tasks.popleft().result():
                    if url not in seen and hostname(startUrl) == hostname(url):
                        seen.add(url)
                        tasks.append(executor.submit(htmlParser.getUrls, url))
        
        return list(seen)

class Solution { 
public: 
    string get_hostname(const string& url) 
    { 
        int start = url.find("/") + 2; 
        int end = url.find("/", start); 
        if (end == string::npos) 
        { 
            return url.substr(start); 
        } 
        else 
        { 
            return url.substr(start, end - start); 
        } 
    } 
     
    void work(HtmlParser& htmlParser) 
    { 
        while (true) 
        { 
            unique_lock<mutex> lk(m); 
            cv.wait(lk, [&](){ 
                return done || !s.empty(); 
                }); 
            if (done) 
            { 
                return; 
            } 
            string cur = s.top(); 
            s.pop(); 
            working++; 
            lk.unlock(); 
            cv.notify_all(); 
            vector<string> urls = htmlParser.getUrls(cur); 
             
            lk.lock(); 
            for (const auto& url : urls) 
            { 
                if (target_hostname == get_hostname(url) && seen.find(url) == seen.end()) 
                { 
                    seen.insert(url); 
                    s.push(url); 
                } 
            } 
             
            working--; 
            if (working == 0 && s.empty()) 
            { 
                done = true; 
            } 
             
            lk.unlock(); 
            cv.notify_all(); 
        } 
    } 
     
    vector<string> crawl(string startUrl, HtmlParser htmlParser) { 
         
        seen.insert(startUrl); 
        s.push(startUrl); 
        target_hostname = get_hostname(startUrl); 
         
        vector<thread> threads; 
        int num_threads = 16; 
         
        for (size_t i = 0; i < num_threads; ++i) 
        { 
            threads.emplace_back(&Solution::work, this, ref(htmlParser));
        } 
         
        for (size_t i = 0; i < num_threads; ++i) 
        { 
            threads[i].join(); 
        } 
         
        return vector(seen.begin(), seen.end()); 
    } 
private: 
    mutex m; 
    int working = 0; 
    bool done = false;     
    condition_variable cv; 
    stack<string> s; 
    unordered_set<string> seen; 
    string target_hostname{}; 
};