2
\$\begingroup\$

I recently faced this following question in a Java coding round, needless to say I did not get a callback. So I want to know where I am going wrong in my solution and also what can be done to improve it.

The Problem statement was as follows:

Create a java program, with two components, a supplier and consumer.

Supplier’s responsibility is to provide ‘random integer values’ in ‘random time intervals’ to consumer.

Consumer is responsible to receive data provided by supplier in the same order and add it to a binary tree. When all the data is passed and processed, consumer should print the data of binary tree in visually tree format.

Supplier’s ‘random time interval’ should be dynamically calculated which can be between 1 and 5 second(s). A total of 10 randomly generated integer elements can be passed on to the consumer.

Maximum number of thread instances which can be initialized in the solution is three.

You can ignore the part about adding it to a binary tree and printing it. I am more interested in the multithreaded implementation of producer/consumer.

The Solution that I submitted was as follows:

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.atomic.AtomicInteger;

public class InternalQueue {
    
    private static final int MAX_QUEUE_SIZE = 10;
    
    private final BlockingQueue<Integer> queue = new ArrayBlockingQueue<>(MAX_QUEUE_SIZE);
    
    private final AtomicInteger itemsProduced = new AtomicInteger(0);
    
    private final AtomicInteger itemsConsumed = new AtomicInteger(0);
        
    public boolean put(int n) {
        if(itemsProduced.incrementAndGet() > MAX_QUEUE_SIZE)
            return false;
        System.out.println(Thread.currentThread().getName() + " trying to put " + n);
        return queue.offer(n);
    }
    
    public Optional<Integer> get() throws InterruptedException {
        if(itemsConsumed.incrementAndGet() > MAX_QUEUE_SIZE)
            return Optional.empty();

        
        Integer n = queue.take();
        System.out.println(Thread.currentThread().getName() + " consumed " + n);
        
        return Optional.of(n);
    }
    
}

I went with a queue data structure where all the elements would be held until a consumer was ready to consume it. (Somewhat how MQ systems operate)

Then the producer and consumers:

import java.util.concurrent.CountDownLatch;
public class Consumer implements Runnable{
    
    private InternalQueue queue;
    
    private BTree bTree;
    
    private CountDownLatch latch;
    
    public Consumer(InternalQueue queue, BTree bTree, CountDownLatch latch) {
        this.queue = queue;
        this.bTree = bTree;
        this.latch = latch;
    }
    
    @Override
    public void run() {
        
        while (true) {
            Optional<Integer> num;
            try {
                num = queue.get();
            } catch (InterruptedException e) {
                e.printStackTrace();
                latch.countDown();
                break;
            }
            if(num.isEmpty()) {
                latch.countDown();
                break;
            }
            
            int n = num.get();
            
            System.out.println(Thread.currentThread().getName() + " pushing to BTREE " + n);
            bTree.insert(n);
        }
    }

} 

public class Producer implements Runnable{

    private InternalQueue queue;
    
    private CountDownLatch latch;
    
    public Producer(InternalQueue queue, CountDownLatch latch) {
        this.queue = queue;
        this.latch = latch;
    }
    
    @Override
    public void run(){
        
        while (true) {
            int num = ThreadLocalRandom.current().nextInt();
            boolean added = queue.put(num);
            if(!added) { 
                latch.countDown();
                break;
            }
            
            int delay = ThreadLocalRandom.current().nextInt(1, 5+1);
            
            try {
                Thread.sleep(delay * 1000L);
            } catch (InterruptedException e) {
                e.printStackTrace();
                latch.countDown();
                break;
            }
        }
    }
}

Please ignore the B-Tree part.

And lastly the void main(String args[]) of the program:

public class Runner {

    private static final int THREAD_POOL_SIZE = 3;
    
