Web crawler multithreaded

Depth-First Search Breadth-First Search Concurrency

51.1% acceptance

Mar 31, 2026

594

104

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 a 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's 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 an HTTP request. You can treat it as a blocking function call that waits for an 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? Below are two examples explaining the functionality of the problem. For custom testing purposes, you'll have three variables urls, edges and startUrl. Notice that you will only have access to startUrl in your code, while urls and edges are not directly accessible to you in code.

Solution

C++

Time O(n³)

Space O(1)

LeetCode

solution.cpp

/**
 * // This is the HtmlParser's API interface.
 * // You should not implement it, or speculate about its implementation
 * class HtmlParser {
 *   public:
 *     vector<string> getUrls(string url);
 * };
 */
class Solution {
public:
  string getHostname(const string& url) {
    int start = url.find("//") + 2;
    int end = url.find('/', start);
    return end == string::npos ? url.substr(start) : url.substr(start, end - start);
  }

  vector<string> crawl(string startUrl, HtmlParser htmlParser) {
    string hostname = getHostname(startUrl);
    unordered_set<string> visited;
    visited.insert(startUrl);
    vector<string> result = {startUrl};
    vector<future<vector<string>>> futures;

    queue<string> q;
    q.push(startUrl);

    while (!q.empty()) {
      futures.clear();
      vector<string> batch;
      while (!q.empty()) {
        batch.push_back(q.front());
        q.pop();
      }
      for (const string& url : batch) {
        futures.push_back(async(launch::async, [&htmlParser](const string& u) {
          return htmlParser.getUrls(u);
        }, url));
      }
      for (auto& f : futures) {
        for (const string& next : f.get()) {
          if (!visited.count(next) && getHostname(next) == hostname) {
            visited.insert(next);
            result.push_back(next);
            q.push(next);
          }
        }
      }
    }
    return result;
  }
};