Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
4
of 12 vote

// 1 process

if(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 ?????

- S O U N D W A V E October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Great explanation. But answer will be 24 as 5 more processes makes it 6 overall. 6*4=24.

- krshnsh October 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

if(fork() && fork()) // shouldn't this create 3 more processes. As the 2nd child of main process will execute the left fork successfully?

- prince October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 votes

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.

- Patrick Chan October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

+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.

- S O U N D W A V E October 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

===========

- coder November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

18 not 17

- coder November 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 5 vote

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.

- Eduraser October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- takeda64 October 30, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- pshaikh.jobs October 24, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

64 :)

- Vibhav October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can somebody explain semantics of fork? How does it fork current thread?

- gstepanov@griddynamics.com October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

[*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.

- S O U N D W A V E October 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I compile and run it. the result is 20

- Shin Qi October 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- 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

- takeda64 October 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

did anyone try executing? comes out to be 19 on a Linux box running Ubuntu. I don't know how so you may try justifying that.

- darth vader November 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Definitely not a Google question , this totally depends on the state of the scheduler i dont think they are this stupid

- osusosu December 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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!

- liveusr January 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

24

- brijraj ji September 01, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

20
fork() && fork() && fork() -- 4 ( assuming 1 process before this step)
(fork() || fork()) && fork() -- 5 ( assuming 1 process before this step)

Total - 4*5 = 20

- Deepak Tiwari December 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- chetan chauhan September 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Stop posting homework questions. Fork off.

- Anonymous October 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Compile and run defeats this MCQ.
This is not out of the realm of reality for Google SRE interviews.

- S O U N D W A V E October 22, 2013 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More