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

Semaphore

CompletableFuture

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

Semaphore

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