google and microsoft interview questions and solutions

(More questions and solutions are at : " target="_blank">http://www.chinaworks.cn/postdetail.php?post_id=2577  and http://www.chinaworks.cn/postdetail.php?post_id=2578 target="_blank">http://www.chinaworks.cn/postdetail.php?post_id=2578


http://www.chinaworks.cn/postdetail.php?post_id=2577

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 using Depth-First Search (DFS), and Breadth-First Search (BFS). In the example above, you drive and drive around while you hope to find the destination. Have you reached a deadend? Turn around and go back to where you came from. It might not be the shortest way, but if you tried every possible road, you would know that you can’t get to China from New York. Understanding this leads you to more exotic things like A* Search, and it’s a fundamental exploring algorithm. Too many things can be reduced into a graph, and knowing the best way to search a graph will come in handy. DFS is basically a stack-based implementation, while BFS is a queue-based implementation, each with its own strengths and weaknesses..

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

Hash it. Take every shirt, and put it in a different drawer depending on the color of the shirt. Whenever you want a shirt, all you have to do is simply open the drawer with the corresponding color. That’s hashing in a nutshell.Conceptually easy, if only because most classes hop over this with idealizations. The legendary Udi Manber was fond of saying, “hashing, hashing, hashing”. Hashing is hard, but don’t be afraid to use it. Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do? Of course, you might (and likely do) have more than one shirt of a given color. That is hash collision, and there are tons of research papers in the world on the topic, 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 to guess 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 still have 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 cousin ternary search- can help you solve numerical equations (this is actually called bisection). For example, you want to find the cube root of N (N^(1/3)), but don’t have any sort of library ready. Easy solution? Binary search! You know x=y^3, so “guess” a value for x, and go from there!

4.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 annoces that at least one husband has benn unfaithful. What happens?

Nothing happens. The queen does not tell the wives anything they don’t already know. They know that the other husbands are cheating, so it is not 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 is heavier 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 someone has already taken a rectangular piece from it? The removed piece an be any size or at any place in the cake. You are only allowed one straight cut.

Slice the cake half-way through the depth of the cake (look through the side of the cake). This way no matter what size the slice removed is or where it is removed, you will still have two equal pieces