Good challenge.
BTW, you don't need 18 rounds, you need 17 because there's no need to check the floor 99 after you've checked 98.
However, I believe you missed one important issue. In order for the solution to be efficient, it's not important how many rounds you do but how many floors you have to walk up and down. For example, if the right floor is 99, with your solution you'd have to do 17 rounds but walk up and down 1215 floors. With my solution, if I used both marbles (drop first, go up 3 floors, drop second, go down to pick them up), I'd do 18 rounds but walk up and down 983 floors.
The difference gets more obvious in the lower floors. For example, if the floor 9 was the right one, you'd do 8 rounds and walk 45 floors, while I'd do just 3 rounds and walk 23 floors, etc.
Re:I had an interview with Google a few weeks ago
on
Want To Work At Google?
·
· Score: 2, Insightful
Few years ago, this type of interviewing would seem pointless to me, as well. However, since then, I have become a team leader at my company and had several opportunities to interview candidates for positions in our development team. Managing developers has taught me that technical knowledge and years of experience in programming language X on platform Y, although important, is secondary to one simple property of a human individual: intelligence. I know it sounds unfair but I can say in all honesty: I don't worry too much if an experienced developer never coded in Ruby. He'll learn it in 3 days! What I worry about is whether his poor logic will cause our applications to run slowly or our projects to run late. That's what questions like these help me figure out at an interview.
BTW, the first question is interesting. I'd start by dropping one marble from the first floor, moving up 3 floors at a time, dropping the same marble and keeping one in reserve. Therefore, if a drop from the floor n was successful and a drop from the floor n+3 wasn't, I'd try the floor n+2 with the second marble. If it doesn't break, n+2 is the answer. If it does, it's n+1.
Slashdot Mirror
Good challenge. BTW, you don't need 18 rounds, you need 17 because there's no need to check the floor 99 after you've checked 98. However, I believe you missed one important issue. In order for the solution to be efficient, it's not important how many rounds you do but how many floors you have to walk up and down. For example, if the right floor is 99, with your solution you'd have to do 17 rounds but walk up and down 1215 floors. With my solution, if I used both marbles (drop first, go up 3 floors, drop second, go down to pick them up), I'd do 18 rounds but walk up and down 983 floors. The difference gets more obvious in the lower floors. For example, if the floor 9 was the right one, you'd do 8 rounds and walk 45 floors, while I'd do just 3 rounds and walk 23 floors, etc.
Few years ago, this type of interviewing would seem pointless to me, as well. However, since then, I have become a team leader at my company and had several opportunities to interview candidates for positions in our development team. Managing developers has taught me that technical knowledge and years of experience in programming language X on platform Y, although important, is secondary to one simple property of a human individual: intelligence. I know it sounds unfair but I can say in all honesty: I don't worry too much if an experienced developer never coded in Ruby. He'll learn it in 3 days! What I worry about is whether his poor logic will cause our applications to run slowly or our projects to run late. That's what questions like these help me figure out at an interview.
BTW, the first question is interesting. I'd start by dropping one marble from the first floor, moving up 3 floors at a time, dropping the same marble and keeping one in reserve. Therefore, if a drop from the floor n was successful and a drop from the floor n+3 wasn't, I'd try the floor n+2 with the second marble. If it doesn't break, n+2 is the answer. If it does, it's n+1.