Interview Practice Problems for Multithreading

Photo by Nathan Dumlao on Unsplash | I don’t really like to drink coffee. To me, coffee smells better than they actually taste >< They are really bitter and I prefer drinking tea to coffee. However, i thought this photo looked really nice .

wait() and notify() need to be wrapped within a synchronized block.

When you use the synchronized keyword in Java, it provides built-in locking mechanism to ensure that only one thread at a time can execute the synchronized block or method. In such cases, you don't need to explicitly use a separate Lock object.

1242. Web Crawler Multithreaded

Given a URL startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl.

Return all URLs obtained by your web crawler in any order.

Your crawler should:

• Start from the page: startUrl
• Call HtmlParser.getUrls(url) to get all URLs from a webpage of a given URL.
• Do not crawl the same link twice.
• Explore only the links that are under the same hostname as startUrl.

As shown in the example URL above, the hostname is example.org. For simplicity's sake, you may assume all URLs use HTTP protocol without any port specified. For example, the URLs http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while URLs http://example.org/test and http://example.com/abc are not under the same hostname.

The HtmlParser interface is defined as such:

interface HtmlParser {
  // Return a list of all urls from a webpage of given url.
  // This is a blocking call, that means it will do HTTP request and return when this request is finished.
  public List<String> getUrls(String url);
}

Note that getUrls(String url) simulates performing an HTTP request. You can treat it as a blocking function call that waits for an HTTP request to finish. It is guaranteed that getUrls(String url) will return the URLs within 15ms. Single-threaded solutions will exceed the time limit so, can your multi-threaded web crawler do better?

Below are two examples explaining the functionality of the problem. For custom testing purposes, you’ll have three variables urls, edges and startUrl. Notice that you will only have access to startUrl in your code, while urls and edges are not directly accessible to you in code.

Example 1:

Input:
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com",
  "http://news.yahoo.com/us"
]
edges = [[2,0],[2,1],[3,2],[3,1],[0,4]]
startUrl = "http://news.yahoo.com/news/topics/"
Output: [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.yahoo.com/us"
]

Example 2:

Input: 
urls = [
  "http://news.yahoo.com",
  "http://news.yahoo.com/news",
  "http://news.yahoo.com/news/topics/",
  "http://news.google.com"
]
edges = [[0,2],[2,1],[3,2],[3,1],[3,0]]
startUrl = "http://news.google.com"
Output: ["http://news.google.com"]
Explanation: The startUrl links to all other pages that do not share the same hostname.

Constraints:

• 1 <= urls.length <= 1000
• 1 <= urls[i].length <= 300
• startUrl is one of the urls.
• Hostname label must be from 1 to 63 characters long, including the dots, may contain only the ASCII letters from 'a' to 'z', digits from '0' to '9' and the hyphen-minus character ('-').
• The hostname may not start or end with the hyphen-minus character (‘-’).
• See: https://en.wikipedia.org/wiki/Hostname#Restrictions_on_valid_hostnames
• You may assume there’re no duplicates in the URL library.

Follow up:

1. Assume we have 10,000 nodes and 1 billion URLs to crawl. We will deploy the same software onto each node. The software can know about all the nodes. We have to minimize communication between machines and make sure each node does equal amount of work. How would your web crawler design change?
2. What if one node fails or does not work?
3. How do you know when the crawler is done?

/**
 * // This is the HtmlParser's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface HtmlParser {
 *     public List<String> getUrls(String url) {}
 * }
 */
class Solution {
    Set<String> result  = new HashSet<String>();
        
    public List<String> crawl(String startUrl, HtmlParser htmlParser) {            
        crawl(startUrl, htmlParser, startUrl);
        List<String> finalResult = new ArrayList<String>();
        finalResult.addAll(result);
        return finalResult; 
    }
    
    private void crawl(String startUrl, HtmlParser htmlParser, String currentUrl) {
        result.add(currentUrl);
        List<String> childUrls = htmlParser.getUrls(currentUrl);
           
        childUrls.parallelStream().filter( url ->          
              !result.contains(url) && getHostName(url).equals(getHostName(startUrl)) 
            ).forEach(url -> crawl(startUrl, htmlParser, url));
       
    }
    private String getHostName(String url){
        return url.split("http://")[1].split("/")[0];
    }
}

