* 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.
* 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.