Slashdot Mirror

Oh, I'm sorry, you're quite correct.
My mistake, I would retract my original comment had I the ability.

Yours was a good puzzle, and reminds me of the Pirates dividing loot puzzle.

This is just plain old fashioned wrong. It would work if the probability of k girls was 1/k, but in reality it's the probability of k-1 girls that's 1/k, because someone who has a boy first time out stops without a girl. The off-by-one error matters even in the infinite sum.

not true. check out the solution to this: http://www.techinterview.org/Puzzles/fog0000000026 .html

five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

(to be clear on what 50% means, 3 pirates must vote for the proposal when there are 5 for it to pass. 2 if there are 4. 2 if there are 3. etc... )

Solution

Google uses aptitude tests, which it has even placed in technical magazines, hoping some really big brains would tackle the hardest problems

Almost all hightech companies look for big brains. Typical questions would look like this:

five pirates have 100 gold coins. they have to divide up the loot. in order of seniority (suppose pirate 5 is most senior, pirate 1 is least senior), the most senior pirate proposes a distribution of the loot. they vote and if at least 50% accept the proposal, the loot is divided as proposed. otherwise the most senior pirate is executed, and they start over again with the next senior pirate. what solution does the most senior pirate propose? assume they are very intelligent and extremely greedy (and that they would prefer not to die).

The answer is in the no. 63 of techInterview. Don't feel depress when you couldn't come up with the right answer, and don't bother memorizing all those answers before going to interview. They probably wouldn't reuse any of them anyway. If you don't have extremely high IQ, you probably want to learn techniques to solve those problems.

As a matter of fact, questions as such are mostly problems in Game Theory(Yes, Game Theory as in the movie A Beautiful Mind). Pirates problem above is a typical game that can be solved by backward induction on an extended subgame. I've actually seen this question in a final examination of Game Theory in my prograduate Economics studies.

some more questions.

DO NOT make them solve brain-teasers on the spot, regardless of what joelonsoftware.com might say.

Huh? While Joel has a site with brain teasers (techinterview.org), he discourages using them.

From Joel's Guerilla Guide to Interviewing:

Finally, avoid brain teaser questions like the one where you have to arrange 6 equal length matches to make exactly 4 identical perfect triangles. If it's an "aha!" question, you don't get any information about "smart/get things done" by figuring out if they happen to make the mental leap or not.

You've got to use the right questions. As someone else has pointed out, there's a great web site called techinterview.org that has similar questions. They talk about something called the "aha factor". If something has a high aha factor, then you'll only get it if you've heard the question before. These aren't very useful as interview questions.

If something has a low aha factor, then it's a useful question even if they've heard it before. The idea is to watch the interviewee's reasoning process, not to make sure they get the right answer. When I interview people, I ask these types of questions. I find it an invaluable probe of their ability to reason and think logically.

One of my favourites is this:
"How many trailing zeroes are there on 100! (100! = 100x99x98x97x...x3x2x1)."

Try it. It's reasonably straightforward to get, but you have to show an understanding of factoring and multiplication to get it. The answer is on techinterview.org if you want to check yours.

Scott

for more tech interview questions and answers try http://www.techinterview.org/

Presumably one of the reasons you'd be building this library and gaining this knowledge is to get a job. One book that I think is especially helpful for that is Programming Interviews Exposed . Most of the book is made up of step by step examples of how to solve the kinds of problems that are presented in interviews. This is something you might not get from the other books that have been mentioned, because interview problems tend to be significantly different from those that you would encounter in classes or real programming.

Of course, I may be a little biased, since I'm one of the authors, but some other people seem to have found it pretty useful, too, so hopefully you'll consider it worth a look.

---

Can you get modded down "Self Promotion"?