1188. Design Bounded Blocking Queue

Implement a thread-safe bounded blocking queue that has the following methods:

• BoundedBlockingQueue(int capacity) The constructor initializes the queue with a maximum capacity.
• void enqueue(int element) Adds an element to the front of the queue. If the queue is full, the calling thread is blocked until the queue is no longer full.
• int dequeue() Returns the element at the rear of the queue and removes it. If the queue is empty, the calling thread is blocked until the queue is no longer empty.
• int size() Returns the number of elements currently in the queue.

Your implementation will be tested using multiple threads at the same time. Each thread will either be a producer thread that only makes calls to the enqueue method or a consumer thread that only makes calls to the dequeue method. The size method will be called after every test case.

Please do not use built-in implementations of bounded blocking queue as this will not be accepted in an interview.

Example 1:

Input:
1
1
["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"]
[[2],[1],[],[],[0],[2],[3],[4],[]]

Output:
[1,0,2,2]

Explanation:
Number of producer threads = 1
Number of consumer threads = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // initialize the queue with capacity = 2.

queue.enqueue(1);   // The producer thread enqueues 1 to the queue.
queue.dequeue();    // The consumer thread calls dequeue and returns 1 from the queue.
queue.dequeue();    // Since the queue is empty, the consumer thread is blocked.
queue.enqueue(0);   // The producer thread enqueues 0 to the queue. The consumer thread is unblocked and returns 0 from the queue.
queue.enqueue(2);   // The producer thread enqueues 2 to the queue.
queue.enqueue(3);   // The producer thread enqueues 3 to the queue.
queue.enqueue(4);   // The producer thread is blocked because the queue's capacity (2) is reached.
queue.dequeue();    // The consumer thread returns 2 from the queue. The producer thread is unblocked and enqueues 4 to the queue.
queue.size();       // 2 elements remaining in the queue. size() is always called at the end of each test case.

Example 2:

Input:
3
4
["BoundedBlockingQueue","enqueue","enqueue","enqueue","dequeue","dequeue","dequeue","enqueue"]
[[3],[1],[0],[2],[],[],[],[3]]
Output:
[1,0,2,1]

Explanation:
Number of producer threads = 3
Number of consumer threads = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3);   // initialize the queue with capacity = 3.

queue.enqueue(1);   // Producer thread P1 enqueues 1 to the queue.
queue.enqueue(0);   // Producer thread P2 enqueues 0 to the queue.
queue.enqueue(2);   // Producer thread P3 enqueues 2 to the queue.
queue.dequeue();    // Consumer thread C1 calls dequeue.
queue.dequeue();    // Consumer thread C2 calls dequeue.
queue.dequeue();    // Consumer thread C3 calls dequeue.
queue.enqueue(3);   // One of the producer threads enqueues 3 to the queue.
queue.size();       // 1 element remaining in the queue.

Since the number of threads for producer/consumer is greater than 1, we do not know how the threads will be scheduled in the operating system, even though the input seems to imply the ordering. Therefore, any of the output [1,0,2] or [1,2,0] or [0,1,2] or [0,2,1] or [2,0,1] or [2,1,0] will be accepted.

Constraints:

• 1 <= Number of Prdoucers <= 8
• 1 <= Number of Consumers <= 8
• 1 <= size <= 30
• 0 <= element <= 20
• The number of calls to enqueue is greater than or equal to the number of calls to dequeue.
• At most 40 calls will be made to enque, deque, and size.

class BoundedBlockingQueue {
    private Semaphore enq;
    private Semaphore deq;
    // The enq semaphore represents the number of available slots 
    // in the queue, and the deq semaphore represents the number of
    // elements in the queue.
    ConcurrentLinkedDeque<Integer> q;
    public BoundedBlockingQueue(int capacity) {
        q =  new ConcurrentLinkedDeque<>();
        enq = new Semaphore(capacity);
        deq = new Semaphore(0);
    }
    public void enqueue(int element) throws InterruptedException {
        enq.acquire(); // The enqueue method first acquires a permit from the enq semaphore using the acquire method. This blocks if there are no available permits, effectively limiting the number of elements that can be added to the queue to its capacity. O
        q.add(element);
        deq.release(); // permit is released from the deq semaphore using the release method. This indicates that there is one more element in the queue that can be removed.
    }
    public int dequeue() throws InterruptedException {
        deq.acquire(); // This blocks if there are no elements in the queue to be removed, 
        int val = q.poll();
        enq.release(); // This indicates that there is one more available slot in the queue that can be filled.
        return val;
    }
    public int size() {
        return q.size();
    }
}

