google and microsoft interview questions and solutions

1. You have to get from point A to point B. You don’t know if you can get there. What would you do?
The two most common ways to tackle a problem like this are usingDepth-First Search (DFS), and Breadth-First Search (BFS). In theexample above, you drive and drive around while you hope to find thedestination. Have you reached a deadend? Turn around and go back towhere you came from. It might not be the shortest way, but if you triedevery possible road, you would know that you can’t get to China fromNew York. Understanding this leads you to more exotic things like A*Search, and it’s a fundamental exploring algorithm. Too many things canbe reduced into a graph, and knowing the best way to search a graphwill come in handy. DFS is basically a stack-based implementation,while BFS is a queue-based implementation, each with its own strengthsand weaknesses..
2.Imagine you have a closet full of shirts. It’s very hard to find ashirt. So what can you do to organize your shirts for easy retrieval?
Hash it. Take every shirt, and put it in a different drawer dependingon the color of the shirt. Whenever you want a shirt, all you have todo is simply open the drawer with the corresponding color. That’shashing in a nutshell.Conceptually easy, if only because most classeshop over this with idealizations. The legendary Udi Manber was fond ofsaying, “hashing, hashing, hashing”. Hashing is hard, but don’t beafraid to use it. Imagine you have a closet full of shirts. It’s veryhard to find a shirt. So what can you do? Of course, you might (andlikely do) have more than one shirt of a given color. That is hashcollision, and there are tons of research papers in the world on thetopic, so know that they exist.
3.What method would you use to look up a name in a dictionary?
Do you remember that game 20 questions? You have to ask 20 questions toguess a word. The way to cheat is to narrow it down by half every time.The English dictionary has about 500,000 words, meaning you would stillhave queries to spare.
Yes, it would be boring, but it would go something like this:
Does your word come before the word “marry”? Yes
Does your word come before the word “gerrymander”? You get the point.
Assuming you already know you have to sort, you can binary search at O(log_2 N). For this, say, a trillion, is less than 50.
But its application doesn’t stop there, as it -as well as its cousinternary search- can help you solve numerical equations (this isactually called bisection). For example, you want to find the cube rootof N (N^(1/3)), but don’t have any sort of library ready. Easysolution? Binary search! You know x=y^3, so “guess” a value for x, andgo from there!
4.Every man in a village of 100 married couples has cheated on hiswife. Every wife in the village instantly knows when a man other thanher 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 whocan prove that her husband is unfaithful must kill him that very day.The women of the village would never disobey this law. One day, thequeen of the village visits and annoces that at least one husband hasbenn unfaithful. What happens?
Nothing happens. The queen does not tell the wives anything they don’talready know. They know that the other husbands are cheating, so it isnot news to them.
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 isheavier by using a balance and only two weighings?
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
6.How do you cut a rectangular cake into two equal pieces when someonehas already taken a rectangular piece from it? The removed piece an beany size or at any place in the cake. You are only allowed one straightcut.
Slice the cake half-way through the depth of the cake (look through theside of the cake). This way no matter what size the slice removed is orwhere it is removed, you will still have two equal pieces
7.How many piano tuners are there in the entire world?
This question takes some basic knowledge about the population of theunited states and the world…not really about piano tuners.First thinkabout how many pianos there are and how often they are used. Pianos aretypically owned by middle to upper class households, and are also foundschools, churches, hotels, etc.
The US population is approx 300 million. Assuming that each householdhas 3 people in it, that leaves 100 mil lion households. Of those, 50million are in the middle to upper class and may have pianos. Of those50 million households, you can think that no more than 10 percent havepianos. (That is probably high…it may be more like 2-3%). Anycase, thatleaves us with approximately 5 million households with pianos.Now youneed to think about how many piano tuners it takes to maintain thosepianos. I would say a typical piano tuner could tune approx 20 pianos aweek (2 hours each), and given a full year, that is approximately 1000pianos.
Now, how often do pianos need to be tuned? Once a year maybe? If thatis the case, then there would be 1 piano tuner for every 1000 pianos.That mean approx 5000 piano tuners in the US.
Now think about the rest of the world, it’s population, and it’swealth. I would guess that the US has 1/3 of the world’s pianos.Therefore, I would guess the total number of piano tuners in the worldis approximately 15000.
8. What gives you joy?
Concatinating the letters ‘j’, ‘o’, and ‘y’, will give you the word joy.
9.Mike has $20 more than Todd. How much does each have given thatcombined they have $21 between them. You can’t use fractions in theanswer. (Hint: This is a trick question, pay close attention to thecondition)
Mike has $20, Todd initially has $21. Todd keeps all his money on thetable between them. Hence, now Todd has nothing, Mike has $20 more thanTodd, and they have $21 between them i.e on the table between them.
10.How many times a day a clock’s hands overlap?
In any circular motion, if the ratio between 2 fellow is n:1 then foreach lap of the slower fellow, faster fellow overlaps him n times,except for the last lap of the slower fellow, where the number ofcrossings are n-1. (The race just finishes before the n th cross.
slower fellow : hour hand (short)
faster fellow : minuite hand (long)
n = 12
Total laps for hour hand = 2
total overlaps = 12+11 = 23.
11.How many times a day a clock’s hands overlap?
In any circular motion, if the ratio between 2 fellow is n:1 then foreach lap of the slower fellow, faster fellow overlaps him n times,except for the last lap of the slower fellow, where the number ofcrossings are n-1. (The race just finishes before the n th cross.
slower fellow : hour hand (short)
faster fellow : minuite hand (long)
n = 12
Total laps for hour hand = 2
total overlaps = 12+11 = 23.
12.If you look at a clock and the time is 3:15, what is the anglebetween the hour and the minute hands? ( The answer to this is notzero!)
The time is 3:15, i.e. 25% of the time between 3 and 4 has passed. Thehour-hand should, by simple mechanical logic, have moved 25% of itstotal distance between 3 and 4.
The total angle the hand covers is360%, so the angle covered between 3 and 4 should be360/12 = 30 degrees.
The minute hand is smack on 3, and the hour hand is a quarter of 30degrees further on. The angle made between them is thus 30*1/4 = 7.5degrees.