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<String> 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.

Example 1:

Input:
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]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

Example 2:

Input: 
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com"
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = "http://news.google.com"
Output: ["http://news.google.com"]
Explanation: The startUrl links to all other pages that do not share the same hostname.

Constraints:

• 1 <= urls.length <= 1000
• 1 <= urls[i].length <= 300
• startUrl is one of the urls.
• Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from 'a' to 'z', digits from '0' to '9' and the hyphen-minus character ('-').
• The hostname may not start or end with the hyphen-minus character ('-'). 
• See:  https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
• You may assume there're no duplicates in the URL library.

Follow up:

1. 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?
2. What if one node fails or does not work?
3. How do you know when the crawler is done?

1. 10,000 nodes, 1 billion URLs

The main goals are:

• distribute work evenly
• avoid crawling the same URL twice
• minimize network communication

The key idea is partition URLs by hashing.

Partition ownership

Suppose there are N machines.

Each URL has a unique owner.

For example

Each URL always belongs to exactly one machine.

This immediately solves duplicate crawling.

Crawling

Machine A crawls one page

It discovers

Instead of checking all URLs locally, it computes

Then sends

Each node only stores

• visited URLs it owns
• work queue it owns

No global visited set exists.

Why communication is minimized

Without partitioning

That's terrible.

With consistent ownership

Only one network message.

Load balancing

A good hash distributes URLs uniformly.

Expected work

Very balanced.

Better partitioning

Instead of

real systems use

• Consistent Hashing

because machines may join or leave.

Otherwise

2. What if one node fails?

Need fault tolerance.

Several approaches.

Option 1 (most common)

Persist work queue.

Instead of

use

• Kafka
• SQS
• Redis Streams

If machine dies

another worker continues.

Option 2

Replication.

Each partition has

If primary dies

Replica becomes primary.

Exactly like

Option 3

Checkpoint visited URLs.

Suppose machine processed

Persist

Crash

Restart

Continue.

Interview answer:

Each partition should periodically persist its frontier and visited metadata (or store them in a replicated distributed queue/database). If a worker fails, another worker can take ownership of that partition and resume crawling without starting over.

3. How do you know crawler is finished?

This is the interesting one.

In one machine

works.

Distributed?

No.

Machine A

Machine B

Machine A isn't actually done.

Need global termination detection.

Simple solution

Coordinator.

Each node periodically reports

Crawler finishes when

Every node

Need to account for messages in flight.

Example

Cannot terminate early.

Real systems maintain

or

When

Done.

More sophisticated algorithms exist.

Examples

• Dijkstra-Scholten termination detection
• Credit distribution
• Token algorithms

Usually unnecessary in interviews.

Complete interview answer

A concise answer might be:

I would partition the URL space across machines using a deterministic hash (or consistent hashing), so each URL has a single owner. Each node maintains only the visited set and work queue for the URLs it owns. When a node crawls a page and discovers new URLs, it hashes each URL and forwards it only to its owner. This avoids duplicate crawling, balances work across machines, and minimizes communication because every URL is sent to exactly one destination instead of broadcasting lookups.

For fault tolerance, I would persist each partition's frontier in a durable distributed queue or replicate partitions so another node can take over if one fails. A failed worker can resume from the last checkpoint instead of restarting.

To detect completion, I would use a coordinator that tracks whether every node's work queue is empty, all workers are idle, and there are no URLs currently being transferred between nodes. Only when all three conditions hold can the distributed crawler safely terminate.

This demonstrates understanding of partitioning, fault tolerance, and distributed termination detection, which are the core concepts interviewers are looking for.

# """
# This is HtmlParser's API interface.
# You should not implement it, or speculate about its implementation
# """
#class HtmlParser(object):
#    def getUrls(self, url):
#        """
#        :type url: str
#        :rtype List[str]
#        """

from typing import List
from threading import Thread, Lock
from queue import Queue
from urllib.parse import urlparse


class Solution:
    def crawl(self, startUrl: str, htmlParser: 'HtmlParser') -> List[str]:
        hostname = urlparse(startUrl).netloc

        visited = {startUrl}
        lock = Lock()

        q = Queue()
        q.put(startUrl)

        def worker():
            while True:
                url = q.get()

                # Sentinel: stop the worker.
                if url is None:
                    q.task_done()
                    break

                try:
                    for next_url in htmlParser.getUrls(url):
                        if urlparse(next_url).netloc != hostname:
                            continue

                        with lock:
                            if next_url in visited:
                                continue
                            visited.add(next_url)

                        q.put(next_url)
                finally:
                    q.task_done()

        NUM_THREADS = 8
        threads = []

        for _ in range(NUM_THREADS):
            t = Thread(target=worker)
            t.start()
            threads.append(t)

        # Wait until all URLs have been processed.
        q.join()

        # Stop all workers.
        for _ in range(NUM_THREADS):
            q.put(None)

        for t in threads:
            t.join()

        return list(visited)

 You call q.join() when you want to wait until all queued tasks have been processed.

Without it:

the main thread may continue before workers finish.

Internally:

• every put() increments an unfinished task counter
• every task_done() decrements it
• q.join() blocks until the counter reaches 0

For producer-consumer problems like 1242. Web Crawler Multithreaded, the common pattern is: