Design threadsafe program to keep counts of word

Design threadsafe program to keep counts of word
https://github.com/mission-peace/interview/blob/master/src/com/interview/multithreaded/CountingWord.java
 * Keep a concurrent map. Key to this map should be word while value should be AtomicLong to update it
 * in threadsafe way
public class CountingWord {

    private ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<>();
 
    public void addWord(String word){
        AtomicLong l = map.get(word);
        if(l == null){
            l = new AtomicLong(1);
            l = map.putIfAbsent(word, l);
            if(l != null){
                l.incrementAndGet();
            }
        }else{
            l.incrementAndGet();
        }
    }
   
    public long getCount(String word){
        AtomicLong l = map.get(word);
        if(l != null){
            return l.longValue();
        }
        return 0;
    }
   
    public static void main(String args[]) throws InterruptedException{
        ExecutorService executor1 = Executors.newFixedThreadPool(20);
        ExecutorService executor2 = Executors.newFixedThreadPool(20);
        ExecutorService executor3 = Executors.newFixedThreadPool(20);
   
        int total = 100000;
        CountDownLatch countDownLatch = new CountDownLatch(3*total);
        CountingWord cw = new CountingWord();
        for(int i= 0; i < total; i++){
            executor1.execute(() -> cw.addWord("word1"));
            countDownLatch.countDown();
        }
        for(int i= 0; i < total; i++){
            executor2.execute(() -> cw.addWord("word2"));
            countDownLatch.countDown();
        }
        for(int i= 0; i < total; i++){
            executor3.execute(() -> cw.addWord("word3"));
            countDownLatch.countDown();
        }
       
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            throw e;
        }
        executor1.shutdownNow();
        executor2.shutdownNow();
        executor3.shutdownNow();
       
        long count1 = cw.getCount("word1");
        long count2 = cw.getCount("word2");
        long count3 = cw.getCount("word3");
        assert count1 == total;
        assert count2 == total;
        assert count3 == total;
       
    }

Design threadsafe program to keep min and max

Design threadsafe program to keep min and max
https://github.com/mission-peace/interview/blob/master/src/com/interview/multithreaded/MinMaxKeeper.java
 * @author tusroy
 *
 * Write a program which keeps min and max value in threadsafe way
 * Support 2 apis
 * void updateMaxMin(int val)
 * int getMin()
 * int getMax()
 *
 * Solution
 * Use compareAndSet method of AtomicInteger to update min and max
 *
 * @ThreadSafe
 */
public class MinMaxKeeper {

    private AtomicInteger min = new AtomicInteger(Integer.MAX_VALUE);
    private AtomicInteger max = new AtomicInteger(Integer.MIN_VALUE);
   
    /**
     * Threadsafe way of updating min and max
     * @param value
     */
    public void updateMinMax(int value){
        //update min
        while(true){
            //if value is greater than whatever is in min just break right away
            int minVal = min.get();
            if(value >= minVal){
                break;
            }
            //try to update value only if minVal is in min
            boolean isSetSuccesful = min.compareAndSet(minVal, value);
            //if set was successful break from while loop else keep looping
            if(isSetSuccesful){
                break;
            }
        }
       
        //update max
        while(true){
            int maxVal = max.get();
            if(value <= maxVal){
                break;
            }
            boolean isSetSuccesful = max.compareAndSet(maxVal, value);
            if(isSetSuccesful){
                break;
            }
        }
    }
   
    public int getMin(){
        return min.get();
    }
   
    public int getMax(){
        return max.get();
    }
   
    public static void main(String args[]) throws InterruptedException{
        ExecutorService executors = Executors.newFixedThreadPool(100);
        MinMaxKeeper mmKeeper = new MinMaxKeeper();
       
        for(int i=0 ; i < 100000; i++){
            GenerateRand rand = new GenerateRand(mmKeeper, i);
            executors.execute(rand);
        }
       
        executors.shutdown();
        executors.awaitTermination(10, TimeUnit.SECONDS);
       
        assert mmKeeper.getMin() == -1;
        assert mmKeeper.getMax() == 1000001;
    }

    static class GenerateRand implements Runnable{
        int index = 0;
        MinMaxKeeper mmKeeper;
        public GenerateRand(MinMaxKeeper mmKeeper, int index) {
            this.index = index;
            this.mmKeeper = mmKeeper;
        }
        @Override
        public void run() {
            int rand = ThreadLocalRandom.current().nextInt(1000000);
            if(index == 999){
                rand = -1;
            }
            if(index == 1001){
                rand = 1000001;
            }
            mmKeeper.updateMinMax(rand);
        }
       
    }
}