ConcurrentLinkedDeque is a class in the Java Collections Framework that provides an implementation of a double-ended queue (deque) that can be safely accessed from multiple threads.

A deque is a data structure that allows insertion and removal of elements at both ends, making it useful for implementing a stack, a queue, or a double-ended queue. The ConcurrentLinkedDeque class implements the Deque interface, which provides methods for inserting, removing, and accessing elements in the deque.

The above was taken from someone’s else solution because I really don’t know all these myself in my first attempt.

On another day, I came up with the solution below myself.

class BoundedBlockingQueue {
    Queue<Integer> q;
    int capacity;
    public BoundedBlockingQueue(int capacity) {
        q = new LinkedList<>();
        this.capacity = capacity;
    }
    
    public synchronized void enqueue(int element) throws InterruptedException {
        while(q.size() >= capacity){
            wait();
        }
        this.q.add(element);
        notifyAll();
    }
    
    public synchronized int dequeue() throws InterruptedException {
        while(q.size() == 0){
            wait();
        }
        int res = q.poll();
        notifyAll();
        return res;
    }
    
    public int size() {
        return q.size();
    }
}

Blocking Queue | Bounded Buffer | Consumer Producer (Without using Queue data stucture)

Implement a blocking queue where the queue has a fixed capacity.

A blocking queue is defined as a queue which blocks the caller of the enqueue method if there’s no more capacity to add the new item being enqueued. Similarly, the queue blocks the dequeue caller if there are no items in the queue. Also, the queue notifies a blocked enqueuing thread when space becomes available and a blocked dequeuing thread when an item becomes available in the queue.

Our example below creates two dequeueing threads and one enqueueing thread. The enqueueing thread initially fills up the queue and gets blocked, till the dequeueing threads start off and remove elements from the queue. The output would show enqueuing and dequeuing activity interleaved after the first 5 enqueues.

class Demonstration {
    public static void main( String args[] ) throws Exception{
       final BlockingQueue<Integer> q = new BlockingQueue<Integer>(5); // size 5
       Thread t1 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    for (int i = 0; i < 50; i++) {
                        q.enqueue(new Integer(i));
                        System.out.println("enqueued " + i);
                    }
                } catch (InterruptedException ie) {
                }
            }
        });
        Thread t2 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    for (int i = 0; i < 25; i++) {
                        System.out.println("Thread 2 dequeued: " + q.dequeue());
                    }
                } catch (InterruptedException ie) {
                }
            }
        });
        Thread t3 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    for (int i = 0; i < 25; i++) {
                        System.out.println("Thread 3 dequeued: " + q.dequeue());
                    }
                } catch (InterruptedException ie) {
                }
            }
        });
        t1.start();
        Thread.sleep(4000);
        t2.start();
        t2.join();
        t3.start();
        t1.join();
        t3.join();
    }
}
// The blocking queue class
class BlockingQueue<T> {
    T[] array;
    Object lock = new Object();
    int size = 0;
    int capacity;
    int head = 0;
    int tail = 0;
    @SuppressWarnings("unchecked")
    public BlockingQueue(int capacity) {
        // The casting results in a warning
        array = (T[]) new Object[capacity];
        this.capacity = capacity;
    }
    public void enqueue(T item) throws InterruptedException {
        // synchronized means only 1 thread can invoke the euqueue/dequeue
        // method. Hence, when we test for size variable, no other thread
        // is modifying it
        synchronized (lock) {
            while (size == capacity) {
                lock.wait();
            } // If the current size of the queue == capacity 
              // then we know we'll need to block the caller of the method. 
              // The loop's predicate would become false, as soon as, 
              // another thread performs a dequeue.
            
            // reset tail to the beginning if the tail is already
            // at the end of the backing array
            if (tail == capacity) {
                tail = 0;
            }
            array[tail] = item; // place the item in the array
            size++;
            tail++;
            // don't forget to notify any other threads waiting on
            // a change in value of size. There might be consumers (waiting to dequeue)
            // waiting for the queue to have at least one element..
            // If no thread is waiting, then the signal will simply go 
            // unnoticed and be ignored, which wouldn't affect the correct working of our class. This would be an instance of missed signal that we have talked about earlier.
            lock.notifyAll();
        }
    }
    public T dequeue() throws InterruptedException {
        T item = null;
        synchronized (lock) {
            while (size == 0) { // block if there's nothing to dequeue
                lock.wait();
            }
            if (head == capacity) { // We need to reset head of the queue back to zero in-case it's pointing past the end of the array.
                head = 0;
            }
            
            // store the reference to the object being dequeued
            // and overwrite with null 
            item = array[head];
            array[head] = null;
            head++;
            size--;
            
            // don't forget to call notify, there might be another thread
            // blocked in the enqueue method.
            lock.notifyAll();
        }
        return item;
    }
}

