Print Numbers Sequentially Using N Threads
This is one of the interview questions i came across as part of preparation for the amazon interview.
You are given a paragraph , which contain n number of words, you are given m threads. What you need to do is , each thread should print one word and give the control to next thread, this way each thread will keep on printing one word , in case last thread come, it should invoke the first thread. Printing will repeat until all the words are printed in paragraph. Finally all threads should exit gracefully. What kind of synchronization will use?
First of all, this is an interview question the same scenario can be well performed without using threads. But answering this question tests how the interviewee is able to co-ordinate the threads, sharing the data between threads. And tests the understanding and knowledge towards concurrency.
I have just slightly modified the problem instead of using words the m threads should print the numbers sequentially and following the same thread order specified in the problem.
Let's understand this problem first. When one thread is performing the job (either printing a word in the paragraph or printing a incremented number) all other (m - 1) threads should be in waiting. When thread i performed its job thread i should wait and notify to thread (i +1)%m to do the job and so on. So, the vital part is after doing the job thread should wait and should notify the particular thread.
So, Let's assume we have created a lock object and all the threads synchronizes on the same lock object.
doJob(); // Print the number
This does the job of printing the numbers in sequential order but not in the thread order specified. The problem here is thread ordering so we need to implement in such a way that one thread should be able to control the next thread, at the same time it should wait after doing the job.
So, I will create a lock object for each created thread. At the same time i will pass the lock object of the thread which i need to control. From the below code you can understand how it works
// Pass the Thread's own lock and the lock of the thread which it needs to notify
// Acquire the Current Object Lock
synchronized (thisLock) {
synchronized (nextLock) {
printIncrement(threadName);
} catch (InterruptedException e) {
The above program achieves stopping all other threads when it is executing and notifies its successor thread.But there is still a problem with this approach. The problem is when m threads are started at shot we don't which one will get executed first. Because of the simultaneous start the above program got screwed (Even i felt the same for 1/2 hour while doing). We can fix this if the thread creation is in the following way.
1) Create all the m lock objects for the m threads
2) Create a Thread Object and start it and then pause the main thread until the created thread goes into wait mode
3) Proceed to 2 until m threads not created.
So here's the final program in java
public class PrintNThreads {
public static void main(String[] args) {
int n = 10; //Number of threads
Object[] lockObjects = new Object[n];
lockObjects[i] = new Object();
NumberThread tempThread = new NumberThread("Thread-"+(i+1), lockObjects[i], lockObjects[(i+1)%n]);
// Don't start the next thread untill the first thread is waiting. For the last thread we dont need to wait
while(!tempThread.isFirstWaitComplete());
class NumberThread extends Thread
static volatile int i = 0;
static boolean printIncrement(String threadName)
// e.g. Print till 10000 numbers.
System.out.println(threadName+" "+(++i));
private boolean isFirstWaitComplete;
public NumberThread(String threadName,Object thisLock, Object nextLock) {
this.nextLock = nextLock;
this.thisLock = thisLock;
this.threadName = threadName;
synchronized (thisLock) {
synchronized (nextLock) {
// I am just assuming this is sequence number print job. you can insert whatever you want.
if(!printIncrement(threadName))
isFirstWaitComplete = true;
} catch (InterruptedException e) {
public synchronized boolean isFirstWaitComplete() {
synchronized (thisLock) {
return isFirstWaitComplete;
Comments and Suggestions are most welcome.