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?
Answer, from reader Olivier Coudert: The cheating husband problem is a classic recursion pb. Once all the wives know there are at least 1 cheating husband, we can understand the process recursively. Let's assume that there is only 1 cheating husband. Then his wife doesn't see anybody cheating, so she knows he cheats, and she will kill him that very day. If there are 2 cheating husband, their wives know of one cheating husband, and must wait one day before concluding that their own husbands cheat (since no husband got killed the day of the announcement). So with 100 cheating husbands, all life is good until 99 days later, when the 100 wives wives kill their unfaithful husband all on the same day. Job: Product Manager. Photo: symmetry_mind
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)?
Reader ru offers this answer: The trick here is that .95 is the probability for 1 or more cars, not the probability of seeing just one car. The prob. of NO cars in 30 minutes is 0.05, so the prob of no cars in 10 minutes is the cube root of that, so the prob of seeing a car in 10 minutes is one minus *that*, or ~63% Job: Product Manager
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?
Answer, from an anonymous reader: 1 and 2 across (2 minutes); 1 goes back (3 minutes); 5 and 10 go across (13 minutes); 2 goes back (15 minutes); 1 and 2 cross (17 minutes) - and everyone safe and sound. Job: Product Manager. Photo: Jule_Berlin
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?
Answer: Ignoring seasonal upticks in births, there's about 1/365 probability that any other person has the same birthday as you and 364/365 chance that any other random person does not. Do not take this bet. Job: Product Manager
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!)
Answer, from reader Matt Beauchamp: 7.5 degrees. Every minute on the clock represents 6 degrees (360 degrees/60 minutes). Every hour, the hour hand moves from one number to the next (in this case, it is moving from 3 to 4) which represents 30 degrees. Since it is exactly 1/4 past the hour, the hour hand is 1/4 of the way into its 30-degree trip or 1/4 or 30 degrees....which is 7.5 degrees. Job: Product Manager
What is the probability of breaking a stick into 3 pieces and forming a triangle? Since this question doesn't say the sticks must intersect at their tips to form the triangle, the answer has to be 100%. Any three sticks of any size can make a triangle. Job: Product Manager. Photo: markhillary
There's a latency problem in South Africa. Diagnose it. This is obviously an extremely vague question, and there isn't really one correct answer. A good answer is one in which the interviewee demonstrates familiarity with the term "latency" and enough imagination to come up with an interesting problem with an interesting solution. Job: Product Manager Photo: warrenski
How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
Answer, from reader Denis: Three. Take any two of the points. Draw a line that is parallel to the line segment made by those two points and halfway between that line segment and the third point. Repeat for every combination of two points. Job: Software Engineer. Photo: Caveman 92223
What's 2 to the power of 64?
1.84467441 × 1019 This is a pretty easy answer to figure out when you're not sitting in an interview with no calculator around. Job: Software Engineer.
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? There's no one answer to this. The interviewer wants to test the interviewee's imagination and creativity with problem solving. We feel like reader "Dude" might impress a Google interview with this answer: Organize them according to types of clothes like a HASH and then organize each type into a 2-3-4-Tree or RedBlack Tree. Job: Software Engineer. Photo: Brymo
You are given a game of Tic Tac Toe…You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game। So your data structure should consider this condition also.
Answer, from reader Dude: The data structure that is required is a two character dimensional array. Call the function to check the 6 conditions if there are any winners, the 6th condition is to see if there are any more spaces left. If there is a winner the characters X or O are associated with the players, in this case you need a flag. If there is a winner return the value to the calling function to end the game. If not the run the game. Job: Software Engineer Photo: frozenchipmunk
How long it would take to sort 1 trillion numbers? Come up with a good estimate. Here's another question without one answer. The idea is to test the interviewee's creativity.
We like the simple answer two readers came up with: Merge Sort for sorting. O(1,000,000,000,000 Log 1,000,000,000,000) - Average Case Scenario; O(1,000,000,000,000 Log 1,000,000,000,000) - Worst Case Scenario. I'd guess you can do 1 billion operations per second, thus 3000 seconds. Job: Software Engineer
Design an algorithm to play a game of Frogger and then code the solution…
The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road. Here's the only answer we found for this one, from site Glassdoor.com: "One approach is to write a recursive algorithm that determines when to "wait" or to "jump" to the next lane, depending if there is an approaching obstacle in the next lane." Job: Software Engineer
How many resumes does Google receive each year for software engineering?
This is another question that's about testing the job candidate's ability to frame the problem in a simple way and then creatively solve it. Our answer: A candiate for Quantitative Compensation Analyst should know that Google hired about 3,400 people in 2008. Figure 75%, or 2,550, of those hired were engineers and that, like Harvard, Google only accepted 3% of those who applied. 2,550 is 3% of 85,000. Job: Quantitative Compensation Analyst
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.
Here's our favorite answer, from reader "dude": Create temporary pointer and start from the root. (Most of the time circular lists have a front and back pointers.) Check if front is larger or if back is larger. If front is larger then you know you are at the end of the list and at the front of the list. If front is larger then traverse the opposite direction and compare numbers. If there is no root or a pointer pointing to any part of the list then your data is lost in memory. Job: Quantitative Compensation Analyst