Google interview in progress…
Interview questions from Google – sample below:
How many piano tuners are there in the entire world?
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?
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.)
I guess this is useful. It can find logical, clever, informed people – which is probably a good base of people to hire from.
November 9th, 2010 at 11:41 am
I was asked a question similar to the 8 balls, but it was 12 and 3 weighings. It took me a while to get it, but once I had that “ahah” moment, it all became clear. After the interview I went to dinner with a friend where we discussed optimum solutions for an arbitrary number of balls. That was a great day.
November 9th, 2010 at 12:50 pm
The 2 weighings solution works for 9 balls. I actually am about to interview someone and that question is high on my list.
November 9th, 2010 at 12:58 pm
Yes. 3^n balls require n weighings. It’s a power of 3s problem. My initial thought was binary search, but I soon realized that it wouldn’t be enough. My ahah moment was realizing I could learn about things I wasn’t weighing.
Another good one I saw was:
4 hikers are trying to cross a rope bridge in the dark. The bridge can support two at a time but it’s getting dark and they only have one light. Each of them cross at their own speeds: 1,2,5,10mins, and they have 17 minutes of light remaining. How do you get them all across in time?
November 9th, 2010 at 1:01 pm
Maybe Google should want the one who would take the flashlight and leave the others?
November 9th, 2010 at 1:03 pm
There is nothing in the problem which states that they need to have the light in hand to cross the bridge. The problem is in the assumption that they need to see their way.
November 9th, 2010 at 1:27 pm
And now I have a solution for a version of the problem which patches that verbal hole
November 9th, 2010 at 1:28 pm
They do need the light to cross. I’m sorry I didn’t specify that.
November 9th, 2010 at 3:02 pm
My algorithm:
Answer:
[1,2]->
<[2]
[5,10]->
<[1]
[1,2]->
2+2+10+1+2 = 17
November 11th, 2010 at 11:14 am
You are all geeks!!! If they’re stupid enough to be hiking when it’s dark and didn’t bring enough flashlights, get them all on the on the bridge and cut the rope bridge, they’re too stupid to let them breed.
November 11th, 2010 at 1:30 pm
Nerds!Nerds!Nerds!