Concurrency

1114. Print in Order

Synchronized

class Foo {
    private int counter = 1;
    public Foo() {
    }

    public void first(Runnable printFirst) throws InterruptedException {
        synchronized (this) {
            while (counter != 1) {
                this.wait();
            }
            printFirst.run();
            counter = 2;
            this.notifyAll();
        }
        // printFirst.run() outputs "first". Do not change or remove this line.
    }

    public void second(Runnable printSecond) throws InterruptedException {
        synchronized (this) {
            while (counter != 2) {
                this.wait();
            }
            printSecond.run();
            counter = 3;
            this.notifyAll();
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        // printSecond.run();
    }

    public void third(Runnable printThird) throws InterruptedException {
        synchronized (this) {
            while (counter != 3) {
                this.wait();
            }
            printThird.run();
            counter = 1;
            this.notifyAll();
        }
    }
}

ReentrantLock

class Foo {
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();
    private volatile int count = 1;
    public Foo() {
        
    }

    public void first(Runnable printFirst) throws InterruptedException {
        lock.lock();
        try {
            while (count != 1) {
                condition.await();
            }
            // printFirst.run() outputs "first". Do not change or remove this line.
            printFirst.run();
            count = 2;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        lock.lock();
        try {
            while (count != 2) {
                condition.await();
            }
            printSecond.run();
            count = 3;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
        // printSecond.run() outputs "second". Do not change or remove this line.
        
    }

    public void third(Runnable printThird) throws InterruptedException {
        lock.lock();
        try {
            while (count != 3) {
                condition.await();
            }
            printThird.run();
            count = 1;
            condition.signalAll();
        } finally {
            lock.unlock();
        }
        
        // // printThird.run() outputs "third". Do not change or remove this line.
        // printThird.run();
    }
}

Semaphore

class Foo {
    private Semaphore firstSem = new Semaphore(1);
    private Semaphore secondSem = new Semaphore(0);
    private Semaphore thirdSem = new Semaphore(0);
    public Foo() {
    }

    public void first(Runnable printFirst) throws InterruptedException {
        firstSem.acquire();
        printFirst.run();
        secondSem.release();
        // printFirst.run() outputs "first". Do not change or remove this line.
    }

    public void second(Runnable printSecond) throws InterruptedException {
        secondSem.acquire();
        printSecond.run();
        thirdSem.release();
        // printSecond.run() outputs "second". Do not change or remove this line.
        // printSecond.run();
    }

    public void third(Runnable printThird) throws InterruptedException {
        thirdSem.acquire();
        printThird.run();
        firstSem.release();
    }
}

CompletableFuture

class Foo {
  private volatile CompletableFuture<Void> firstFuture = CompletableFuture.completedFuture(null);
    private volatile CompletableFuture<Void> secondFuture = new CompletableFuture<>();
    private volatile CompletableFuture<Void> thirdFuture = new CompletableFuture<>();

    public void first(Runnable printFirst) throws InterruptedException {
        try {
            firstFuture.get();
            printFirst.run();
            secondFuture.complete(null);
        } catch (ExecutionException e) {
            Thread.currentThread().interrupt();
        }
    }

    public void second(Runnable printSecond) throws InterruptedException {
        try {
            secondFuture.get();
            printSecond.run();
            thirdFuture.complete(null);
        } catch (ExecutionException e) {
            Thread.currentThread().interrupt();
        }
    }

    public void third(Runnable printThird) throws InterruptedException {
        try {
            thirdFuture.get();
            printThird.run();
            // Reset for next cycle
            firstFuture = CompletableFuture.completedFuture(null);
            secondFuture = new CompletableFuture<>();
            thirdFuture = new CompletableFuture<>();
        } catch (ExecutionException e) {
            Thread.currentThread().interrupt();
        }
    }
}

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();
    }

1115. Print FooBar Alternately

ReentrantLock

class FooBar {
    private int n;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition condition = lock.newCondition();
    private volatile boolean fooTurn = true;
    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            lock.lock();
            try {
                while (!fooTurn) {
                    condition.await();
                }
                printFoo.run();
                condition.signalAll();
                fooTurn = false;
            } finally {
                lock.unlock();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            lock.lock();
            try {
                while (fooTurn) {
                    condition.await();
                }
                printBar.run();
                condition.signalAll();
                fooTurn = true;
            } finally {
                lock.unlock();
            }
        }
    }
}

Synchronized

class FooBar {
    private int n;
    private volatile boolean fooTurn = true;
    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        synchronized (this) {
            for (int i = 0; i < n; i++) {
                while (!fooTurn) {
                    this.wait();
                }
                // printFoo.run() outputs "foo". Do not change or remove this line.
                printFoo.run();
                fooTurn = false;
                this.notify();
            }
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        synchronized (this) {
            for (int i = 0; i < n; i++) {
                while (fooTurn) {
                    this.wait();
                }   
                // printBar.run() outputs "bar". Do not change or remove this line.
                printBar.run();
                fooTurn = true;
                this.notify();
            }
        }
    }
}

Semaphore

class FooBar {
    private int n;
    private Semaphore fooSema = new Semaphore(1);
    private Semaphore barSema = new Semaphore(0);
    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            fooSema.acquire();
        	printFoo.run();
            barSema.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            barSema.acquire();
        	printBar.run();
            fooSema.release();
        }
    }
}

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);
        }
    }
}