LeetCode 1242: Web Crawler Multithreaded Solution

Master LeetCode problem 1242 (Web Crawler Multithreaded), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1242. Web Crawler Multithreaded

Medium

Depth-First Search Breadth-First Search Concurrency

Problem Explanation

Explanation:

This problem involves implementing a multithreaded web crawler, where multiple threads work together to crawl a given set of URLs. The main idea is to have a shared queue of URLs to be crawled and multiple threads that fetch a URL from the queue, crawl it, extract more URLs from the crawled page, and add them back to the queue for processing by other threads.

Algorithm:

Create a shared queue to store URLs to be crawled.
Initialize a set to keep track of visited URLs to avoid duplicates.
Implement a function to fetch a URL, crawl it, extract more URLs, and add them to the queue and visited set.
Create multiple threads that continuously fetch URLs from the queue, crawl them, and repeat the process until all URLs are crawled.
Ensure thread safety by using synchronization mechanisms like locks to access the shared queue and visited set.

Time Complexity:

The time complexity of this algorithm depends on the number of URLs to be crawled and the efficiency of the crawling process. Let's denote N as the number of URLs.
In the worst-case scenario, each URL might lead to extracting multiple new URLs, resulting in a total of O(N) URLs to be crawled.
The time complexity can be O(N) in the worst case.

Space Complexity:

The space complexity is also influenced by the number of URLs to be crawled and the storage required for the shared queue and visited set.
The space complexity can be O(N) in the worst case.

Solution Code

// Java Solution
import java.util.concurrent.*;
import java.util.HashSet;
import java.util.Set;

class WebCrawlerMultithreaded {
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {
        Set<String> visited = new HashSet<>();
        visited.add(startUrl);
        
        BlockingQueue<String> queue = new LinkedBlockingQueue<>();
        queue.add(startUrl);
        
        int numOfThreads = 4; // Number of threads to use
        
        ExecutorService executor = Executors.newFixedThreadPool(numOfThreads);
        
        for (int i = 0; i < numOfThreads; i++) {
            executor.execute(() -> {
                while (true) {
                    String url = queue.poll();
                    if (url == null) break;
                    
                    for (String nextUrl : htmlParser.getUrls(url)) {
                        if (!visited.contains(nextUrl)) {
                            visited.add(nextUrl);
                            queue.add(nextUrl);
                        }
                    }
                }
            });
        }
        
        executor.shutdown();
        try {
            executor.awaitTermination(Long.MAX_VALUE, TimeUnit.NANOSECONDS);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        
        return new ArrayList<>(visited);
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1242 (Web Crawler Multithreaded)?

This page provides optimized solutions for LeetCode problem 1242 (Web Crawler Multithreaded) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1242 (Web Crawler Multithreaded)?

The time complexity for LeetCode 1242 (Web Crawler Multithreaded) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1242 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1242 in Java, C++, or Python.

Back to LeetCode Solutions