In both the enqueue() and dequeue() methods we use the notifyAll() method instead of the notify() method. The reason behind the choice is very crucial to understand. Consider a situation with two producer threads and one consumer thread all working with a queue of size one. It's possible that when an item is added to the queue by one of the producer threads, the other two threads are blocked waiting on the condition variable. If the producer thread after adding an item invokes notify() it is possible that the other producer thread is chosen by the system to resume execution. The woken-up producer thread would find the queue full and go back to waiting on the condition variable, causing a deadlock. Invoking notifyAll() assures that the consumer thread also gets a chance to wake up and resume execution.

In the above, we solved the consumer producer problem using the synchronized keyword, which is equivalent of a monitor in Java.

1226. The Dining Philosophers

Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers.

Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.

Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.

Design a discipline of behaviour (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.

The philosophers’ ids are numbered from 0 to 4 in a clockwise order. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:

• philosopher is the id of the philosopher who wants to eat.
• pickLeftFork and pickRightFork are functions you can call to pick the corresponding forks of that philosopher.
• eat is a function you can call to let the philosopher eat once he has picked both forks.
• putLeftFork and putRightFork are functions you can call to put down the corresponding forks of that philosopher.
• The philosophers are assumed to be thinking as long as they are not asking to eat (the function is not being called with their number).

Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. The function may be called for the same philosopher more than once, even before the last call ends.

Example 1:

Input: n = 1
Output: [[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
Explanation:
n is the number of times each philosopher will call the function.
The output array describes the calls you made to the functions controlling the forks and the eat function, its format is:
output[i] = [a, b, c] (three integers)
- a is the id of a philosopher.
- b specifies the fork: {1 : left, 2 : right}.
- c specifies the operation: {1 : pick, 2 : put, 3 : eat}.

Constraints:

• 1 <= n <= 60

class DiningPhilosophers {
    private Semaphore[] forks = new Semaphore[5];
    private Lock maxDiners;
    public DiningPhilosophers() {
        for(int i=0; i<5; i++) {
         forks[i] = new Semaphore(1);
        }
        maxDiners = new ReentrantLock(); // must be reentrant 
    }
    // call the run() method of any runnable to execute its code
    public void wantsToEat(int id,
                           Runnable pickLeftFork,
                           Runnable pickRightFork,
                           Runnable eat,
                           Runnable putLeftFork,
                           Runnable putRightFork) throws InterruptedException {
        maxDiners.lock();
        int leftFork = id;
        int rightFork = (id + 1) % 5;
       
        forks[leftFork].acquire();
        forks[rightFork].acquire();

        pickLeftFork.run();
        pickRightFork.run();
        eat.run();
        putLeftFork.run();
        putRightFork.run();

        forks[leftFork].release();
        forks[rightFork].release();
        maxDiners.unlock();
        
    }
}

Support reentrant behavior when the same thread attempts to acquire the lock multiple times consecutively.

In the Dining Philosophers problem, the wantsToEat method is executed by each philosopher independently. If the lock used for synchronization is not reentrant and a philosopher attempts to acquire the lock multiple times consecutively (for example, if a philosopher calls wantsToEat recursively), a non-reentrant lock would result in a deadlock. This is because a non-reentrant lock would consider the lock already held by the same thread as a conflicting acquisition, causing the thread to block indefinitely.

1279. Traffic Light Controlled Intersection

There is an intersection of two roads. First road is road A where cars travel from North to South in direction 1 and from South to North in direction 2. Second road is road B where cars travel from West to East in direction 3 and from East to West in direction 4.

There is a traffic light located on each road before the intersection. A traffic light can either be green or red.

1. Green means cars can cross the intersection in both directions of the road.
2. Red means cars in both directions cannot cross the intersection and must wait until the light turns green.

The traffic lights cannot be green on both roads at the same time. That means when the light is green on road A, it is red on road B and when the light is green on road B, it is red on road A.

Initially, the traffic light is green on road A and red on road B. When the light is green on one road, all cars can cross the intersection in both directions until the light becomes green on the other road. No two cars traveling on different roads should cross at the same time.

Design a deadlock-free traffic light controlled system at this intersection.

Implement the function void carArrived(carId, roadId, direction, turnGreen, crossCar) where:

• carId is the id of the car that arrived.
• roadId is the id of the road that the car travels on.
• direction is the direction of the car.
• turnGreen is a function you can call to turn the traffic light to green on the current road.
• crossCar is a function you can call to let the current car cross the intersection.

Your answer is considered correct if it avoids cars deadlock in the intersection. Turning the light green on a road when it was already green is considered a wrong answer.

Example 1:

Input: cars = [1,3,5,2,4], directions = [2,1,2,4,3], arrivalTimes = [10,20,30,40,50]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Car 3 Has Passed Road A In Direction 1",    // Car 3 crosses the intersection as the light is still green.
"Car 5 Has Passed Road A In Direction 2",    // Car 5 crosses the intersection as the light is still green.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses the intersection as the light is still green.
]

Example 2:

Input: cars = [1,2,3,4,5], directions = [2,4,3,3,1], arrivalTimes = [10,20,30,40,40]
Output: [
"Car 1 Has Passed Road A In Direction 2",    // Traffic light on road A is green, car 1 can cross the intersection.
"Traffic Light On Road B Is Green",          // Car 2 requests green light for road B.
"Car 2 Has Passed Road B In Direction 4",    // Car 2 crosses as the light is green on road B now.
"Car 3 Has Passed Road B In Direction 3",    // Car 3 crosses as the light is green on road B now.
"Traffic Light On Road A Is Green",          // Car 5 requests green light for road A.
"Car 5 Has Passed Road A In Direction 1",    // Car 5 crosses as the light is green on road A now.
"Traffic Light On Road B Is Green",          // Car 4 requests green light for road B. Car 4 blocked until car 5 crosses and then traffic light is green on road B.
"Car 4 Has Passed Road B In Direction 3"     // Car 4 crosses as the light is green on road B now.
]
Explanation: This is a dead-lock free scenario. Note that the scenario when car 4 crosses before turning light into green on road A and allowing car 5 to pass is also correct and Accepted scenario.

class TrafficLight {
    private boolean isLightAGreen;
    public TrafficLight() {
        isLightAGreen = true;
    }
    
    public synchronized void carArrived(
        int carId,           // ID of the car
        int roadId,          // ID of the road the car travels on. Can be 1 (road A) or 2 (road B)
        int direction,       // Direction of the car
        Runnable turnGreen,  // Use turnGreen.run() to turn light to green on current road
        Runnable crossCar    // Use crossCar.run() to make car cross the intersection 
    ) {
        if (!isLightAGreen && roadId == 1 || isLightAGreen && roadId == 2) {
                isLightAGreen = !isLightAGreen; // Toggle boolean variable
                turnGreen.run();
        }
        crossCar.run(); // If light is already green, just let car pass
    }
}

1115. Print FooBar Alternately

Suppose you are given the following code:

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }
public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

The same instance of FooBar will be passed to two different threads:

• thread A will call foo(), while
• thread B will call bar().

Modify the given program to output "foobar" n times.

Example 1:

Input: n = 1
Output: "foobar"
Explanation: There are two threads being fired asynchronously. One of them calls foo(), while the other calls bar().
"foobar" is being output 1 time.

Example 2:

Input: n = 2
Output: "foobarfoobar"
Explanation: "foobar" is being output 2 times.

class FooBar {
    private int n;
    Semaphore sFoo = new Semaphore(1);
    Semaphore sBr = new Semaphore(0);

    public FooBar(int n) {
        this.n = n;
    }

    public void foo(Runnable printFoo) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            sFoo.acquire();
            // printFoo.run() outputs "foo". Do not change or remove this line.
            printFoo.run();
            sBr.release();
        }
    }

    public void bar(Runnable printBar) throws InterruptedException {
        
        for (int i = 0; i < n; i++) {
            sBr.acquire();
            // printBar.run() outputs "bar". Do not change or remove this line.
            printBar.run();
            sFoo.release();
        }
    }
}

