It sounds to me like they are leading you toward a semaphore solution. Semaphores are used to signal another thread that it’s their turn. They are used much less frequently than mutexes, which I guess is why they think it’s a good interview question. It’s also why the example seems contrived.

Basically, you would create m semaphores. Each thread x waits on semaphore x then posts to semaphore x+1 after doing its thing. In pseudocode:

loop:
    wait(semaphore[x])
    if no more words:
        post(semaphore[(x+1) % m])
        exit
    print word
    increment current word pointer
    post(semaphore[(x+1) % m])

In my opinion, this is a fabulous interview question — at least assuming (1) the candidate is expected to have deep knowledge of threading, and (2) the interviewer also has deep knowledge and is using the question to probe the candidate. It’s always possible that the interviewer was looking for a specific, narrow answer, but a competent interviewer should be looking for the following:

• Ability to differentiate abstract concepts from concrete implementation. I throw this one in primarily as a meta-comment on some of the comments. No, it doesn’t make sense to process a single list of words this way. However, the abstract concept of a pipeline of operations, which may span multiple machines of differing capabilities, is important.
• In my experience (nearly 30 years of distributed, multi-process, and multi-threaded applications), distributing the work is not the hard part. Gathering the results and coordinating independent processes are where most threading bugs occur (again, in my experience). By distilling the problem down to a simple chain, the interviewer can see how well the candidate thinks about coordination. Plus, the interviewer has the opportunity to ask all sorts of follow-on questions, such as “OK, what if each thread has to send its word to another thread for reconstruction.”
• Does the candidate think about how the processor’s memory model might affect implementation? If the results of one operation never get flushed from L1 cache, that’s a bug even if there’s no apparent concurrency.
• Does the candidate separate threading from application logic?

This last point is, in my opinion, the most important. Again, based on my experience, it becomes exponentially more difficult to debug threaded code if the threading is mixed with the application logic (just look at all the Swing questions over on SO for examples). I believe that the best multi-threaded code is written as self-contained single-threaded code, with clearly-defined handoffs.

With this in mind, my approach would be to give each thread two queues: one for input, one for output. The thread blocks while reading the input queue, takes the first word off of the string, and passes the remainder of the string to its output queue. Some of the features of this approach:

• The application code is responsible for reading a queue, doing something to the data, and writing the queue. It doesn’t care whether it is multi-threaded or not, or whether the queue is an in-memory queue on one machine or a TCP-based queue between machines that live on opposite sides of the world.
• Because the application code is written as-if single-threaded, it’s testable in a deterministic manner without the need for a lot of scaffolding.
• During its phase of execution, the application code owns the string being processed. It doesn’t have to care about synchronization with concurrently-executing threads.

That said, there are still a lot of grey areas that a competent interviewer can probe:

• “OK, but we’re looking to see your knowledge of concurrency primitives; can you implement a blocking queue?” Your first answer, of course, should be that you’d use a pre-built blocking queue from your platform of choice. However, if you do understand threads, you can create a queue implementation in under a dozen lines of code, using whatever synchronization primitives your platform supports.
• “What if one step in the process takes a very long time?” You should think about whether you want a bounded or unbounded output queue, how you might handle errors, and effects on overall throughput if you have a delay.
• How to efficiently enqueue the source string. Not necessarily a problem if you’re dealing with in-memory queues, but could be an issue if you’re moving between machines. You might also explore read-only wrappers on top of an underlying immutable byte array.

Finally, if you have experience in concurrent programming, you might talk about some frameworks (eg, Akka for Java/Scala) that already follow this model.

Interview questions are sometimes actually trick questions, intended to make you think about the problem that you’re trying to solve. Asking questions about a question are an integral part of approaching any problem, whether it’s in the real world or in an interview. There are a number of videos circulating the internet on how to approach questions in technical interviews (look particularly for Google and perhaps Microsoft).

“Just try to answer, and get the hell out of there..”

Approaching interviews with this thought pattern will lead you to bombing any interview for any company worth working for.

If you don’t think that you gain much (if anything from threading), tell them that. Tell them why you don’t think there is any benefit. Have a discussion with them. Technical interviews are meant to be an open discussion platform. You may end up learning something about how it can be useful. Don’t just forge ahead blindly trying to implement something your interviewer told you to.

• First tokenize the paragraph with appropriate delimiters and add the words
  to a Queue.

• Create N number of threads and keep it in a thread pool.

• Iterate over the thread pool and start the thread and wait for the
  thread to join. And start the next thread once the first thread ends
  and so on.

• Each Thread should just poll the queue and prints it.

• Once all threads are used within the thread pool, start from the
  beginning of the pool.

As you said, I don’t think this scenario benefits greatly, if at all from threading. It’s most likely slower than a single threaded implementation.

However, my answer would be to have each thread in a tight loop attempting to access a lock which controls access to the word array index. Each thread grabs the lock, gets the index, gets the corresponding word from the array, prints it, increments the index then releases the lock. The threads exits when the index is at the end of the array.

Something like this:

while(true)
{
    lock(index)
    {
        if(index >= array.length())
          break;
        Console.WriteLine(array[index]);
        index++;
    }
}

I think this should achieve the one thread after another requirement, but the ordering of the threads is not guaranteed. I’m curious to hear other solutions as well.

Use condition wait/signal APIs to solve this problem.

Let say first thread picks 1 word and meanwhile rest all threads are waiting for a signal.
1st thread print 1st word and generates signal to next thread and then 2nd thread print the second word and generates signal to 3rd thread and so on.

#include <iostream>
#include <fstream>
#include <pthread.h>
#include <signal.h>
pthread_cond_t cond[5] = {PTHREAD_COND_INITIALIZER,};
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

using namespace std;