Data Structures and Algorithm: Distributed doubly linked list sum

Data Structures and Algorithm: Distributed doubly linked list sum

You are given a doubly linked list whose nodes are distributed. Every node has next, previous pointers and a method send(integer). A node can talk to its next and previous nodes only. Different instances of same  threads are running in them. How would you implement the run method of the thread class so that each node prints the sum of complete linked list.

We will accumulate the number from right to left and then propagate the sum from left to right.

1. Every node except the right most node will wait for a first send call. Right node will send its value immediately to its left node.
2. After receiving the number from right side each node will add it with its own value and send it to its left.
3. The left most node, after receiving the send call, add its own number and send the complete sum to its right node.
4. All nodes will wait for a second send call.
5. After receiving the second send call each node will print the sum.
6. After printing each node will propagate the sum to its right node.

The threads will start running as soon as the nodes are created. But the doubly linked list may not be completely formed by then. So we will use a shared flag which will signal all the threads to start working.

public class DistributedDoublyLinkedListSum
{
 public static volatile boolean startFlag = false;

 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  a.next = b;
  b.next = c;
  c.next = d;
  d.next = e;
  e.prev = d;
  d.prev = c;
  c.prev = b;
  b.prev = a;
  startFlag = true;
 }

 private static class Node
 {
  Node next;
  Node prev;
  int value;
  Integer data;

  public Node(int value)
  {
   this.value = value;
   new Thread(new NodeRunner(this, value)).start();
  }

  public synchronized void send(int data)
  {
   this.data = data;
  }

 }

 private static class NodeRunner implements Runnable
 {
  Node node;
  int id;

  public NodeRunner(Node node, int id)
  {
   this.node = node;
   this.id = id;
  }

  @Override
  public void run()
  {
   while (!startFlag)
   {
   }
   if (node.next == null)
   {
    node.prev.send(node.value);
   } else
   {
    while (node.data == null)
    {
     try
     {
      Thread.sleep(10);
     } catch (InterruptedException e)
     {
     }
    }
    int sum = node.data + node.value;
    if (node.prev != null)
    {
     node.data = null;
     node.prev.send(sum);
    }
   }
   while (node.data == null)
   {
    try
    {
     Thread.sleep(10);
    } catch (InterruptedException e)
    {
    }
   }
   System.out.println("id:" + id + " sum:" + node.data);
   if (node.next != null)
   {
    node.next.send(node.data);
   }

  }
 }
}

Read full article from Data Structures and Algorithm: Distributed doubly linked list sum

Data Structures and Algorithm: Distributed binary tree sum

Data Structures and Algorithm: Distributed binary tree sum

You are given a binary tree where each node has an integer value, a left, right and parent pointer. Every node is an independent distributed system where a thread is running in each node. You can talk to other node only by one method called "send(node, data)". And a node can call "send" only to its children or parent. How will you design the system so that all the nodes know the total sum of values of all the nodes in the binary tree and report them asynchronously. 

The basic technique that we will follow to get the total sum is as follows.
1. Every node will wait for its children to report the sum of nodes of the tree rooted at the child node.
2. The node will add the sum of its left and right children and add its own value and send it to its parent.
3. Then wait for its parent to report back the total sum of the tree.
The root node will be the first to know the complete sum. Then it propagates it back to its children which in turn will propagate down to its children till every node is aware of the total sum.

To implement this, we keep on adding the values coming via the send method and increment a counter to record how many times the send has been called. When the send has been called equal to the number of children, it means all children has reported their sums. So a node will send the sum after adding its own value to its parent (So leaf nodes will immediately send its own value to its parents). Then resets the sum. Then it keeps on waiting for another send call from its parent. When the send method is called again, the sum will be equal to the total sum of the tree. Then it propagates the same value by calling its children and print the value to console. We need to start the process after our tree building is completed. So we maintained a global static flag which signals all threads to start their operations.

