Tags: answers, technical, management |
Posted by Admin on
8/31/2008 12:42 PM |
Comments (0)

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.
Tags: answers, technical, management, phone interview |
Posted by Admin on
11/13/2007 1:08 PM |
Comments (7)

Google telephonic Interview
Asked
about my project. Prepare well to answer any type of questions that may
arise in your project.They will just ask to explain about any one of
the projects listed in your resume.
In a plane, n points
are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now given
these n points.Find the maximum number of collinear points.
Solution:
The
duality algorithm would work. Find the point of intersection with
maximum no of lines incident on it in the dual plane. It works in
O(n^2).
Write the code for finding the min of n number.
I gave:
for(i=0;i<n;i++)
{
if( a[i]<min )
{
min = a[i] ---- eq(i)
}
}
Given that n numbers are from random sampling how many times (probability) does the line (i) be executed
Solution:
min=a[0];
for(i=1;i<n;i++)
{
if( a[i]<min )
{
min = a[i]; -------eq(i)
}
}
Once
the variable min is initialized,the probability of a[i] < min is
1/2. So the expected number of occurances of equation i is (n-1)/2 .
Google Interview Round 2:
What is Bottom up parsing and what is top down parsing?
Solution:
Bottom-up
parsing is a strategy for analyzing unknown data relationships that
attempts to identify the most fundamental units first, and then to
infer higher-order structures from them. It attempts to build trees
upward toward the start symbol. It occurs in the analysis of both
natural languages and computer languages.
Top-down
parsing is a strategy of analyzing unknown data relationships by
hypothesizing general parse tree structures and then considering
whether the known fundamental structures are compatible with the
hypothesis. It occurs in the analysis of both natural languages and
computer languages. Please refer to these links for much better
information.
http://en.wikipedia.org/wiki/Bottom-up_parsing
http://en.wikipedia.org/wiki/Top-down_parsing
What is a symbol table?
Solution:
In
computer science, a symbol table is a data structure used by a language
translator such as a compiler or interpreter, where each identifier in
a program's source code is associated with information relating to its
declaration or appearance in the source, such as its type, scope level
and sometimes its location.
Check out
http://en.wikipedia.org/wiki/Symbol_table
There
is a portal with two billion users registered. If you store all the 2
billion users in a conventional databases it will take more time to
retrieve the data about a particular user when that user tries to
login. How do you handle this situation to make sure that the user gets
the response quickly.
Solution:
Every row has a primary key. Suppose the primary key for this
particular database is the name of the user then we can sort the names based
on alphabets and do secondary indexing based on the starting alphabet . If
the data is uniformly distributed we can go for multilevel indexing or
hashing.Similarly if we have a registration number as the primary key then
we can sort the table based on registration number and then do indexing
either secondary level or multilevel or apply hashing techniques based on
the distribution of data. Many efficient algorithms are available for
indexing and hashing.
There
are 8 identical balls. One of them is defective. It could be either
heavier of lighter. Given a common balance how do you find the
defective ball in least number of weighings.
Solution:
Weigh 3 balls against 3 others.
Case A:
If, on the first weighing, the balls balance, then the defective is
among the 2 remaining balls and can be determined using 2 weighings
making it a total of 3.
Case B:
Step1: If, on the first weighing, the balls don't balance.
If the balls do not balance on the first weighing, we know that the odd
ball is one of the 6 balls that was weighed. We also know that the
group of 2 unweighed balls are normal, and that one of the sides, let's
say Side A, is heavier than the other (although we don't know whether
the odd ball is heavy or light).
Step 2 :
Take 2 balls from the unweighed group and use them to replace 2 balls
on Side A (the heavy side). Take the 2 balls from Side A and use them
to replace 2 balls on Side B (which are removed from the scale).
I. If the scale balances, we know that one of the 2 balls removed from
the scale was the odd one. In this case, we know that the ball is also
light. We can proceed with the third weighing amd determine the lighter
of the 2 balls ,hance the defective.
II. If the scale tilts to
the other side, so that Side B is now the heavy side, we know that one
of the three balls moved from Side A to Side B is the odd ball, and
that it is heavy. We proceed with the third weighing and determine the
heavier one ,the defective.
III. If the scale remains the
same, we know that one of the two balls on the scale that was not
shifted in our second weighing is the odd ball. We also know that the
unmoved ball from Side A is heavier than the unmoved ball on Side B
(though we don't know whether the odd ball is heavy or light).
Step 3 (for Case B):
Weigh the ball from Side A against a normal ball. If the scale
balances, the ball from Side B is the odd one, and is light. If the
scale does not balance, the ball from Side A is the odd one, and is
heavy.
You have all the English words with
you. you would like to manage a dictionary so that you can look up when
ever you have doubt. Which data structure would you like to use and why?
Solution:
Dozens
of different data structures have been proposed for implementing
dictionaries including hash tables, skip lists, and balanced/unbalanced
binary search trees -- so choosing the right one can be tricky.
Depending on the application, it is also a decision that can
significantly impact performance. In practice, it is more important to
avoid using a bad data structure than to identify the single best
option available.As the frequency of look ups for a word is also
important,weighted binary search tree with weights in proportion to the
frequency of lookups and determining the depth, can be effective.
Asked me about all the details of hash table and heaps.
Write code for finding number of zeros in n!
Solution:
A
zero in n! typically occurs when a multiple of 5 gets multiplied to an
even number.We use this simple yet effective information to solve this
problem.In the first n natural numbers,those divisible by 5 are always
less than the no of even numbers.So it all boils down to the power of 5
in the prime factorization of n! .
This simple formula works for finding it floor(n/5)+floor(n/25)+floor(n/125)+......
function zeros(int n)
{
int count=0,k=5;
while(n>=k)
{
count+=n/k;
k*=5;
}
return count;
}
this count is the number of o's in n!.
Google Interview Round 3 :
Write
C++ class for the game Connect Four. [Connect Four (also known as Plot
Four, Four In A Row, and Four In A Line) is a two-player board game in
which the players take turns in dropping discs into a seven column grid
with the objective of getting four of one's own discs in a line.]
Given a stack and an input string of 1234.At any point you can do anyone of the follow
i. take the next input symbol and Enque.
ii. you can pop as many as you can. When ever you
pop an element it will be printed
(you cannot pop from an empty stack)
How many such permutations are possible on an input of size N?
Solution:
It is Nth catalan number.For a detailed solution look at question5 of Stacks and Queues
Give an example of one permutation that this data structure cannot generate.
For Example:
1234 is input.
First push all 1,2,3,4 on to stack and pop all.
output will be 4321.
It means that this data structure can generate 4321.
Solution:
3124
for a detailed solution please look at question7 of the post
Stacks and Queues
Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque.
Input: 12345
Data Structure: Deque ( Doubly Que )
Note: Deque is a data structure into which you can do enque
and deque from both sides.Some thing like this
__________________________________
enque ---> <----enque dequeue <---- ----->dequeue
__________________________________
Solution:
It
is N!. Guess why?(no constraints).Convince yourself by proving that
every permutation can be generated by a set of valid operations.This
prove can be using the principle of strong mathematical induction.So
for this specific input the answer is 120.
Classic
Egg Puzzle Problem You are given 2 eggs.You have access to a 100-store
building. Eggs can be very hard or very fragile means it may break if
dropped from the first floor or may not even break if dropped from 100
th floor.Both eggs are identical.You need to figure out the highest
floor of a 100-store building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to
break 2 eggs in the process.
Solution:
Let "d" be the number of drops required to find out the max floor.we need to get the value of d.
let's
say if we drop from height d then if it breaks then we have d-1 floors
to check for the second egg . so max of "d" drops, so first we will
drop it from height "d" if it doesn't break at a height "d" then we are
left with "d-1" drops,so lets drop it from d + 'd-2' + 1 height suppose
if it break there then you are left with 'd-2' drops.
and so on until that sum is less than 100, it's like a linear search,
in equations,
(1+(d-1))+ (1+(d-2)) + .... >= 100
here we need to find out d
from the above equation
d(d + 1)/2 >= 100
from above d is 14
Google Interview Round 4 :
Given n non overlapping intervals and an element. Find the interval into which this element falls.
Solution:
we can extend binary search to intervals.(Assuming the intervals are sorted)
consider interval [a,b].
if (a-x)(b-x) <=0
then x belongs to [a,b].
else
if x>a
element can be present only in the intervals to its right.
so select the middle interval among them to it's right
and repeat the procedure.
else
element can be present only in the intervals to its left.
so select the middle interval among them to it's left
and repeat the procedure.
The complexity of this problem is log(N) where N is the number of sorted non-overlapping intervals.
Worst
case is take all intervals one at a time and see whether the element
lies in the interval or not.It will take O(n). So please give a
solution that will do better than O(n).
Now given
that the n intervals are overlapping then how do you solve? The
interviewer was concentrating more on the complexities (running, memory
..)
Solution:
If the above intervals
are overlapping ,then they can be merged in O(N) and then the exact
intervals can be resolved later.Otherwise ,we can identify one correct
interval and then linear search on its left and right neighbourhood to
find the other solutions.
Write code for Random Sort?
Algorithm is explained:
Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.
Google Interview Round 5: This is Manager Round
Tell me an achievement that you have done in your non academics
Tell me about one of your project
Take a feature of C++ and tell me how you have implemented it in one of your project
By
taking one of your project as example tell me how you have taken care
of software engineering where you would have handled more data
There
is a routine already written to find the subtraction of two sets ( set
A - set B) . Write test cases for testing it.Tell me how do you test
the test cases you have written?
There is a printed
book. The page numbers are not printed. Now the printing of page
numbers is being done separately. If the total number of digits printed
is 1095 then how many pages does the book have?
Solution: Well people,this is too simple a question ..so do give it a try..(no malice,too simple).Any queries then do shoot a comment.