Google Interview Questions and the Google Campus Interview Process 2011
Hi Guys,
I know I'm not really writing a letter, but I really felt that I should jot down my impression of the Google Campus Placement process of 2010 before I forgot most of it. As a lot of my Facebook friends know by now, I've been given a campus placement offer by Google. Naturally, I'm really excited about it. Here's the story of how it all happened - a blow by blow account. (Tip: The interview questions are well marked out in the narrative and you can skip to them if you're not really interested in the campus process narrative).
Google's hiring process is known to be pretty tough and their engineers are counted among the best in the world. The first whiff of that came through when a couple of young techies and an HR landed on campus sometime in November to carry out their written test. 50 eligible candidates for the test and 50 copies of the question paper: +3 -1 was the scoring scheme - so no guessing! (or atleast very calculative guessing). Most of the interview questions were pretty standard in nature - probability, expectation, some coding questions. Judge for yourself. Here are the questions for 2010 (reconstructed from collective memory of all the candidates that gave the test).
Google Placement Paper 2010
10th November 2010
Eligibility : B Tech/IDD/M Tech/PHD-CSE
CGPA-7.0 for B Tech, 7.5 for M Tech
Time Allocated : 65 mins
There were 17 objective questions and 1 subjective question.
1) Given preorder traversal of a Binary Search Tree. From the given options you have to select which one can possibly be the inorder traversal of the tree.
[If it is indeed a BST, then the correct answer should be the one which is in sorted order]
2) If u could find the (n/4)th element of an array in O(n) time, then what is the worst time complexity of quick sort algo if this algo is used to decide the pivot element.
Answer : It's O(nlogn), since we can write the execution time as
T(n) = . T(n . r) + T(n (1 - r)) + O(n)
where r is 1/4 for this case.
for any r < 1, we have the expression recursively approaching
T(n ) = T(n * r^2) + 2 T(n * r * (1 - r)) + T(n * (1 - r)^2) + 2O(n) ; [O(n) = O(nr) + O(n(1-r))]
the number of O(n)s adds = log n/log r or logn/log(1-r) whichever is higher... but just logn times
3) find the min no of comparisons required to find both the max and min elements of an array containing 20 elements.
Ans) Can be done in a total of 28 comparisons.
4) If an array[0...m-1,0....n-1] is stored in column major format how will u find the (i,j) element?
a)i*n+j
b)i*m+j
c)j*n+i
d)j*m+i
5)If an insurance company pays $5000 for complete loss, $1500 in case of a loss of $2000 and more and nothing in case the loss is less that $2000. It obviously pays nothing in case of no loss.
If the probability of the first 3 events are 0.02,0.10 and 0.3 , find what should the company charge in order to make a profit of $50 from each customer
6) the prob of finding the parking slot occupied is 1/3.
U find it empty for 9 consecutive days.
Find the prob that it will be empty on the 10th day.
7) consider a NxN matrix in which the elements are either 0 or 1.
Find how many such matrixes are possible that are symmetric in nature(the matrix and its transpose count as 1.
8) 1<=i,j,k<=300.
Find (i,j,k) pairs such that their sum is divisible by 3.
(2,2,1) and (2,1,2) are counted as different.
9) in the loop
int counter=0;
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
for(k=j+1;k<10;k++)
for(l=k+1;l<10;l++)
for(m=l+1;m<10;m++)
counter++;
Find the value of counter in the end.
Ans. 10C5
i,j,k,l,m can be any 5 different numbers between [0-9] such that i<j<k<l<m. So, choose any 5 numbers and there is only one way to arrange.
10) Consider a set S of the first 10 natural numbers.
Find the number of subsets that do not contain consecutive elements.
Ans)
11) A question on TestandSet(), which are used as locks.....taught in OS course.
enter_CS() //This is what I remember
{
while(TestandSet(X));
}
Exit_CS()
{
X=0;
}
12) A disk contains 16 partition unit , each unit contains 128 subunits, and each subunit contains 256 sectors of 512 byte each.
Find out what is total storage capacity?
Also find out the no of bits required to identify each sector?
Ans) 256 MB, 19 bits
13) Which of the following is not a Regular Language :
a)None given
b)(0^i).(1^j) such that i<j
c)(0^i).w.(1^j) such that w belongs to {0,1}* and i>=0
d) such that every pth input digit is 0 where p is a prime number
14)find the output
void f(char * x)
{
x++;
*x='a';
}
int main()
{
char * str="hello";
f(str);
cout<<str;
system("pause");
return 0;
}
a) hello
b)hallo
c)allo
d)empty string
15)Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not.
a)O(lgn)
b)O(n)
c)O((lgn)^2)
d)O(1)
[Ans is option d]
16)The weight of a squence a0, a1,a2,... ,an is defined as a0+a1/2+a2/(2^2)+...+an/(2^(n)). A subsequence of a sequence is said to be a sequence with some of the elements deleted from the original sequence but the order of the sequence remaining the same. Now let X be the maximum weight for a subsequence of a sequence a0,a1,a2,a3..,an. And Y be the maximum weight for a subsequence of the sequence a1,a1,a2,a3.....,an. Then X in terms of Y is
a) max(Y,a0+Y)
b)max(Y,a0+Y/2)
c)max(Y,a0+2*Y)
d)a0+Y/2
[opn b]
17) What is the complexity for finding all the leaders in an array? A leader is defined as an element which is greater than all the elements to its right.
18) Subjective question
Write a program to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.
For Ex : in the circular array ABCDEABCCDE
The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array.
10th November 2010
Eligibility : B Tech/IDD/M Tech/PHD-CSE
CGPA-7.0 for B Tech, 7.5 for M Tech
Time Allocated : 65 mins
There were 17 objective questions and 1 subjective question.
1) Given preorder traversal of a Binary Search Tree. From the given options you have to select which one can possibly be the inorder traversal of the tree.
[If it is indeed a BST, then the correct answer should be the one which is in sorted order]
2) If u could find the (n/4)th element of an array in O(n) time, then what is the worst time complexity of quick sort algo if this algo is used to decide the pivot element.
Answer : It's O(nlogn), since we can write the execution time as
T(n) = . T(n . r) + T(n (1 - r)) + O(n)
where r is 1/4 for this case.
for any r < 1, we have the expression recursively approaching
T(n ) = T(n * r^2) + 2 T(n * r * (1 - r)) + T(n * (1 - r)^2) + 2O(n) ; [O(n) = O(nr) + O(n(1-r))]
the number of O(n)s adds = log n/log r or logn/log(1-r) whichever is higher... but just logn times
3) find the min no of comparisons required to find both the max and min elements of an array containing 20 elements.
Ans) Can be done in a total of 28 comparisons.
4) If an array[0...m-1,0....n-1] is stored in column major format how will u find the (i,j) element?
a)i*n+j
b)i*m+j
c)j*n+i
d)j*m+i
5)If an insurance company pays $5000 for complete loss, $1500 in case of a loss of $2000 and more and nothing in case the loss is less that $2000. It obviously pays nothing in case of no loss.
If the probability of the first 3 events are 0.02,0.10 and 0.3 , find what should the company charge in order to make a profit of $50 from each customer
6) the prob of finding the parking slot occupied is 1/3.
U find it empty for 9 consecutive days.
Find the prob that it will be empty on the 10th day.
7) consider a NxN matrix in which the elements are either 0 or 1.
Find how many such matrixes are possible that are symmetric in nature(the matrix and its transpose count as 1.
8) 1<=i,j,k<=300.
Find (i,j,k) pairs such that their sum is divisible by 3.
(2,2,1) and (2,1,2) are counted as different.
9) in the loop
int counter=0;
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
for(k=j+1;k<10;k++)
for(l=k+1;l<10;l++)
for(m=l+1;m<10;m++)
counter++;
Find the value of counter in the end.
Ans. 10C5
i,j,k,l,m can be any 5 different numbers between [0-9] such that i<j<k<l<m. So, choose any 5 numbers and there is only one way to arrange.
10) Consider a set S of the first 10 natural numbers.
Find the number of subsets that do not contain consecutive elements.
Ans)
Subsets of length 0 = 1
Subsets of length 1 = 10
Subsets of length 2 = 36
Subsets of length 3 = 56
Subsets of length 4 = 35
Subsets of length 5 = 6
Total = 144
11) A question on TestandSet(), which are used as locks.....taught in OS course.
enter_CS() //This is what I remember
{
while(TestandSet(X));
}
Exit_CS()
{
X=0;
}
12) A disk contains 16 partition unit , each unit contains 128 subunits, and each subunit contains 256 sectors of 512 byte each.
Find out what is total storage capacity?
Also find out the no of bits required to identify each sector?
Ans) 256 MB, 19 bits
13) Which of the following is not a Regular Language :
a)None given
b)(0^i).(1^j) such that i<j
c)(0^i).w.(1^j) such that w belongs to {0,1}* and i>=0
d) such that every pth input digit is 0 where p is a prime number
14)find the output
void f(char * x)
{
x++;
*x='a';
}
int main()
{
char * str="hello";
f(str);
cout<<str;
system("pause");
return 0;
}
a) hello
b)hallo
c)allo
d)empty string
15)Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not.
a)O(lgn)
b)O(n)
c)O((lgn)^2)
d)O(1)
[Ans is option d]
16)The weight of a squence a0, a1,a2,... ,an is defined as a0+a1/2+a2/(2^2)+...+an/(2^(n)). A subsequence of a sequence is said to be a sequence with some of the elements deleted from the original sequence but the order of the sequence remaining the same. Now let X be the maximum weight for a subsequence of a sequence a0,a1,a2,a3..,an. And Y be the maximum weight for a subsequence of the sequence a1,a1,a2,a3.....,an. Then X in terms of Y is
a) max(Y,a0+Y)
b)max(Y,a0+Y/2)
c)max(Y,a0+2*Y)
d)a0+Y/2
[opn b]
17) What is the complexity for finding all the leaders in an array? A leader is defined as an element which is greater than all the elements to its right.
18) Subjective question
Write a program to find the index in an circular array such that the string that is formed starting from that index is first in lexicographic order.
For Ex : in the circular array ABCDEABCCDE
The answer is 6 because the circular string starting from the element A in the 6th position comes first in the dictionary formed from all the possible strings of the circular array.
The pre-placement talk was well received (especially since the brother of one of the 2010 B.Tech passouts and an IIT Roorkee alumni had come for giving the PPT). Most of the interaction was very informal with questions ranging from mundane to the technical. Google Instant and the "Did you mean?" feature of Google were the hot topics of discussion and of course, how can we omit the discussion on the Google core search algorithm. The actual interview process was slated for 29th November. A number of questions were asked by the curious audience and very candidly answered by the techies.
The interview process began dot on time at 6:00 pm on 29th November. A couple of minutes spent getting things in order and off we go!
The first indication that we were dealing with a company that was serious about the people it hired was the fact that it had arrived on campus as a team of 16 people hiring for 3 different profiles. The fact was that they were interviewing only 12 candidates shortlisted from the written test. A quick, back of the envelope calculation shows that they've spent more than Rs. 1 lakh per campus that they've visited (5,000 x 16 airfare + hotel + travel). All the interviews were soon cubbyholed in the board rooms on the first floor of the placement office and off started the mating ritual: people would go into rooms and emerge 45-50 minutes later after having an intense session. Here's how my interviews went.
Interview 1: 45 minutes
Q1. Given a graph with all vertices of even degree, how will you print the Euler's tour of the graph?
A: Fleury's Algorithm
Q2. Given a set of overlapping intervals of the form (start, end), each of which is associated with a property (say S), print a sequence of disjoint intervals with all properties current valid in that interval.
eg. (1, 3, S0) (2, 3, S1) (2, 4, S2) yields (1,2, S0), (2, 3, S0 + S1 + S2), (3,4,S2) as the disjoint intervals.
Also, code a solution to the above problem.
Q3. Design a site similar to tinyurl.com
Q4. Now scale it to higher loads.
Q5. Given that you now have 2 geographically separated datacenters and a request comes in for a url that's not present in your current datacentre, how will you handle it?
Q6. Various questions about failovers, replication, node failures, load balancing, redirects etc.
Interview 2: 45 minutes - This one went horribly.
Q1. Given a 2^n x 2^n chessboard and an infinite number of L shaped tiles (of size 2x2) which may be rotated and placed, is it possible to tile the entire chessboard leaving just a single gap?
A: Yes. You can prove this by induction. Unfortunately, the solution didn't strike during the interview.
Q2. Delete a node from a Binary search tree.
A: Standard data structures question
Interview 3: 45 minutes
Q1. Print the elements of a matrix in spiral order (outside to inside). Make your code as efficient as possible. (an icebreaker question)
Q2. Given 2 numbers in base 10 with digits given in MSB to LSB order in a singly linked list, add the two numbers and return the result as a linked list in MSB to LSB order. Do this in < 4n operations on the given linked lists (including traversals) (this constraint was stated somewhat vaguely). Code up the solution. The more efficient the better. I gave multiple solutions to this problem (the first few methods had 4n operations).
The primary challenge in the interviews was the tight time limits within which we had to figure out solutions and code them up. Finally, I guess there was some CV evaluation from Mountain View and the offer letters materialized after a sleepless night for us. Congratulations Naman, Parth, Tanmay and Gunjan for also clearing Google. You guys rock!
Other interesting questions:
Q1. Given a credit card number with a certain number of fixed digits and a certain number of digit placeholders, find the number of solutions such that the entire number yields a remainder of 3 when divided by 13. Use properties of modulus.
A: This question has a DP that can be solved in O(m n) where n is the number of digit placeholders and m = 13. Brute force is O(10^n). Quite a tough question.
Q2. Given numbers of the form 2^i x 3^j x 5^k x 7^l - generate the numbers in ascending order of the sequence given i,j,k,l >= 0 and are integers. Give an efficient solution to this problem.
Best of luck to those that are still giving Google Interviews this season! :)
The visit was useful. Content was really very informative. From www.expressgiftbasketsusa.com.
ReplyDeleteThe visit was useful. Content was really very informative. From www.giftflowersusa.com/gift_hamper_to_usa.asp
ReplyDeleteThe visit was useful. Content was really very informative. From www.singaporeflowershop.com/Exclusive_Gifts.asp
ReplyDeleteDude can you help me with question no 15,(Given an sorted array, what is the complexity of finding weather a number is present n/2 times or not.)
ReplyDeletesince you have given O(1) as answer,it should be straight-forward..
what I thought was using binary search find location of the first number greater than given no and first number less. so O(2*log(n))
I also went through a copule of forums for it (geeksforgeeks sort of ) but no luck :(
Hi Rohit,
DeleteAs given array is already sorted, You just need to compare first element with middle element and middle element with last element.
If any of these two comparison results in true then you found your element which is present n/2 times. otherwise not.
Hope it help. :)
Sorry, My bad.
DeletePrevious comment was wrong !
Divye, Can you please tell me how to do it in O(1) ? I found a solution in O(log n).
Thanks.
Hi Divye,
ReplyDeleteThanks for your post. It is very informative ! I am not able to figure out a solution for the credit card problem. Also I dont understand why you chose m = 13. If you dont have a solution which you can email me, I would really appreciate a couple of quick pointers to help solve this DP problem. thanks !
-Neha
Hi Divye bro,
ReplyDeleteThanks for such a wonderful and informative post. I have only one question. I have been selected for M.tech CSE in IIT Madras. But I'm worried as my B.Tech CGPA is only 6.9/10. But you have mentioned that 7.0 was the eligibility cutoff for B.Tech. Does that B.Tech eligibility cutoff, apply only for students studying B.Tech at the time of interview, or even for M.Tech students.
P.S. What I'm trying to ask is that, for M.Tech students, will they see both B.Tech CGPA and M.Tech CGPA for eligibility. Or will they only see M.Tech CGPA?
This is really bothering me bro. You are one of my role models whom I'm trying to follow. So, please answer it bro.