1117. Building H2O

There are two kinds of threads: oxygen and hydrogen. Your goal is to group these threads to form water molecules.

There is a barrier where each thread has to wait until a complete molecule can be formed. Hydrogen and oxygen threads will be given releaseHydrogen and releaseOxygen methods respectively, which will allow them to pass the barrier. These threads should pass the barrier in groups of three, and they must immediately bond with each other to form a water molecule. You must guarantee that all the threads from one molecule bond before any other threads from the next molecule do.

In other words:

• If an oxygen thread arrives at the barrier when no hydrogen threads are present, it must wait for two hydrogen threads.
• If a hydrogen thread arrives at the barrier when no other threads are present, it must wait for an oxygen thread and another hydrogen thread.

We do not have to worry about matching the threads up explicitly; the threads do not necessarily know which other threads they are paired up with. The key is that threads pass the barriers in complete sets; thus, if we examine the sequence of threads that bind and divide them into groups of three, each group should contain one oxygen and two hydrogen threads.

Write synchronization code for oxygen and hydrogen molecules that enforces these constraints.

Example 1:

Input: water = "HOH"
Output: "HHO"
Explanation: "HOH" and "OHH" are also valid answers.

Example 2:

Input: water = "OOHHHH"
Output: "HHOHHO"
Explanation: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" and "OHHOHH" are also valid answers.