string gstr;

void* thread1(void*)
{
    do {
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[0],&mutex);
    cout <<"thread1 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread2(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[1],&mutex);
    cout <<"thread2 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread3(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[2],&mutex);
    cout <<"thread3 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread4(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[3],&mutex);
    cout <<"thread4 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

void* thread5(void*)
{
    do{
    pthread_mutex_lock(&mutex);
    pthread_cond_wait(&cond[4],&mutex);
    cout <<"thread5 :"<<gstr<<endl;
    pthread_mutex_unlock(&mutex);
    }while(1);
}

int main()
{
    pthread_t t[5];
    void* (*fun[5])(void*);
    fun[0]=thread1;
    fun[1]=thread2;
    fun[2]=thread3;
    fun[3]=thread4;
    fun[4]=thread5;

    for (int i =0 ; i < 5; ++i)
    {
        pthread_create(&t[i],NULL,fun[i],NULL);
    }
    ifstream in;
    in.open("paragraph.txt");
    int i=0;
    while(in >> gstr)
    {

        pthread_cond_signal(&cond[i++]);
        if(i == 5)
            i=0;
        usleep(10);
    }
    for (int i =0 ; i < 5; ++i)
    {
        int ret = pthread_cancel(t[i]);
        if(ret != 0)
            perror("pthread_cancel:");
        else
            cout <<"canceledn";
    }
    pthread_exit(NULL);
}

[Terms used here maybe specific to POSIX threads]

It should be possible to use a FIFO mutex as well to solve this problem.

Where to use :

Assume two threads T1 and T2 are trying to execute a critical section. Both don’t have much to do outside this critical section and hold locks for a good amount of time. So, T1 may lock, execute and unlock and signal T2 for wakeup. But before T2 could wakeup and acquire lock, T1 reacquires lock and execute. In this way, T2 may have to wait a very long time before it actually gets the lock or may be not.

How it works / How to implement :

Have a mutex to lock on. Initialize Thread Specific Data (TSD) for each thread to a node containing thread id and semaphore. Also, have two variables – owned (TRUE or FALSE or -1), owner (owner thread id). In addition, keep a waiters queue and a pointer waiterLast pointing to last node in waiters queue.

lock operation :

node = get_thread_specific_data(node_key);
lock(mutex);
    if(!owned)
    {
        owned = true;
        owner = self;
        return success;
    }

    node->next = nullptr;
    if(waiters_queue == null) waiters_queue = node;
    else waiters_last->next = node;

    waiters_last = node;
unlock(mutex);
sem_wait(node->semaphore);

lock(mutex);
    if(owned != -1) abort();
    owned = true;
    owner = self;
    waiters_queue = waiters_queue->next;
 unlock(mutex);

unlock operation :

lock(mutex);
    owner = null;
    if(waiters_queue == null)
    {
        owned = false;
        return success;
    }
    owned = -1;
    sem_post(waiters_queue->semaphore);
unlock(mutex);

Interesting question. Here is my solution in Java using SynchronousQueue to create a rendezvous channel between threads:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.SynchronousQueue;

public class FindNWordsGivenMThreads {

    private static final int NUMBER_OF_WORDS = 100;
    private static final int NUMBER_OF_THREADS = 5;
    private static final Stack<String> POISON_PILL = new Stack<String>();

    public static void main(String[] args) throws Exception {
        new FindNWordsGivenMThreads().run();
    }

    private void run() throws Exception {
        final Stack<String> words = loadWords();
        SynchronousQueue<Stack<String>> init = new SynchronousQueue<Stack<String>>();
        createProcessors(init);
        init.put(words);
    }

    private void createProcessors(SynchronousQueue<Stack<String>> init) {
        List<Processor> processors = new ArrayList<Processor>();

        for (int i = 0; i < NUMBER_OF_THREADS; i++) {

            SynchronousQueue in;
            SynchronousQueue out;

            if (i == 0) {
                in = init;
            } else {
                in = processors.get(i - 1).getOut();
            }

            if (i == (NUMBER_OF_THREADS - 1)) {
                out = init;
            } else {
                out = new SynchronousQueue();
            }

            Processor processor = new Processor("Thread-" + i, in, out);
            processors.add(processor);
            processor.start();

        }

    }

    class Processor extends Thread {

        private SynchronousQueue<Stack<String>> in;
        private SynchronousQueue<Stack<String>> out;

        Processor(String name, SynchronousQueue in, SynchronousQueue out) {
            super(name);
            this.in = in;
            this.out = out;
        }

        @Override
        public void run() {

            while (true) {

                Stack<String> stack = null;
                try {
                    stack = in.take();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }

                if (stack.empty() || stack == POISON_PILL) {
                    System.out.println(Thread.currentThread().getName() + " Done!");
                    out.offer(POISON_PILL);
                    break;
                }

                System.out.println(Thread.currentThread().getName() + " " + stack.pop());
                out.offer(stack);
            }
        }

        public SynchronousQueue getOut() {
            return out;
        }
    }

    private Stack<String> loadWords() throws Exception {

        Stack<String> words = new Stack<String>();

        BufferedReader reader = new BufferedReader(new FileReader(new File("/usr/share/dict/words")));
        String line;
        while ((line = reader.readLine()) != null) {
            words.push(line);
            if (words.size() == NUMBER_OF_WORDS) {
                break;
            }
        }
        return words;
    }
}

I’d say that this kind of question is very hard to answer, because it asks for the best way to do something completely stupid. My brain just doesn’t work that way. It cannot find solutions for stupid questions. My brain would immediately say that under these conditions, using multiple threads is pointless, so I would use a single thread.

I’d then ask them to either give a real world question about threading, or to let me give a real world example of some serious threading.