public class DistributedSystemSum
{
 public static volatile boolean startFlag = false;

 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  Node f = new Node(6);
  Node g = new Node(7);
  Node h = new Node(8);
  a.left = b;
  b.parent = a;
  a.right = c;
  c.parent = a;
  b.left = d;
  d.parent = b;
  c.left = e;
  e.parent = c;
  c.right = f;
  f.parent = c;
  f.left = g;
  g.parent = f;
  f.right = h;
  h.parent = f;
  startFlag = true;
 }

 private static class Node
 {
  Node parent;
  Node left;
  Node right;
  int value;
  int sum = 0;
  int receiveCount = 0;

  public Node(int value)
  {
   this.value = value;
   NodeRunner nodeRunner = new NodeRunner(this, value);
   new Thread(nodeRunner).start();
  }

  public synchronized void send(Integer data)
  {
   sum += data;
   receiveCount++;
  }

  public synchronized int getReceivedCount()
  {
   return receiveCount;
  }
 }

 private static class NodeRunner implements Runnable
 {
  Node node;
  int id;

  NodeRunner(Node node, int id)
  {
   this.node = node;
   this.id = id;
  }

  @Override
  public void run()
  {
   while (!DistributedSystemSum.startFlag)
   {
   }
   int childCount = 0;
   if (node.left != null)
    childCount++;
   if (node.right != null)
    childCount++;
   while (node.getReceivedCount() != childCount)
   {
   }
   int sum = node.sum + node.value;
   node.sum = 0;
   if (node.parent != null)
   {
    node.parent.send(sum);
    while (node.getReceivedCount() != childCount + 1)
    {
    }
   } else
   {
    node.sum = sum;
   }
   if (node.left != null)
    node.left.send(node.sum);
   if (node.right != null)
    node.right.send(node.sum);
   System.out.println("Thread id=" + id + " sum=" + node.sum);

  }

 }
}

Read full article from Data Structures and Algorithm: Distributed binary tree sum

Data Structures and Algorithm: Distributed Circular linked list sum

Data Structures and Algorithm: Distributed Circular linked list sum

You are given a circular linked list whose nodes are distributed. Every node has next pointer and a method send(integer). A node can talk to its next node only. Different instances of same  threads are running in the nodes. How would you implement the run method of the thread class so that each node prints the sum of complete linked list.

We will accumulate the number along the next pointer circularly and then propagate it in the same direction in second iteration.

The trick of this problem is that in a circular linked list every node is equal and there is no starting and ending node. For this, we have taken a flag object, Every thread will try to acquire its lock, and whoever wins in this race will become a decisive node and it changes the value of the flag so that no other thread can become decisive. So there will be only one node randomly chosen in the linked list which will start the operation. It will send its value to the next node. All other nodes will wait for its first send call. After that it adds its own value and send it to the next node. In this way the decisive node will be the first to know the complete sum. It will then send it to the next node. So again every node will wait for second send call. Then it will print the total sum and propagate it to its next node and exits.

public class DistributedCircularListSum
{
 public static volatile boolean startFlag = false;
 private static Boolean flag = false;

 public static void main(String[] args)
 {
  Node a = new Node(1);
  Node b = new Node(2);
  Node c = new Node(3);
  Node d = new Node(4);
  Node e = new Node(5);
  a.next = b;
  b.next = c;
  c.next = d;
  d.next = e;
  e.next = a;
  startFlag = true;
 }

 private static class Node
 {
  Node next;
  int value;
  Integer data;

  public Node(int value)
  {
   this.value = value;
   new Thread(new NodeRunner(this, value)).start();
  }

  public synchronized void send(int data)
  {
   this.data = data;
  }

 }

 private static class NodeRunner implements Runnable
 {
  Node node;
  int id;

  public NodeRunner(Node node, int id)
  {
   this.node = node;
   this.id = id;
  }

  @Override
  public void run()
  {
   while (!startFlag)
   {
   }

   boolean isFirst = false;
   synchronized (flag)
   {
    if (flag == false)
    {
     flag = true;
     isFirst = true;
    }
   }
   if (isFirst)
    node.next.send(node.value);
   else
   {
    while (node.data == null)
    {
     try
     {
      Thread.sleep(10);
     } catch (InterruptedException e)
     {

     }
    }
    int sum = node.value + node.data;
    node.data = null;
    node.next.send(sum);
   }
   while (node.data == null)
   {
    try
    {
     Thread.sleep(10);
    } catch (InterruptedException e)
    {

    }
   }
   System.out.println("id:" + id + "sum:" + node.data);
   node.next.send(node.data);
  }
 }
}

Read full article from Data Structures and Algorithm: Distributed Circular linked list sum