Constraints:

• 3 * n == water.length
• 1 <= n <= 20
• water[i] is either 'H' or 'O'.
• There will be exactly 2 * n 'H' in water.
• There will be exactly n 'O' in water.

import java.util.concurrent.*;

class H2O {
    
    private final CyclicBarrier barrier = new CyclicBarrier(3);
    private final Semaphore hSem = new Semaphore(2);
    private final Semaphore oSem = new Semaphore(1);

    public H2O() {
        
    }

    public void hydrogen(Runnable releaseHydrogen) throws InterruptedException {
       try {
            hSem.acquire();
            barrier.await(); // if the thread reaches here, it means there are 2 h
             // releaseHydrogen.run() outputs "H". Do not change or remove this line.
            releaseHydrogen.run();
        } catch(Exception ignore) {
            
        } finally {
            hSem.release();
        }

    }

    public void oxygen(Runnable releaseOxygen) throws InterruptedException {
        try {
            oSem.acquire();
            barrier.await();
            // releaseOxygen.run() outputs "O". Do not change or remove this line.
            releaseOxygen.run();
        } catch(Exception ignore) {
            
        } finally {
            oSem.release();
        }
    }
}

When we use synchronized keyword, we usually don’t need to use lock. Vice versa applies.

1116. Print Zero Even Odd

You have a function printNumber that can be called with an integer parameter and prints it to the console.

• For example, calling printNumber(7) prints 7 to the console.

You are given an instance of the class ZeroEvenOdd that has three functions: zero, even, and odd. The same instance of ZeroEvenOdd will be passed to three different threads:

• Thread A: calls zero() that should only output 0's.
• Thread B: calls even() that should only output even numbers.
• Thread C: calls odd() that should only output odd numbers.

Modify the given class to output the series "010203040506..." where the length of the series must be 2n.

Implement the ZeroEvenOdd class:

• ZeroEvenOdd(int n) Initializes the object with the number n that represents the numbers that should be printed.
• void zero(printNumber) Calls printNumber to output one zero.
• void even(printNumber) Calls printNumber to output one even number.
• void odd(printNumber) Calls printNumber to output one odd number.

Example 1:

Input: n = 2
Output: "0102"
Explanation: There are three threads being fired asynchronously.
One of them calls zero(), the other calls even(), and the last one calls odd().
"0102" is the correct output.

Example 2:

Input: n = 5
Output: "0102030405"

My original code that has the error “You passed invalid value. Exiting.”. I don’t fully understand why but i think it’s relating to num?

