Google Interview Questions By SEO2India

[SEO2India]

Hi all SEO2India Group Members
Here i m submit interview questation by Google when u face a google
interview u remember this things...

* Given a number, describe an algorithm to find the next number
which is prime.
* There are 8 stones which are similar except one which is heavier
than the others. To find it, you are given a pan balance. What is the
minimal number of weighing needed to find out the heaviest stone ?

Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If the pan is remains balanced, the heavier is in the remaining (2).
use pan again to find which is heavy from (2). (Total pan use 2)

If the pan does not remain balanced when weighing (3,3), pick the set
of stones that outweigh other. Divide it into (1,1,1). use pan to
weigh first two. It it remains balanced, the remaining stone is the
heavier, otherwise the one outweighing other is heavier(total pan use
2)

[These questions from 'Taher']

* Order the functions in order of their asymptotic performance

* 2^n
* n^Googol ( 10^100)
* n!
* n^n

Answer: n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n

* what is the best and worst performance time for a hash tree and
binary search tree?

Answer:
Best is O(c), worst is O(log n)

* Questions regarding a string Class

* What do you need when you instantiate a string ( i said a byte
array and possibly the length) ?
* What is the best and worst time for the operation 'equals'
* How do you spedup the 'equals' operation (i said used hash MD5
for example)
This still has some problem ( a hash can be the same for unequal
strings)
-> Use Boyer–Moore string search algorithm => O(n)

* Trade offs between a multi threaded and single threaded
implementation ?
* N threads .. n resources .. what protocol do you use to ensure
no deadlocks occur?
* There are a set of 'n' integers. Describe an algorithm to find
for each of all its subsets of n-1 integers the product of its
integers.

For example, let consider (6, 3, 1, 2). We need to find these
products :

*
o 6 * 3 * 1 = 18
o 6 * 3 * 2 = 36
o 3 * 1 * 2 = 6
o 6 * 1 * 2 = 12

last one is simple

int mul = 1;
for i = 1 to N
mul *=a[i];

for i= 1 to N
a[i] = mul/a[i];

(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use
dynamic programming to solve this.

Here's the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni ..
nj). If you had such a table, you could just output

for (int i = 1; i <= n; i++)
{

if (i == 1)
print x[2,n];
else if (i == n)
print x[1,n-1];
else
print x[1,i-1] * x[i+1,n];

}

To build the table, start along the diagonal (x[i,i] = ni). Then do
successive diagonals from previous ones (x[j,k] = x[j-1,k] * x[j,k
+1]).

* 1. Describe Sorting algorithms and their complexity - Quick
sort, Insertion Sort, Merge Sort
* 2. If you had a million integers how would you sort them and how
much memeory would that consume?

Binary tree - requires 1,000,000 integers x 4 bytes = 4 MB + left
pointer and right pointer = 12 MB
Insertion sort - can be done in under 4 MB

* 3.Describe an alogrithm to find out if an integer is a square?
e.g. 16 is, 15 isn't

a) simple answer - start at 2 and divide the integer by each
successive value. If it divides evenly before you reach half way then
it is.
b) complex answer after much leading - Do the bitwise AND of n and
(n-1). If it is zero then it is a square (I think this is wrong. This
actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to
be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2

C)

i=2;
while(!NO)
{

if((i*i)==Number)
{
NO;
return True;}
if((i*i)>Number)
{
NO;
return false;}
i++;
}

* 4. How would you determine if adwords was up and running and
serving contextual content ?

5428907816463810488188

Here are some questions I got on my first interview with Google
(slightly altered for NDA reasons).

* 1 Suppose you have an NxN matrix of positive and negative
integers. Write some code that finds the sub-matrix with the maximum
sum of its elements.

* 2 Write some code to reverse a string.

* 3 Implement division (without using the divide operator,
obviously).

* 4 Write some code to find all permutations of the letters in a
particular string.

* 5 You have to get from point A to point B. You don’t know if you
can get there. What would you do?

* 6 What method would you use to look up a word in a dictionary?

* 7 Imagine you have a closet full of shirts. It’s very hard to
find a shirt. So what can you

do to organize your shirts for easy retrieval?

* 8 You have eight balls all of the same size. 7 of them weigh the
same, and one of them weighs slightly more. How can you fine the ball
that is heavier by using a balance and only two weighings?

