Classic math puzzles for job interviews | Hacker News Reader

Classic math puzzles for job interviews

scribd.com

32 pointspc18 comments

I don't see how the square could be partitioned, maybe I am reading it wrong? My informal counter proof by contradiction (decrypt with rot13.com):

fvapr gur cnegvgvba vf svavgr, gurer vf n fdhner Z jvgu gur fubegrfg fvqr. Abj pbafvqre gur fdhnerf nybat gur gbc fvqr bs gur havg fdhner. Gur fznyyrfg fdhner nzbat gurz unf n fvqr yratgu < 0.5, yrg'f pnyy vg F1. Abj pbafvqre ebj bs fdhnerf pbirevat gur obggbz fvqr bs F1. Gurer unf gb or n fznyyrfg fdhner nzbat gurz, jvgu yratgu < 0.5* fvqr_yratgu_bs(F1) = 0.25. Yrg gung fznyyrfg fdhner or F2. Abj pbafvqre gur ebj bs fdhnerf ng gur obggbz bs gung fdhner. Gurer unf gb or n fznyyrfg fdhner F3 nzbat gurz jvgu fvqr yratgu < 0.5*0.25 = cbjre(0.5,3). Naq fb ba - gurer vf nyjnlf n arkg ebj bs fdhnerf, nf gur fznyyrf fdhner va gur ebj pna abg gbhpu gur obggbz fvqr bs gur havg fdhner. Urapr V pna tb ba yvxr gung vasvavgryl, orpnhfr yvz cbj(0.5,a) = 0 riraghnyyl V'yy svaq n fdhner gung vf fznyyre guna Z, pbagenqvpgvba.

These problems are a lot of fun and in most cases there are interesting general lessons in their solutions, but the way the interview system seems to work is that every year there's a new book or sheet of puzzles that everyone memorizes and then pretends to have never seen before when asked during an interview.

Yeah, these puzzles are too unique and are in many cases well known problems/paradoxes that candidates are likely to know. Interviewers might be better served by asking a generic, LSAT-style logic game or a somewhat simple but time consuming math problem (maybe polynomial factorization).

#5 is impossible. Martin Gardner has a nice proof of this: observe that each domino must cover a black and a white square, no matter how you orient it. When you remove two opposite squares, you remove two squares of the same colour. Imagine you have put 30 of the dominoes on the board, then two squares remain uncovered. These squares must be the same colour (by the above rules), so there is no way the last domino can cover them both.

Ok, I fail and don't get the job, I get it... but where are the answers!

In what kind of job interview would asking any of these help you select an employee?

Professional puzzle solver job interview!

In all seriousness, if you start getting these questions during the interview, you should realize that these people don't know how to hire and you should move away.

Need answers? Email the PDF creator.

"Due to popular demand: I will write up and give out the solution to any problem in return for an interesting new problem. This will serve as a good growing force for the collection of problems."

http://pdos.csail.mit.edu/~petar/misc.html

Wow, I am surprised #13 is listed as a 1-star problem.

I was told a story about this problem by a professor while in class. Supposedly, Edgser Djisktra couldn't sleep one night due to jet lag. He was currently going through a phase in which was exercising the power of thought, practicing thought-exercises such as these without a pencil and paper. While in bed that night, awake due to jet lag, he solved this problem. The professor told us that none of us were smart enough to solve this problem. Hardly seems worthy of one star. :)

I haven't solved it yet, but it seems to be solvable by sheer diligence? Is there a faster solution? I think in an interview I would ask to write a computer program that solves it. Wait - I guess now I have to try that :-(

Edit: which programming language has good support for primes? I thought I saw one recently, but can't find it now.

Using the Goldbach Conjecture makes it easier.

start small and work your way up?

lets say 1>x>y and x+y<=4...

Update: OK, now I wrote the program, and in hindsight it was overkill. Just check the candidates for x+y starting from below, and the right solution appears pretty quickly (there are 24 candidates for x+y, but it is not necessary to check them all).

on the mouse one, could you not mix wines?

100 bottles, divide into 2 groups, feed mouse...

Separate poisoned bottles into 2 groups feed mouse..

basically 100,50,25,12,6,3,1 ... 6 mice needed.

There is only 1 day. Wouldn't you just separate the bottles evenly across all the mice?

That way you could serve 900 bottles. Can you serve more?

Hint: Look at the number of possible outcomes. In this case, each of the 10 mice can either live or die. That gives us 2^10 = 1024 possible outcomes. We can only encounter 1000 possible initial configurations of bottles. Is there a way to set it up so that each of the 1000 possible outcomes maps to an initial configuration?

I figured it out by thinking what would happen if you only had 1 mouse (500 bottles can make it to the party), then looking at the problem again with 2 mice (there's a way to prove that 750 bottles are poison-free using only 2 mice), etc. all the way up to 10 mice.

You do the mice as binary and then read them like 0's and 1's if they die or don't die

Reply on news.ycombinator.com