class ZeroEvenOdd {
    private int n;
    Semaphore oddS = new Semaphore(0);
    Semaphore evenS = new Semaphore(0);
    Semaphore zeroS = new Semaphore(1);
    volatile int num = 1;
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        for(int i=0; i<n; i++){
            zeroS.acquire();
            printNumber.accept(0);
            if(num%2 == 1){
                oddS.release();
            } else {
                evenS.release();
            }
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i=1; i<n; i+=2){
            evenS.acquire();
            printNumber.accept(num);
            zeroS.release();
            num++;
        }
       
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i=0; i<n; i+=2){
            oddS.acquire();
            printNumber.accept(num);
            zeroS.release();
            num++;
        }
    }
}

The code below works. I think the main idea is to minimise the number of shared variables between threads.

class ZeroEvenOdd {
    private int n;
    Semaphore oddS = new Semaphore(0);
    Semaphore evenS = new Semaphore(0);
    Semaphore zeroS = new Semaphore(1);
    
    public ZeroEvenOdd(int n) {
        this.n = n;
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void zero(IntConsumer printNumber) throws InterruptedException {
        boolean isOdd = true;
        for(int i=0; i<n; i++){
            zeroS.acquire();
            printNumber.accept(0);
            if(isOdd){
                oddS.release();
            } else {
                evenS.release();
            }
            isOdd = !isOdd;
        }
    }

    public void even(IntConsumer printNumber) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%2==0){
                evenS.acquire();
                printNumber.accept(i);
                zeroS.release();
            }
        }
       
    }

    public void odd(IntConsumer printNumber) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%2==1){
                oddS.acquire();
                printNumber.accept(i);
                zeroS.release();
            }
        }
    }
}

Sharing an Interview question I got when interviewing with a company

// Given:

public interface <K, V> Cache<K, V> {
   
   V get(K key);
   
}

/**
 * Loads values of type V for keys of type K from an external location. 
 * Actual implementation is unknown. 
 * All we know is that it may be slow.
 */
public interface <K, V> DataSource<K, V> {
   V fetch(K key);
}

/*
Implement interface Cache so that it:
  a) maintains internal cache of values of type V for keys of type K
  b) uses provided DataSource to fetch data from an external data source
  c) when get(K key) is called, it first checks if we already have a cached value and returns it if we have. 
     Otherwise obtain a value by calling DataSource::fetch, place it in the cache and return.
  d) Multithreading
    1) solution should be thread-safe
    2) when two threads are calling get() with the same argument at the same time and value is not available in the cache -- 
       only one thread should invoke DataSource::fetch, the other should wait until the value is available in the cache.
    3) when two threads invoke get() with different arguments at the same time -- both should be allowed to execute 
       DataSource::fetch concurrently
*/

public class CacheImpl implements Cache<K, V> {
      DataSource<K, V> dataSource;
      HashMap<K, V> map = new HashMap<>();
      HashMap<K, Lock> lockMap = new HashMap<>();

      public CacheImpl(DataSource userDataSource){
        this.dataSource = userDataSource;
      }
      
      @Override
      public V get(K key){
        if(map.containsKey(key)){
          return map.get(key);
        }
        V data = fetchData(key);
        map.put(key, data);
        return data;
      } 

      private Lock getOrCreateLock(K key){
          lockMap.putIfAbsent(key, new Semaphore(1));
          return lockMap.get(key);
      }
      
      private V fetchData(K key){ 
        Lock lock = getOrCreateLock(key);
        lock.acquire();
        try{
            if(map.containsKey(key)){
                return map.get(key);
            }
            V data = dataSource.fetch(key);  
            return data;
        } finally {
            lock.release();
        }
      }
}

1195. Fizz Buzz Multithreaded

You have the four functions:

• printFizz that prints the word "fizz" to the console,
• printBuzz that prints the word "buzz" to the console,
• printFizzBuzz that prints the word "fizzbuzz" to the console, and
• printNumber that prints a given integer to the console.

You are given an instance of the class FizzBuzz that has four functions: fizz, buzz, fizzbuzz and number. The same instance of FizzBuzz will be passed to four different threads:

• Thread A: calls fizz() that should output the word "fizz".
• Thread B: calls buzz() that should output the word "buzz".
• Thread C: calls fizzbuzz() that should output the word "fizzbuzz".
• Thread D: calls number() that should only output the integers.

