Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I came across this question:

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?

I strongly feel we cannot take any advantage of threads here but interviewer is trying to understand my synchronization skills?

No need of code, just put some thoughts. I will implement by myself.

share|improve this question
    
Adding a C++ tag probably won't help much here. This questions around here are more conceptual stuff that transcends any particular language. –  cHao Oct 10 '12 at 19:02
    
Trust your feelings. I understand what they are going for, but I've never liked interview questions that deviate so far from how you should solve the problem in the real world. –  G_P Oct 10 '12 at 19:02
12  
@rplusg - I would be much more impressed by an interviewee who pointed out that the solution serializes the problem and merely adds thread overhead without actually doing any concurrent processing. The interviewer can always insist you answer the question as asked. –  David Harkness Oct 10 '12 at 20:32
    
if "each thread should print one word and give the control to next thread", that sounds like serial work, i.e. one thread is waiting for the previous one to finish and it's like passing a relay. why not just make it a single-threaded app in that case? –  amphibient Jan 31 '13 at 16:30
1  
i get it @Blrfl. it's kind of like i need to verify you know how to use tool X but was too lazy or sloppy to design an authentic application use case scenario that genuinely warrants the use of that tool so i just grabbed whatever was first at hand and pigeonholed my example into it sloppily. frankly, if i were asked that in an interview, i'd call him out on it and probably wouldn't wanna work with someone sloppy and halfast like that –  amphibient Jan 31 '13 at 17:34

8 Answers 8

up vote 17 down vote accepted

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])
share|improve this answer
    
Thanks for the bounty. Took me a while to figure out that mousing over it would say who gave it. –  kdgregory Feb 13 '13 at 16:54
    
Excuse my ignorance, can you elaborate more on how this solution is correct? is this some new fancy type of semaphores? I am sure however that the question is solved by a wait/notify solution [which semaphores use]. –  AJed Apr 13 at 0:01
    
It's just an array of standard semaphores. Nothing special about them. Notify is called "post" in some implementations. –  Karl Bielefeldt Apr 13 at 0:14
    
@KarlBielefeldt Well, if every thread x will wait for semaphore x, then all threads will be blocked and nothing will happen. If wait(sem) is actually acquire(sem) - then they will get into at the same time and there is no exclusion. Until there are more clarifications, I believe that there is something wrong in this pseudocode and it should not be the best answer. –  AJed Apr 13 at 18:16
    
This is just showing the loop for each thread. The setup code would have to post to the first semaphore to kick things off. –  Karl Bielefeldt Apr 13 at 18:36

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.

share|improve this answer
1  
I downvoted this answer (even though it inexplicably got 4 upvotes), because it doesn't answer the question that was asked. –  Robert Harvey Oct 10 '12 at 21:28
1  
@RobertHarvey: Sometimes people ask the wrong questions. The OP has a poor mindset to tackle technical interviews and this answer was an attempt to help put him/her on the right track. –  Demian Brecht Oct 10 '12 at 21:45
1  
@RobertHarvey I honestly believe this is the right answer for the question. The keyword here is "interview question" which is mentioned in the title and in the body of the question. For such a question, this is the right answer. If the question was only "I have m threads and a paragraph of n words, and I want to do this and that with them, what's the better approach", then yes, this answer would not have been appropriate for the question. As it is I think it's great. Paraphrasing: I've bombed quite a few interview question because I didn't follow the advice given here –  Shivan Dragon Jan 31 '13 at 14:23
    
@RobertHarvey it answers a related question, down-voting didn't accomplish anything. –  Marc DiMillo Feb 8 '13 at 10:50

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.

share|improve this answer
    
That whole note about the processor's L1 cache really intrigued me. Voted up. –  Marc DiMillo Feb 8 '13 at 10:51
  • 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.

share|improve this answer

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.

share|improve this answer

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 <<"canceled\n";
    }
    pthread_exit(NULL);
}
share|improve this answer

[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);
share|improve this answer

Interesting question. Here is my solution in Java using SynchronousQueue to create rendezvou 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;
    }

}

Update 1: Included code instead of linking to my gist on github

share|improve this answer
2  
Please include your solution here; a link-only post is not really an answer. Also, the OP asked for thoughts on the question, not code. –  Martijn Pieters Feb 6 '13 at 0:00

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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