# Concurrency

#### [1114. Print in Order](https://leetcode.com/problems/print-in-order/)

{% tabs %}
{% tab title="Synchronized" %}

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

{% endtab %}

{% tab title="ReentrantLock" %}

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

{% endtab %}

{% tab title="Semaphore" %}

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

{% endtab %}

{% tab title="CompletableFuture" %}

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

{% endtab %}
{% endtabs %}

#### [1188. Design Bounded Blocking Queue](https://leetcode.com/problems/design-bounded-blocking-queue/)

```java
    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](https://leetcode.com/problems/print-foobar-alternately/)

{% tabs %}
{% tab title="ReentrantLock" %}

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

{% endtab %}

{% tab title="Synchronized" %}

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

{% endtab %}

{% tab title="Semaphore" %}

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

{% endtab %}
{% endtabs %}

**Web Crawler with future**

{% tabs %}
{% tab title="First Tab" %}

```java
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;
    }
}

```

{% endtab %}

{% tab title="Second Tab" %}

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

```

{% endtab %}
{% endtabs %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://howardyangemail.gitbook.io/decode-leetcode/design/concurrency.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.