Total there are five Technical Interviews followed by Management round.
So here are the questions.
Google Interview Round 1:
- What is the Space complexity of quick sort algorithm? how do find it?
Solution: Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
* in-place partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is
(recursively) sorted first, requiring at most O(logn) space. Then the
other partition is sorted using tail-recursion or iteration.
The
version of quicksort with in-place partitioning uses only constant
additional space before making any recursive call. However, if it has
made O(logn) nested recursive calls, it needs to store a constant
amount of information from each of them. Since the best case makes at
most O(logn) nested recursive calls, it uses O(logn) space. The worst
case makes O(n) nested recursive calls, and so needs O(n) space.
However,
if we consider sorting arbitrarily large lists, we have to keep in mind
that our variables like left and right can no longer be considered to
occupy constant space; it takes O(logn) bits to index into a list of n
items. Because we have variables like this in every stack frame, in
reality quicksort requires O(log2n) bits of space in the best and
average case and O(nlogn) space in the worst case. This isn't too
terrible, though, since if the list contains mostly distinct elements,
the list itself will also occupy O(nlogn) bits of space.
- What are dangling pointers?
Solution:
A dangling pointer is a pointer to storage that is no longer allocated.
Dangling pointers are nasty bugs because they seldom crash the program
until long after they have been created, which makes them hard to find.
Programs that create dangling pointers often appear to work on small
inputs, but are likely to fail on large or complex inputs.
- Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
Solution:The simple recurrence relation governing this problem is f(N)=f(N-1) +f(N-2)(why?),which is a fibonacci sequence.
Nth
state can be arrived directly by taking 2 step movement from N-2 or 1
step from N-1.Remember N-2 -> N-1 -> N is not a direct path from
N-2th state to Nth state.Hence the no of solutions is no of ways to
reach N-2th step and then directly taking a 2 jump step to N + no of
ways to reach N-1th step and then taking 1 step advance.
- You are given biased coin. Find unbiased decision out of it?
Solution:Throw
the biased coin twice.Classify it as true for HT and false for TH.Both
of these occur with probability=p*(1-p),hence unbiased. Ignore the
other 2 events namely HH and TT.
- On a empty
chessboard, a horse starts from a point( say location x,y) and it
starts moving randomly, but once it moves out of board, it cant come
inside. So what is the total probability that it stays within the board
after N steps
Google Interview Round 2:
- You
have 1 to N-1 array and 1 to N numbers, and one number is missing, you
need to find the missing the number. Now you have 1 to N-2 numbers, and
two numbers missing. Find them.
Solution:
The
question can be elucidated as follows.Given an array of size N-1
containing numbers less than N and with out any duplicates!! We knew
that there is a number missing from the array say K .Let S be the sum
of the elements of the array.
Sum of first N natural numbers=N*(N+1)/2 and S=N*(N+1)/2 - K.Now putting this other way around we get K=N*(N+1)/2 -S !! Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.
We solve this problem by solving 2 essential equations.
They are X+Y=N*(N+1)/2 -S---------->(1)
X*Y=N!/P-------------------(2) where S and P are the cumulative sum and product of the array entries.
- You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Solution:
The
problem of checking whether there is a cycle or not can be solved using
2 pointers one moving in increments of 1 and the other in increments of
2.If there is a cycle then these 2 pointers meet at some node say N1
inside the cycle otherwise the fast pointer reaches the end of the
list.This is a O(N) solution.
Now coming to the identification
of the node at which looping took place.After our identification of
cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow
pointer to count the no of nodes in the cycle.(After traversing the
whole cycle P1 and P2 shall again be at the same node).Let this size be
K.Now take one of the pointers to the head node and count the no of
nodes till N1.Let this number be X.Now use one of these pointers to
reverse the cycle starting from N1.Only the cycle gets reversed.Now
again traverse from head node to N1.Let the number of nodes this time
be Y.Let the no of nodes from head to the start node of the cycle be Z
Now
X+Y=2*Z+K .Hence solve for K and then having figured out the start node
N2 of the cycle.Now as the cycle is reversed having figured out this
start node its next node is the looping nodes so set the looping nodes
next pointer to NULL and reverse the list further till you reach N2.
- Questions on my project please be prepare well about your project
- How do you search for a word in a large database.
- How
do you build address bar in say gmail. i.e. if you press 'r' then you
get all email starting from 'r', and if you press 'ra' then you will
get emails starting from 'ra'.
Google Interview Round 3:
- You have given an array. Find the maximum and minimum numbers in less number of comparisons.
Solution:
only
3n/2 comparisons are necessary to find both the minimum and the
maximum. To do this, we maintain the minimum and maximum elements seen
thus far. Rather than processing each element of the input by comparing
it against the current minimum and maximum, however, at a cost of two
comparisons per element, we process elements in pairs. We compare pairs
of elements from the input first with each other, and then compare the
smaller to the current minimum and the larger to the current maximum,
at a cost of three comparisons for every two elements.
- You
have given an array from 1 to N and numbers also from 1 to N. But more
than one number is missing and some numbers have repeated more than
once. Find the algo with running time O(n).
Solution:All
the numbers are positive to start with.Now, For each A[i], Check the
sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a
repetition if it's negative.Finally all those entries i,for which A[i]
is negative are present and those i for which A[i] is positive are
absent.
Google Interview Round 4 :
- Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
Solution:
bool test(A,B,C)
{
i=j=k=0;
while(k < C.size())
{
if(i < A.size() && C[k]==A[i])
{i++,k++;
}
else if(j < B.size() && C[k]==B[j])
{
j++,k++;
}
else
return false
}
return (i == A.size() && j == B.size());
}
The
above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing
one in to a dilemma whether to accept the character from A or B.
- Given two sorted arrays A and B.
- Find the intersection of these arrays A and B.
Solution:The intersection can be found by using a variation of merge routine of the merge sort.
- If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?
Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.
Google Interview Round 5:
- If you get into Google, which products are you going to work on?
- What is TCP, UDP. what is reliability, unreliability, give examples of these?
Solution:
Click Here To Read About TCP
Click Here To Read About UDP
Click Here To Read About Reliability
- What is http protocol?
Solution:
Click Here To Read About HTTP
- How does Google search engine works?
- What is indexing, what is the input and output to it. how Google does that?
This was the interview i got from one of my friends.