    public static void main(String[] args) throws InterruptedException {
        ExecutorService service = Executors.newFixedThreadPool(THREAD_POOL_SIZE);
        
        InternalQueue queue = new InternalQueue();
        
        BTree bTree = new BTree();
        
        int num_threads = 3;
        
        CountDownLatch latch = new CountDownLatch(num_threads);
        
        Producer producer1 = new Producer(queue,latch);
        Producer producer3 = new Producer(queue,latch);
        Consumer consumer1 = new Consumer(queue, bTree,latch);
        Consumer consumer2 = new Consumer(queue, bTree,latch);
        
        service.execute(producer1);
        service.execute(consumer2);
//      service.execute(producer3);
        service.execute(consumer1);
        
        latch.await();
        
        bTree.printTree();
        
        service.shutdown();
        
    }

}

So a couple of questions:

  1. Is this solution thread-safe and correct ? I used AtomicInteger to guard against when the producer has produced over the limit and another AtomicInteger so guard against queue underflow. Is it ok ? Or is there something better or wrong ?
  2. Was it correct to use a CountDownLatch ? Or was it overkill ?
  3. BlockingQueue needed or not ? I used it because I was not sure if any concurrency problems would be there if I hadn't used a thread-safe Collection from the library.

Any feedback or suggestions ?

Thanks.

\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

As you requested I am going to ignore B-Tree and display stuff.

First off after reading problem description it is not obvious for me how exactly should the solution look like:

  • random integer values - does plural form of values suggests that producer should be able to produce more than one value at a time or just that it is able to produce many of them over many iterations?
  • A total of 10 randomly generated integer elements can be passed on to the consumer. - what kind of limit is this, exactly? Is it supposed to be whole problem constraint (like producer should only produce 10 values)? Is it consumer limit (so that consumer rejects more than 10 values)? Is it producer limit (so that producer shouldn't produce more than 10 values? at a time? in the whole program lifecycle?)

Before coding anything I'd start with trying to clarify problem description (who knows may that be part of interview process for that company?).

Correctness in terms of the problem description:

  • Rule stated in the description: Maximum number of thread instances which can be initialized in the solution is three seems to be broken as program will initialize at least (ignoring jvm details) 4 threads during its runtime (1) main thread and (2)(3)(4) thread pool threads. This can be easily fixed as it seems that only one producer and one consumer are needed here (according to the problem description).

  • BlockingQueue - in a version with only one producer and one consumer there is no shared mutable state (only one thing modifies and one reads) so the only aspect that we have to really worry about is read-during-write thread safety (so if collection implementation does not have some possible internal state during the write that would cause reads to fail) and BlockingQueue seems to satisfy this condition (it is thread-safe according to reads) possibly you could also use simple LinkedList with manual synchronization during writes (see e.g. linkLast(E e) implementation - it has mentioned internal state that during write may lead to inconsistent reads).

In terms of the code itself:

  1. Consider writing tests for it - in multi thread cases its always an adventure and would require adjusting the code design to be testable
  2. Currently both producer and consumer can modify the queue - as both have access to method put - if we don't want consumer to produce I'd express this intention in the code design... Consider if the consumer and producer need to know how exactly data is transferred (it kinda depends on a problem description not being clear in this regard, sadly) - possibly all that producer needs is Comsumer<Integer> and all what producer needs is Supplier<Integer> instead of whole queue.
  3. Are you sure you need whole queue? Maybe consumer and producer can communicate using just shared AtomicInteger (possibly via interfaces mentioned in previous point)? (again it heavily depends on the unclear problem description)
  4. Just from reading the code I am not entirely sure what CountDownLatch actually does - it goes to 0 after countDown() in either producer or consumer - so like 1 produce 1 consume and 1 more produce is enough which will cause a tree to be printed and main thread to be shut down, right? Tests would be mighty useful here - I assume this is not intended behavior. If it was intended as a mean of signalling to the main thread that consumer has finished processing all data (and, at the same time, decouple it from expected number of elements? then why passing it to producer?) I would reconsider the approach.

There are also smaller things about the code that could be improved but I think that its design should be reconsidered first.

PS. after reviewing the code for a bit I think that description is not that vague as I initially thought - I think that my initial confusion was caused by my understanding being different than the one represented in the given code. I'd assume that intended understanding was: Producer should produce 10 values, one at a time, in random time periods. After those 10 (all) values were processed data should be visualized in form of B-tree. (which should simplify the solution).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.