Concurrency

1188. Design Bounded Blocking Queue

    Deque<Integer> d;
    int size;
    Object lock;
    public BoundedBlockingQueue(int capacity) {
        d = new LinkedList<>();
        size = capacity;
        lock = new Object();
    }
    
    public void enqueue(int element) throws InterruptedException {
        synchronized (lock) {
            while (d.size() == size) {
                lock.wait();
            }
            d.addLast(element);
            lock.notify();
        }
    }
    
    public int dequeue() throws InterruptedException {
        int val = 0;
        synchronized (lock) {
            while (d.isEmpty()) lock.wait();
            val = d.removeFirst();
            lock.notify();
        }
        return val;
    }
    
    public int size() {
        return d.size();
    }

Web Crawler with future

First Tab

import java.util.*;
import java.util.concurrent.*;

public interface WebsiteScanner {
    /**
     * Makes a call-out to the webpage and scrapes the HTML
     * for any hyperlinks to other URLs present in the webpage.
     *
     * @param url The URL of the webpage to scrape
     * @return A list of URLs (as strings) that are directly linked from the given webpage
     */
    List<String> getLinks(String url);
}

class Solution {

    /**
     * Finds the minimum number of hops required to navigate from webpageStart to webpageEnd.
     *
     * @param webpageStart The starting webpage URL
     * @param webpageEnd The target webpage URL
     * @param maxHops The maximum number of hops allowed
     * @param scanner WebsiteScanner instance to fetch links
     * @return The minimum number of hops, or -1 if not reachable within maxHops
     */
    public static int findMinimumHops(String webpageStart, String webpageEnd, int maxHops, WebsiteScanner scanner) {
        Set<String> visited = ConcurrentHashMap.newKeySet();
        Queue<String> queue = new LinkedList<>();
        ExecutorService executor = Executors.newFixedThreadPool(10);

        queue.offer(webpageStart);
        visited.add(webpageStart);
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Future<List<String>>> futures = new ArrayList<>();

            for (int i = 0; i < size; i++) {
                String current = queue.poll();
                if (current.equals(webpageEnd)) {
                    executor.shutdown();
                    return level;
                }

                futures.add(executor.submit(() -> scanner.getLinks(current)));
            }

            for (Future<List<String>> future : futures) {
                try {
                    for (String next : future.get()) {
                        if (visited.add(next)) {
                            queue.offer(next);
                        }
                    }
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }

            if (++level > maxHops) {
                executor.shutdown();
                return -1;
            }
        }

        executor.shutdown();
        return -1;
    }
}

Second Tab

import java.util.*;
import java.util.concurrent.*;

public class ConcurrentWebCrawler {

    public interface WebsiteScanner {
        List<String> getLinks(String url);
    }

    public static void crawl(String startUrl, WebsiteScanner scanner, int maxDepth) throws InterruptedException {
        Set<String> visited = ConcurrentHashMap.newKeySet(); // thread-safe visited set
        BlockingQueue<String> queue = new LinkedBlockingQueue<>();
        ExecutorService executor = Executors.newFixedThreadPool(10);

        visited.add(startUrl);
        queue.add(startUrl);

        for (int depth = 0; depth <= maxDepth; depth++) {
            int size = queue.size();
            if (size == 0) break;

            List<Future<List<String>>> tasks = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                String currentUrl = queue.poll();
                if (currentUrl == null) continue;

                String urlToCrawl = currentUrl;
                tasks.add(executor.submit(() -> scanner.getLinks(urlToCrawl)));
            }

            for (Future<List<String>> task : tasks) {
                try {
                    for (String link : task.get()) {
                        if (visited.add(link)) { // only if newly added
                            queue.add(link);
                        }
                    }
                } catch (ExecutionException e) {
                    System.err.println("Error crawling: " + e.getMessage());
                }
            }
        }

        executor.shutdown();
        executor.awaitTermination(5, TimeUnit.MINUTES);

        System.out.println("Crawled URLs:");
        for (String url : visited) {
            System.out.println(url);
        }
    }
}