Modify the given class to output the series [1, 2, "fizz", 4, "buzz", ...] where the ith token (1-indexed) of the series is:

• "fizzbuzz" if i is divisible by 3 and 5,
• "fizz" if i is divisible by 3 and not 5,
• "buzz" if i is divisible by 5 and not 3, or
• i if i is not divisible by 3 or 5.

Implement the FizzBuzz class:

• FizzBuzz(int n) Initializes the object with the number n that represents the length of the sequence that should be printed.
• void fizz(printFizz) Calls printFizz to output "fizz".
• void buzz(printBuzz) Calls printBuzz to output "buzz".
• void fizzbuzz(printFizzBuzz) Calls printFizzBuzz to output "fizzbuzz".
• void number(printNumber) Calls printnumber to output the numbers.

Example 1:

Input: n = 15
Output: [1,2,"fizz",4,"buzz","fizz",7,8,"fizz","buzz",11,"fizz",13,14,"fizzbuzz"]

Example 2:

Input: n = 5
Output: [1,2,"fizz",4,"buzz"]

class FizzBuzz {
    private int n;
    Semaphore fizzS = new Semaphore(0);
    Semaphore buzzS = new Semaphore(0);
    Semaphore fizzBuzzS = new Semaphore(0);
    Semaphore numberS = new Semaphore(1);

    public FizzBuzz(int n) {
        this.n = n;
    }

    // printFizz.run() outputs "fizz".
    public void fizz(Runnable printFizz) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%3 == 0 && i%5 != 0){
                fizzS.acquire();
                printFizz.run();
                unlock(i+1);
            }
        }
    }

    // printBuzz.run() outputs "buzz".
    public void buzz(Runnable printBuzz) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%5 == 0 && i%3 != 0){
                buzzS.acquire();
                printBuzz.run();
                unlock(i+1);
            }
        }
    }

    // printFizzBuzz.run() outputs "fizzbuzz".
    public void fizzbuzz(Runnable printFizzBuzz) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%3 == 0 && i%5 == 0){
                fizzBuzzS.acquire();
                printFizzBuzz.run();
                unlock(i+1);
            }
        }
    }

    // printNumber.accept(x) outputs "x", where x is an integer.
    public void number(IntConsumer printNumber) throws InterruptedException {
        for(int i=1; i<=n; i++){
            if(i%3 != 0 && i%5 != 0){
                numberS.acquire();
                printNumber.accept(i);
                unlock(i+1);
            }
        }
    }

    public void unlock(int n){
        if(n%3 == 0 && n%5 != 0){
            fizzS.release();
        } else if (n%5 == 0 && n%3 != 0){
            buzzS.release();
        } else if (n%15 == 0){
            fizzBuzzS.release();
        } else {
            numberS.release();
        }
    }
}

1114. Print in Order

Suppose we have a class:

public class Foo {
  public void first() { print("first"); }
  public void second() { print("second"); }
  public void third() { print("third"); }
}

The same instance of Foo will be passed to three different threads. Thread A will call first(), thread B will call second(), and thread C will call third(). Design a mechanism and modify the program to ensure that second() is executed after first(), and third() is executed after second().

Note:

We do not know how the threads will be scheduled in the operating system, even though the numbers in the input seem to imply the ordering. The input format you see is mainly to ensure our tests’ comprehensiveness.

Example 1:

Input: nums = [1,2,3]
Output: "firstsecondthird"
Explanation: There are three threads being fired asynchronously. The input [1,2,3] means thread A calls first(), thread B calls second(), and thread C calls third(). "firstsecondthird" is the correct output.

Example 2:

Input: nums = [1,3,2]
Output: "firstsecondthird"
Explanation: The input [1,3,2] means thread A calls first(), thread B calls third(), and thread C calls second(). "firstsecondthird" is the correct output.

Constraints:

• nums is a permutation of [1, 2, 3].

class Foo {
    Semaphore firstS = new Semaphore(1);
    Semaphore secondS = new Semaphore(0);
    Semaphore thirdS = new Semaphore(0);
    public Foo() {
        
    }

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

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

    public void third(Runnable printThird) throws InterruptedException {
        thirdS.acquire();
        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

The End :)

I am really practising and trying my best.