Google Interview Question Software Engineer / Developers
Country: India
Interview Type: Written Test
Great explanation. But answer will be 24 as 5 more processes makes it 6 overall. 6*4=24.
if(fork() && fork()) // shouldn't this create 3 more processes. As the 2nd child of main process will execute the left fork successfully?
I tried. It's 20. But in my opinion, your explanation is not completely correct.
if(fork() || fork())
The above line will only create 2 more processes. Here is why:
The parent process will only do one fork() and get a positive number. It then skips the second fork (short circuit). The newly created process will try the second fork and create another new process (this second new process will not go into the body of the if-statement). So, in total 2 new processes will be created after this line.
Why 20? It is because, we have 4 processes after the 1st if-statement. And each of them will create create 4 more processes after going through the 2nd if-statement. So, in total, we have 16 newly created processes after the 2nd if-statement. So, 4 processes after 1st if-statement and 16 processes after 2nd if-statement. We have 20 processes in total before the printf. As a result, there are 20 "Hello world" being printed out.
+1 @Chan.
TBH, when I know I can solve a problem I rush in solving/explaining it.
It works really well in general, because you can learn a lot and get things done faster, but it fails when you need to explain your thoughts. Gotta work on it.
Answer is 17. (none of the given choices)
f0- primary execution thread
f1-f6 are the forks from top to bottom: each one is a print of Hello world.
========
f0
f1 f2 f3 f4 f6
f2 f3 f4 f6
f3 f4 f6
f4 f5 f6
f6
f6
===========
24
You have to take into account two things:
- fork() returned value: If you take into account that fork() returns the pid of the child to the parent and 0 to the child.
- The order of evaluation of operands:
+ In case of AND (&&), after evaluation of left operand, right operand will be evaluated only if left operand evaluates to non-zero.
+ In case of OR (||), after evaluation of left operand, right operand will be evaluated only if left operand evaluates to zero.
I computed myself and it came to 20 (value in parenthesis is what the if statement be like for the specific process, if not provided the fork is after the if statement):
- First part: parent(FF), child(TF), child(TT), child (this effectively multiplies next part by 4)
- Second part: parent(FF), child(TF), child, child(FT), child -> 5 processes
4*5 = 20
After seeing your solution and that it had 3 votes I started doubting myself but I then just compiled the code and run and it showed the message 20 times as well.
For me answer is coming out to be "20". Number of processes spawned by original process (P) is actually number of times hello world is printed.
Let each "fork" be labeled by its position in the program (first fork - 1, second fork - 2),
Let each process be labeled by sequence of forks that gave birth to that process (original invokation labeled P0).
fork returns pid of a child in a parent and 0 in a child process. Also remember "short circuiting" in evaluation of condition (if first value is false in AND condition then condition is false, if its true in OR condition then condition is true, no need to evaluate second value in condition).
Here is how forking will work -
P0 (parent of all, invocation by user)
P1, P2, P3, P4, P6 (no P5 because condition will be true after fork#4 returns)
P14, P16,P24,P26, P34, P36, P45, P46
P145, P146, P245, P246, P345, P346
That's it. Counting it , 20 is answer.
[*nix OS specific]
a process calls fork() (call it this process 1 which dives into fork)
This causes OS, via a system call, to create a copy of process 1, call it process 2, with some PID
then fork call returns into both processes as if they had executed that bit of code
so 1 process dives in, 2 dive back out... how to differentiate in the two different programs that are now executing the same code from thereon?
in process1: fork returns a positive integer (PID of process 2)
in process2: fork returns 0
There on each independently executes the rest of the code assuming on that line, and for that call, fork returned what it did for them.
consider first if block,
parent->child1 [ if(fork() ]
. |
. v
parent->child2 [ if(fork() && fork()) ]
. |
. v
parent->child3 [ { fork(); } ]
so at this point, there are 4 processes: 3 children + 1 parent
consider next if block for one process,
parent->child1 [ if(fork() ]
. | . . . . . . |
. | . . . . . . v
. | . . . . . child1->child2 [ if(fork() || fork()) ]
. | . . . . . . |
. | . . . . . . v
. | . . . . . child1->child3 [ { fork(); } ]
. |
. v
parent->child4 [ { fork(); } ]
so here you'll get 5 processes: 4 children + 1 parent
hence total processes 4x5=20, hence 20 prints!
Answer is 20
_____0_______Hello World
|
| ___0___ Hello World
| |
_____0______|___1___|___1__ Hello World
|
| ___0___Hello World
| |
|_____1______|___1___ Hello World
|
|
| ____0____ Hello World
| | ____0___ Hello World
| | |
| ___0____|___1______|___1___ Hello World
| | ___0___Hello World
| | |
| | |
| _______0_______|___1____|___1___Hello World
| |
| | _____0____Hello World
| | |
| | | ____0___ Hello World
| | | |
| | _____0____ |___1__|____1___Hello World
| | |
| | | ___0___ Hello World
| | | |
| | ____0____|_____1____|___1___ Hello World
| | | ____0___ Hello World
| | | | ____0____Hello World
| | | | |
| | | ___0___|____1___|____1____Hello World
| | | |
| | | |
| | | | ____0____ Hello World
| | | | |
____ |_______1_________|_____1_____|___1____|______1______|____1____ Hello World
Here 0 and 1 are return value by fork() call (i.e 0 for child and 1 for parent)
// 1 process
- S O U N D W A V E October 22, 2013if(fork() && fork()) // creates 2 more
{
fork(); //very first process will get here and create 1 more
}
//4 processes reach here
=== assume 1 process reached here though ===
if(fork() || fork()) //creates 3 more (even first child will try second fork)
{
fork(); // 2 processes reach here (original plus 1st child that tried 2nd fork above)
}
// Thus above sequence will create 5 more processes
4 x 5 = 20 ?????