Monday, October 17, 2016

Multi-Thread Practices



* Develop a software to count number of events in last 5 mins. You have to support two apis
* 1) addEvent() -> It means increment event by 1
* 2) getTotalEvents() -> Return total number of events in last 5 mins
*
* Program should support millions of events every minute and should also provide multi-threading support
*
* This class might not have 100% accuracy as far as events in last 5 mins are concerned.
* Since we are using circular queue last second information may not be very accurate.

public class RealTimeCounter {

    private final static int GRANULARITY = 300;
    private AtomicLongArray counter = new AtomicLongArray(GRANULARITY);
    private volatile int pos = 0;
 
    private RealTimeCounter(){
        PositionUpdater positionUpdater = new PositionUpdater(this);
        positionUpdater.start();
    }
 
    private static volatile RealTimeCounter INSTANCE;
 
    public static RealTimeCounter getInstance(){
        if(INSTANCE == null){
            synchronized (RealTimeCounter.class) {
                if(INSTANCE == null){
                    INSTANCE = new RealTimeCounter();
                }
            }
        }
        return INSTANCE;
    }
 
    public long getTotalEvents(){
        int total = 0;
        for(int i=0; i < GRANULARITY; i++){
            total += counter.get(i);
        }
        return total;
    }
 
    public void addEvent(){
        counter.getAndIncrement(pos);
    }
 
    void incrementPosition(){
        //first reset the value to 0 at next counter location.
        counter.set((pos + 1)%GRANULARITY, 0);
        pos = (pos + 1)%GRANULARITY;
    }
 
    public static void main(String args[]){
        ExecutorService executor = Executors.newFixedThreadPool(10);
        RealTimeCounter realTimeCounter = new RealTimeCounter();
        final Random random = new Random();
        final int TOTAL_EVENTS = 10000;
        CountDownLatch countDownLatch = new CountDownLatch(TOTAL_EVENTS);
        for(int i=0; i < TOTAL_EVENTS; i++){
            executor.execute(() -> {
                realTimeCounter.addEvent();
                try {
                    Thread.sleep(random.nextInt(10));
                } catch (Exception e) {
                    e.printStackTrace();
                }
                countDownLatch.countDown();
            }
            );
        }
        try{
            countDownLatch.await();
        }catch(Exception e){
         
        }
        System.out.println(realTimeCounter.getTotalEvents());
        executor.shutdownNow();
    }
}

class PositionUpdater extends TimerTask{
    private final RealTimeCounter realTimeCounter;
    private final Timer timer = new Timer(true);
    private static final int DELAY = 1000;
    PositionUpdater(RealTimeCounter realTimeCounter) {
        this.realTimeCounter = realTimeCounter;
    }
 
    public void start(){
        timer.schedule(this, DELAY);
    }
    @Override
    public void run() {
        realTimeCounter.incrementPosition();
    }
}

https://github.com/mission-peace/interview/blob/master/src/com/interview/multithreaded/PrintInSequence.java
* A class that has 5 threads - two to increment the myVar variable, two to decrement the myVar variable and one to print the value of myVar.
* Implement increment(), decrement() and printVar() methods such that the following series is printed:
* 0 1 2 3 4 5 4 3 2 1 0 1 2 3 4 5 4 3 2 1 ... (repeating)
- busy waiting

public class PrintInSequence {

    private volatile int val = 0;
    private volatile boolean shouldPrint = true;
    private volatile boolean isIncreasing = true;
    private ReentrantReadWriteLock.WriteLock lock = new ReentrantReadWriteLock().writeLock();
    public void increment() {
        lock.lock();
        if (!shouldPrint && isIncreasing) {
            val = val + 1;
            if (val == 5) {
                isIncreasing = false;
            }
            shouldPrint = true;
        }
        lock.unlock();
    }

    public void decrement() {
        lock.lock();
        if (!shouldPrint && !isIncreasing) {
            val = val - 1;
            if (val == 0) {
                isIncreasing = true;
            }
            shouldPrint = true;
        }
        lock.unlock();
    }

    //only one thread is calling print. So no contention in updating shouldPrint flag.
    public void printVar() {
        if (shouldPrint) {
            System.out.println(val);
            shouldPrint = false;
        }
    }

    public static void main(String args[]) {
        PrintInSequence printInSequence = new PrintInSequence();
        Thread t1 = new Thread(printInSequence::runIncrement);
        t1.start();
        Thread t2 = new Thread(printInSequence::runIncrement);
        t2.start();
        Thread t3 = new Thread(printInSequence::runPrint);
        t3.start();
        Thread t4 = new Thread(printInSequence::runDecrement);
        t4.start();
        Thread t5 = new Thread(printInSequence::runDecrement);
        t5.start();
    }

    private void runIncrement() {
        while(true) {
            this.increment();
        }
    }

    private void runPrint() {
        while (true) {
            this.printVar();
        }
    }

    private void runDecrement() {
        while (true) {
            this.decrement();
        }
    }
}

https://github.com/mission-peace/interview/blob/master/src/com/interview/multithreaded/FillupMatrix.java
* Write a program which fills up boolean matrix from top left to bottom right with true.
* This program should support two apis
* 1) void updateMatrix() which updates last position of matrix with true
* 2) boolean getVal(int x,int y) return boolean val at matrix[x][y]
*
* This program should be threadsafe.
*
* Solution
* Use AtomicLong to increment the value and return old value.
*
* Test cases
* 1) Try with single thread
* 2) Try with multiple threads and big matrix size.
public class FillupMatrix {

    private boolean matrix[][];
    private int size;
    private AtomicLong pos;
    public FillupMatrix(int size){
        matrix = new boolean[size][size];
        this.size = size;
        pos = new AtomicLong(-1);
    }
 
    public void updateMatrix(){
        long pos = next();
        updateMatrix(pos);
    }
 
    private void updateMatrix(long pos){
        if(pos >= size*size){
            throw new IllegalArgumentException("Out of memory");
        }
        matrix[(int)(pos/size)][(int)(pos%size)] = true;
    }
 
    private long next(){
        long val = pos.incrementAndGet();
        return val;
    }
 
    public boolean getVal(int x, int y){
        return matrix[x][y];
    }
 
    public static void main(String args[]) throws InterruptedException{
        int size = 5000;
        FillupMatrix fum = new FillupMatrix(size);
        ExecutorService executor = Executors.newFixedThreadPool(10);
        for(int i=0; i < size*size ; i++){
            executor.execute(() -> fum.updateMatrix());
        }
     
        executor.shutdown();
        executor.awaitTermination(10, TimeUnit.SECONDS);
        for(int i=0; i < size ; i++){
            for(int j=0; j < size; j++){
                assert fum.getVal(i, j);
            }
        }
    }
}

* Given a queue which gets millions of messages. Message is of form <Domain,Update>.
* You have 10000 domain tables. Also you have 50 worker threads. You can only get 
* data from front of the queue. Threads get data from the front and then update the 
* domain table. If work is being done on domain table you cannot apply another update.
* Update should also be applied sequentially. So an update coming later on should not
* be applied before an update coming sooner.

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts