Feynman or not, it's entertaining to anyone who has waded through several hours of contrived interview questions that supposedly relate to programming ability, and that always have a "right" answer.
I had a four hour long interview for a systems programming/administration position where plebeian admins were allowed to grill me for about 25% of the time, asking me to whiteboard viable algorithms for cute little problems they concocted. All of my solutions would have functioned flawlessly and would have met all of the stated requirements, but they didn't involve the same thought processes that the interviewers had used. I "failed" but in the end, I won. I would not have fit in there anyway.
As much as they're interviewing you, you're interviewing them as well. If you're a smart guy, you hopefully have enough prospects that if you don't want to work with pedantic nitwits, you don't have to.
I was interviewing them as well, but I was 4 months unemployed with a disabled wife that couldn't work but whose disability claim was in limbo. I might have actually taken the job had I been offered one, sadly.
Fortunately, all's well that ends well. An old headhunter I'd used in the past tossed my info along (for FREE!) to my current boss. After talking to me on the phone, he gave me the old "We don't have a position open, but I'll call you if something opens up" line. I wrote it off, but he worked to get a position opened up for me and I'm genuinely doing what I love to do for a living these days. It involves Information Security, physical security/surveillance and general-purpose IT work (Sysadmin, programming and networking). I'm basically in geek heaven. It's also 6 miles from home, giving me the perfect excuse to ride my bike to work every day, rain or shine.
No. In my case, I worked for the headhunter as a consultant to a company that eventually hired me. The agency takes a percentage of the first year's salary in many of these situations. That said, I had really good luck with this agency and the recruiter himself personally. Many are scum-bags. If you find a good one, keep 'em on speed dial. You never know when you or a friend will want some help finding work.
I had a similar experience, asked to design a sudoku solver.
Coming from an AI background, I coded up an algorithm for state-space search.
They were expecting me to approach it as a person would, reasoning about how you rule out certain numbers (the constraint propagation), which is a second-order consideration for a game the size of sudoku.
I felt pretty smug when Peter Norvig shortly thereafter put up a blog post that essentially mirrored my solution.
Nothing really clever though - he only applies the two most basic sudoku strategies:
If a square has only one possible value, eliminate it from the square's peers.
If a unit has only one possible place for a value, then put the value there.
And then he notes that those simple strategies combined with search yields very reasonable run times.
Actually, for 9x9 Sudoku doing any more advanced propagation is pointless, since it will slow down the time to find the solution (assuming a reasonably fast search process). If one wants to solve 9x9 Sudokus without search, full propagation combined with shaving (hypothetical reasoning: if I assigned this square this value, woould it lead to an inconsistency) suffices as far as is known currently (no proof, just experiments, http://www.4c.ucc.ie/~hsimonis/sudoku.pdf).
For 16x16, it is more of a toss-up if one should use more advanced propagation. The solve-times are still so low though, that it doesn't really matter (tens of milliseconds). For 25x25 it starts to get interesting. In my experience, full propagation on lines, rows, and regions is needed, but more than that slows it down. Without a good heuristic (some learning process, prefferably coupled with randomized restarts), the solve-time easily goes up into hours. Wih a good heuristic, minutes seems to be a reasonable time-span to hope for.
It might not be that clever, but it is able to considerably reduce the running time of the algorithm (even if the speedup in a 9x9 puzzle is not perceived).
In fact, if you ask people not from a CS background to explain the steps they would take to solve a puzzle, they probably wouldn't be able to think of a DFS, but they would state that they should rule out from each cell the numbers already present in its respective column, line and block. And for a Sudoku solver I don't think you really need more constraint propagation than that.
Anyway, I think you approached the problem the right away, I just think that you were so close to succeed in that test and it wasn't something that difficult to add to your solution.
EDIT: wrote the above before your edit. It's still appropriate though.
