Showing posts with label Google Jobs Interview Questions. Show all posts
Showing posts with label Google Jobs Interview Questions. Show all posts

Google latest Interview Questions For Fresher's, Google telephonic Interview


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.

Read more...

Questions at Google Job Interview - Solutions to Crazy - Google Interview


How many golf balls can fit in a school bus?

Solution:
The point of the question isn't to see how golf balls you think are in the bus, but to see what your deduction skills are like. Do you just make a random guess or try to cop out by saying a lot, or do you actually try to come up with a legitimate answer by going through a logical series of steps.


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?


Solution:
You simply jump out. As you are scaled down, the ratio of muscle mass to total mass remains the same. Potential energy is given by E = mgh. So, if E/m is unchanged (where E is the energy expended in expanding your leg muscles, and m is your mass), then h is unchanged. Mini-me jumps as high as me. This is the reason why grass-hoppers can jump about as high as people.


How much should you charge to wash all the windows in Seattle?

Solution:
As crazy as it might sound, questions like these demonstrate your ability to think through a complex problem with little or no information. They expect you to take an educated guess. Most of the time you can ask them questions like - how many buildings are there in Seattle.


How would you find out if a machine’s stack grows up or down in memory?

Solution:
Instantiate a local variable. Call another function with a local. Look at the address of that function and then compare. If the function's local is higher, the stack grows away from address location 0; if the function's local is lower, the stack grows towards address location 0.


Explain a database in three sentences to your eight-year-old nephew.

Solution:
A database is like a file cabinet. The files, or data, is stored in it and can be arranged in categories. But unlike an actual file cabinet, you can do a lot more cool stuff with a database like being able to make it accessible through the internet.


How many times a day does a clock’s hands overlap?


Solution:The Hour hand and Minute hand would be meeting exactly 11 times in 12 hours (Hour hand would have taken 1 clockwise round and Minute hand would have taken 12 clockwise rounds, so 12 - 1 = 11 rounds).

result:
First time hour and minute hands overlap will be 12 Hours / 11 = 01:05:27.27. So at this time only hour and minute hands would be overlapping and second hand will not be any near to them. Similarly for 2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th and 10th overlap of hour and minute hand the Second hand wont be any nearby. So all 3 hands (hour, minute and Second) overlap only 2 times i.e. (0:0:0 and 12:0:0).

Also we all know when we get our watches repaired, normally the repairman overlaps all the three hands to 12.

If we are considering that the second hand is not present, then the rest two overlaps 22 times in 24 hours.

There again is a catch, if we check the angles by which the hour hand and minute hand moves.

The second hand moves 6 degree in a second. In that time the minute hand will move 6/60 degrees. and the hour hand will move 6/(60*12) degrees. now taking these things in the considerations. if we check the positions of the hour and minute hand in terms of angle from the marker 12, for our first rendezvous time, i.e. 01:05:27.27 sec.
first thing that comes to my mind is that, there is fraction in the seconds. So that time can’t be measured. there will be no exact overlap. now lets calculate the angles:

1 hour 5 mins and 27 seconds = 3600 + 5*60 + 27 = 3927 seconds.

angle of hour hand = 3927 * 6/(60*12) = 32.725 degree.
angle of minute hand = 3927 * 6/60 = 392.7 degree
subtracting 360 degree from it we get - 32.7 degree.

So at 01:05:27 both hands don’t overlap. Now for 01:05:28 :
Angles : hour hand - 32.73333
minute hand - 32.8
so obviously they dont meet at 01:05:28 either.

So they overlap at 12:00 and 24:00 only. So the answer is 2 only.



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


Solution:Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther.

Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed.

During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements.

This is the best chance you have reaching point B if you don’t know if you can get there.


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?

Solution:
Let’s suppose there are
a set of attributes of each shirt you are interested in: e.g. sleeve length, color, buttons (no buttons, fully button, partially buttoned from collar to chest level).
Let’s say the closet is a simple wall closet with a single closet rod running the entire length of closet. On the left you put all the short sleeve shirts, and on the right the long sleeve shorts. You separate then long and short sleeve sides with a specially marked coat hanger. Then you separate each group into no buttonoed, partially buttoned, and fully button, using more specially marked hangers. Then each sub group is separated into colored and monochrome sub-sub-groups (specially marked hangers aren’t needed for separators unless you are color blind) Then each colored group is sorted left to right according to the color spectrum: ROYGBIV: red, orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is sorted left to right: white on the left, black on the right, and shades of grey in the middle, the darker greys on the right, the lighter on the left.


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?

Solution:1. There is only one cheat husband
- If it is so then 99 wives knew it before. So the cheated wife got the idea from queen that her husband is cheating. So she will kill him. Next morning every wife will know there is no cheat husbands anymore.


2. There are more than one cheat husbands


- In this case, all of the wives already had the idea prior to queen's information. Its just that the cheated wives knew the count which is one less than what the non-cheated wives' knew - thats all. i.e. if there were 2 cheat husbands then their wives knew the count is 1 and others knew its 2. So the queen just repeated the info saying "at least 1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife kills her husband.


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?
Solution:From pure probability,we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1


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)?


Solution:If the chance to see the car is 10 percent per minute, the first minute you have 10% chance, the second minute you have 10% of 90% = 9% (so total 19%), the third minute 10% of 81% (= 8,1%, total 27,1 %) ......
As the chance for 30 minutes is 95 percent, the chance for 1 minute is 9.5% and for 10 minute 63.1 %.


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!)

Solution:7.5 degrees (the hour hand is 1/4th of the way between 3 and 4, the angle measure of that is 360/12 = 30 degrees between hours / 4 = 7.5 degrees).


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?

Solution:1 and 2 cross, taking 2 minutes, 1 goes back carrying the flashlight total=3 minutes. 5 and 10 cross, taking 10 minutes totaltime now= 13 minutes, 2 goes back,total time now = 15 minutes. 1 and 2 cross again, taking 2 minutes making it 17 minutes.


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?

Solution:No.


How many piano tuners are there in the entire world?

Solution:1) At first list out all the piano manufacturing companies in the world.
2) Then look into their purchase records and find out the piano purchasers information.
3) i) If the purchase is made by an individual or a house hold then the piano is played at best case by all the people of the house.
ii) Else if the piano is purchased for school then list out the students that opted the piano course in their music curriculum.
iii) If the piano is purchased by a Church then count the no of major or minor events of the church and count the piano users.
sum up all the numbers to get more or less accurate piano users count.


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?

Solution:choose 6 balls and weigh 3 against 3
- if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one
- if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them:
- if they weigh the same, the remaining ball is the heavier one; otherwise you just found the heavier one by weighing the 2 chosen balls.


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


Solution:The highest ranked pirate gets 98 gold coins
---Two pirates get 1 gold coin each
---The other 2 pirates get nothing.

Read more...
Related Posts Plugin for WordPress, Blogger...

  © Blogger templates The Professional Template by Ourblogtemplates.com 2008

Back to TOP