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 .

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

### Comments (7) -

Add comment

biuquote

- Comment
- Preview

could you explain me the duality algorithm for calculating the maximum number of collinear points

We rectify it now.

the problem should be to find the zeros at the end.

also you should use modulo not pow. (at any multiple by 5 a zero will be added at the end)

My ans is

numlines = nC2

for each line

calculate slope

array.push(slope)

sort(slope array);

for each repetitive slope

find the line equation <-> subsitute the points there

if(equation is valid) countLine++;

can you let us know if you got into google after all this?

And if you have got into google, make sure no one at google knows you have shared your questions.

Thanks a lot for making this information available. I was just wondering if you ever had to take a technical questionnaire. Do you have any information regarding that? Also, could you provide some answers to the questions you posted? I appreciate a lot your sharing of this knowledge ^^.