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.

This question was asked in an Electronic Arts interview:

There are 3 threads. The first thread prints the numbers 1 to 10. The second thread prints the numbers 11 to 20. The third thread prints the numbers from from 21 to 30. Now, all three threads are running. The numbers are printed in an irregular order like 1, 11, 2, 21, 12 etc. If I want numbers to be printed in sorted order like 1, 2, 3, 4..., what should I do with these threads?

share|improve this question
2  
Hi user875036, programming puzzles and answers to interview questions aren't on-topic here. I'm currently checking to see if our sister site, Code Golf and Programming Puzzles.SE, would be a better fit. –  user8 Aug 16 '11 at 19:50
2  
I'm not sure why this was closed. It's a conceptual question that I feel is appropriate for Programmers. I voted to reopen. –  Thomas Owens Aug 16 '11 at 19:51
4  
@Thomas It seems less like a conceptual question and more of a "here's a brainteaser, please solve it." –  Anna Lear Aug 16 '11 at 19:53
    
@Mark Per discussion (in my Meta question at meta.programmers.stackexchange.com/questions/1812/…), I think this is on-topic. Ultimately, it's not a puzzle, but a conceptual question about concurrency and multi-threaded applications. My comment on ChrisF's answer (which was upvoted) suggests that questions that aren't "solve this puzzle", but are "is this a valid puzzle" or are asking for an explination of what the correct answer to a technical question is are on topic here. –  Thomas Owens Aug 16 '11 at 19:54
    
@Anna I don't get that at all. The correct answer is about joining threads, what join does, and how it works. That's pretty conceptual, IMO. –  Thomas Owens Aug 16 '11 at 19:55
show 3 more comments

3 Answers

It depends on whether there is a lot of computational effort interspersed with the printing. If the threads are only printing the output, then the best solution is probably to eliminate the three threads. Instead, simply call the functions that print the number in order so that the numbers come out in order. If for some reason three threads are absolutely needed, then block each thread (when it first tries to output, if you only control the output function) until the previous thread(s) are finished.

If the printing is interspersed with computation, then making the threads run in sequence will increase the run time by reducing computational overlap. In that case, the best solution is probably to let all three threads run, directing their output to some intermediary locations. When all three threads are finished, their outputs can be combined as needed.

It's hard to figure out the ideal solution with a problem that's so weakly specified. And I would suspect that the idea was not for you to come up with the perfect solution but to demonstrate that you are capable of understanding the types of solutions that would be used and under what circumstances each one would be suitable.

share|improve this answer
    
This really over complicates the question to the point of nuking it from orbit. To me, the interviewer just wants to know how much knowledge the interviewee has about concurrency, using a very simple example. –  Thomas Owens Aug 16 '11 at 21:50
    
I agree. I'm not sure what you can do other than to point out that the original question is ambiguous on points that determine what the right solution is. You can mention one or two basic solution approaches and perhaps continue to explain where each is appropriate. The point of the question is likely not to give the "right answer" but to demonstrate a grasp of concurrency issues. –  David Schwartz Aug 18 '11 at 1:24
add comment

Since you originally tagged this question with C++, I would assume that is the language of choice for either you or the interviewer. As an interviewer, if this was for a C++ development position or you said your answers would be based in C++, I would be looking for a discussion of the pthread library in *nix systems or Win32 Process and Thread functions on Windows. I would also expect a conceptual answer that uses some kind of implementation that you are familiar with.

The main point that I would probably expect to here is about joining threads. The act of joining two threads means that one thread will wait for the execution of another thread to complete before executing. The thread that calls join will suspect execution until the target thread finishes.

In your example, this means that you want to join the third thread to the second thread and the second thread to the first thread. This will allow the first thread to print the numbers 1 through 10, then the second thread will print the numbers 11 through 20, then finally the third thread will print the numbers 21 through 30.

share|improve this answer
add comment

This problem is solved at http://www.yolinux.com/TUTORIALS/LinuxTutorialPosixThreads.html but for 1-3,3-6,6-10

I am copy pasting the code below

01 #include <stdio.h>  
02 #include <stdlib.h>  
03 #include <pthread.h>  
04    
05 pthread_mutex_t count_mutex     = PTHREAD_MUTEX_INITIALIZER;  
06 pthread_cond_t  condition_var   = PTHREAD_COND_INITIALIZER;  
07    
08 void *functionCount1();  
09 void *functionCount2();  
10 int  count = 0;  
11 #define COUNT_DONE  10  
12 #define COUNT_HALT1  3  
13 #define COUNT_HALT2  6  
14    
15 main()  
16 {  
17    pthread_t thread1, thread2;  
18    
19    pthread_create( &thread1, NULL, &functionCount1, NULL);  
20    pthread_create( &thread2, NULL, &functionCount2, NULL);  
21    
22    pthread_join( thread1, NULL);  
23    pthread_join( thread2, NULL);  
24    
25    printf("Final count: %d\n",count);  
26    
27    exit(0);  
28 }  
29    
30 // Write numbers 1-3 and 8-10 as permitted by functionCount2()  
31    
32 void *functionCount1()  
33 {  
34    for(;;)  
35    {  
36       // Lock mutex and then wait for signal to relase mutex  
37       pthread_mutex_lock( &count_mutex );  
38    
39       // Wait while functionCount2() operates on count  
40       // mutex unlocked if condition varialbe in functionCount2() signaled.  
41       pthread_cond_wait( &condition_var, &count_mutex );  
42       count++;  
43       printf("Counter value functionCount1: %d\n",count);  
44    
45       pthread_mutex_unlock( &count_mutex );  
46    
47       if(count >= COUNT_DONE) return(NULL);  
48     }  
49 }  
50    
51 // Write numbers 4-7  
52    
53 void *functionCount2()  
54 {  
55     for(;;)  
56     {  
57        pthread_mutex_lock( &count_mutex );  
58    
59        if( count < COUNT_HALT1 || count > COUNT_HALT2 )  
60        {  
61           // Condition of if statement has been met.   
62           // Signal to free waiting thread by freeing the mutex.  
63           // Note: functionCount1() is now permitted to modify "count".  
64           pthread_cond_signal( &condition_var );  
65        }  
66        else 
67        {  
68           count++;  
69           printf("Counter value functionCount2: %d\n",count);  
70        }  
71    
72        pthread_mutex_unlock( &count_mutex );  
73    
74        if(count >= COUNT_DONE) return(NULL);  
75     }  
76    
77 } 
share|improve this answer
    
I am trying to write this using condition_variable of C++0x, no success yet. Can someone give me this program in latest C++11 –  user875036 Nov 4 '12 at 11:25
add comment

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.