External Links

www.technical-interview. com Google Interview Questions

Phone interview

1. Describe the data structure that is used to manage memory. (stack)

2. whats the difference between local and global variables?

3. If you have 1 million integers, how would you sort them
efficiently? (modify a specific sorting algorithm to solve this)

4. In Java, what is the difference between static, final, and const.
(if you dont know java they will ask something similar for C or C++).

5. Talk about your class projects or work projects (pick something
easy)… then describe how you could make them more efficient (in terms
of algorithms).

In person interview

1. In Java, what is the difference between final, finally, and
finalize?

2. What is multithreaded programming? What is a deadlock?

3. Write a function (with helper functions if needed) called toExcel
that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and
returns a corresponding integer value (A=1,B=2,… AA=26..).

4. You have a stream of infinite queries (ie: real time Google search
queries that people are entering). Describe how you would go about
finding a good estimate of 1000 samples from this never ending set of
data and then write code for it.

5. Tree search algorithms. Write BFS and DFS code, explain run time
and space requirements. Modify the code to handle trees with weighted
edges and loops with BFS and DFS, make the code print out path to goal
state.

6. You are given a list of numbers. When you reach the end of the list
you will come back to the beginning of the list (a circular list).
Write the most efficient algorithm to find the minimum # in this list.
Find any given # in the list. The numbers in the list are always
increasing but you don’t know where the circular list begins, ie: 38,
40, 55, 89, 6, 13, 20, 23, 36.
Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/
Google_Interview_Questions"

Here is a bunch more:

1. How many golf balls can fit in a school bus? This is a Fermi
question.
2. You are shrunk to the height of a nickel and your mass is
proportionally reduced so as to maintain your original density. You
are then thrown into an empty glass blender. The blades will start
moving in 60 seconds. What do you do?
3. How much should you charge to wash all the windows in Seattle?
4. How would you find out if a machine’s stack grows up or down in
memory?
5. Explain a database in three sentences to your eight-year-old
nephew.
6. How many times a day does a clock’s hands overlap?
7. You have to get from point A to point B. You don’t know if you
can get there. What would you do?
8. Imagine you have a closet full of shirts. It’s very hard to find
a shirt. So what can you do to organize your shirts for easy
retrieval?
9. Every man in a village of 100 married couples has cheated on his
wife. Every wife in the village instantly knows when a man other than
her husband has cheated, but does not know when her own husband has.
The village has a law that does not allow for adultery. Any wife who
can prove that her husband is unfaithful must kill him that very day.
The women of the village would never disobey this law. One day, the
queen of the village visits and announces that at least one husband
has been unfaithful. What happens?
10. In a country in which people only want boys, every family
continues to have children until they have a boy. if they have a girl,
they have another child. if they have a boy, they stop. what is the
proportion of boys to girls in the country?
11. If the probability of observing a car in 30 minutes on a highway
is 0.95, what is the probability of observing a car in 10 minutes
(assuming constant default probability)?
12. If you look at a clock and the time is 3:15, what is the angle
between the hour and the minute hands? (The answer to this is not
zero!)
13. Four people need to cross a rickety rope bridge to get back to
their camp at night. Unfortunately, they only have one flashlight and
it only has enough light left for seventeen minutes. The bridge is too
dangerous to cross without a flashlight, and it’s only strong enough
to support two people at any given time. Each of the campers walks at
a different speed. One can cross the bridge in 1 minute, another in 2
minutes, the third in 5 minutes, and the slow poke takes 10 minutes to
cross. How do the campers make it across in 17 minutes?
14. You are at a party with a friend and 10 people are present
including you and the friend. your friend makes you a wager that for
every person you find that has the same birthday as you, you get $1;
for every person he finds that does not have the same birthday as you,
he gets $2. would you accept the wager?
15. How many piano tuners are there in the entire world?
16. You have eight balls all of the same size. 7 of them weigh the
same, and one of them weighs slightly more. How can you find the ball
that is heavier by using a balance and only two weighings?
17. You have five pirates, ranked from 5 to 1 in descending order.
The top pirate has the right to propose how 100 gold coins should be
divided among them. But the others get to vote on his plan, and if
fewer than half agree with him, he gets killed. How should he allocate
the gold in order to maximize his share but live to enjoy it? (Hint:
One pirate ends up with 98 percent of the gold.)