Reminds me of the bit in Cryptonomicon where Lawrence Waterhouse takes an intelligence test for the navy:
"They gave him an intelligence test. The first question on the math part had to do with boats on a river: Port Smith is 100 miles upstream of Port Jones. The river flows at 5 miles per hour. The boat goes through water at 10 miles per hour. How long does it take to go from Port Smith to Port Jones? How long to come back?
Lawrence immediately saw that it was a trick question. You would have to be some kind of idiot to make the facile assumption that the current would add or subtract 5 miles per hour to or from the speed of the boat. Clearly, 5 miles per hour was nothing more than the average speed. The current would be faster in the middle of the river and slower at the banks. More complicated variations could be expected at bends in the river. Basically it was a question of hydrodynamics, which could be tackled using certain well-known systems of differential equations. Lawrence dove into the problem, rapidly (or so he thought) covering both sides of ten sheets of paper with calculations. Along the way, he realized that one of his assumptions, in combination with the simplified Navier-Stokes equations, had led him into an exploration of a particularly interesting family of partial differential equations. Before he knew it, he had proved a new theorem. If that didn't prove his intelligence, what would?
Then the time bell rang and the papers were collected. Lawrence managed to hang onto his scratch paper. He took it back to his dorm, typed it up, and mailed it to one of the more approachable math professors at Princeton, who promptly arranged for it to be published in a Parisian mathematics journal.
Lawrence received two free, freshly printed copies of the journal a few months later, in San Diego, California, during mail call on board a large ship called the U.S.S. Nevada. The ship had a band, and the Navy had given Lawrence the job of playing the glockenspiel in it, because their testing procedures had proven that he was not intelligent enough to do anything else."
'Then there is the famous fly puzzle. Two bicyclists start twenty miles apart and head toward each other, each going at a steady rate of 10 m.p.h. At the same time a fly that travels at a steady 15 m.p.h. starts from the front wheel of the southbound bicycle and flies to the front wheel of the northbound one, then turns around and flies to the front wheel of the southbound one again, and continues in this manner till he is crushed between the two front wheels. Question: what total distance did the fly cover ? The slow way to find the answer is to calculate what distance the fly covers on the first, northbound, leg of the trip, then on the second, southbound, leg, then on the third, etc., etc., and, finally, to sum the infinite series so obtained. The quick way is to observe that the bicycles meet exactly one hour after their start, so that the fly had just an hour for his travels; the answer must therefore be 15 miles. When the question was put to von Neumann, he solved it in an instant, and thereby disappointed the questioner: "Oh, you must have heard the trick before!" "What trick?" asked von Neumann; "all I did was sum the infinite series." '
This is meant to sound very difficult (and might be, if you majored in journalism), but summing infinite geometric series is easy enough to do in your head if you're facile with fractions: (first_term) / (1 - step_multiplier).
Observe that, of the combined velocity of the fly and the bike approaching him, the fly always makes up 60%. That makes math easier since it eliminates division and time from the problem entirely.
On the first trip, the fly travels 12 miles and the bike approaching him travels 8 miles. There are now 4 (20 - 2 * 8) miles between the bikes.
On the second trip, the fly travels .6 * 4 = 2.4 miles and the bike approaching him travels 1.4 * 4 = 1.6 miles. There are now 0.8 miles between the bikes.
The part where people who are really good with math distinguish themselves from people who are not is realizing quickly that the problem they are looking at, with flies and bikes, quickly decomposes into "sum the series that starts 12, 2.4, etc".
12 / (1 - 0.2) = 12 * 5 / 4 = 15 miles total fly travel.
You can do it a little more formally if you want to verify the intuition that each step takes 1/5th the time (covers 1/5th the distance) of the previous step. (My intuition says "In the time that it takes the fly to go 5 units, the two bikes will chew up 4 units of that distance, so he is only left with 1 unit to travel the next time.")
I don't think it's about difficulty per se but the number of computations required. If 25 miles were covered by the fly and a bicycle, the fly covers 15 making it 60% (first calculation). Thus for 20 miles, the fly covers 12, bicycle 8 (second calculation). 20-16 or 4 miles are remaining of which the fly covers 2.4 (third computation). 2.4 is one-fifth of 12 (fifth computation). 12 / 0.8 => 12 * 5/4 = 15 (sixth computation). This route will always be slower because it requires more computations.
There is another "trick" solution : Let's denote a point when the fly turns around to be a step. Then just notice, from any one step the next, the fly travels exactly 1.5x the distance of any of the bicycles, since it goes 15mph versus the bicyclye's 10mph. This holds at each step, so is true of the total distance traveled as well. But alltogether, one bicycle will travel exactly half of the 20miles, so 10miles. So the fly will travel 15miles.
It's rather arguable that Waterhouse's inability to recognize that the question scenario was a deliberate simplification justifies his naval assignment. Because while he's clearly a brilliant mathematician in the story, he's really too damn dim about everything else to trust with much practical responsibility...
unfortunately, there is some practical truth in this Navy evaluation - Lawrence would definitely failed (ie. wouldn't complete them on-time and according to SOP) most of the assignments in the Navy or military in general.
That would simply be an indication that he was not suited for applying to the Navy. I find that many people who suck and fail at something may truly suck at whatever it is, but they're actually quite awesome at something else. The sad thing is that most people don't know how to find their path and even fewer people know how to set people on the right path where they can achieve their potential.
This video reminds me of an essay from Eliezer Yudkowsky¹. Feynman was basically forced to give a mysterious answer to a mysterious question. He did so, but not before talking about semantic stop-signs², how "magnetic force" could be one, and why it shouldn't be. Brilliant.
it really just depends on how much he wanted the job
I disagree. Feynman was famous for speaking his mind regardless of the context (Bohr insisted on Feynman's presence at critical points during the Manhattan project for exactly this reason, in fact -- everybody else was too inhibited around Bohr to speak up).
Feynman might have kicked himself afterwards, but wanting a job wouldn't have prevented him from pointing out an interviewer's errors.
There is a huge gap between speaking truth to power and being snippy to make yourself feel better. As a ridiculously intelligent and anti authoritarian friend put it. "You don't walk around barefoot on the first day of a new job, you need to break people in."
PS: And yes, he would eventually walk around the office / data centers without footwear.
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.
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.
Of anyone I've read or seen (in person or from videos), Feynman has the best fundamental grasp of meta-knowledge. By meta-knowledge, for lack of a better term, I mean understanding what it means to know something.
mhartl has already posted this excellent video: http://www.youtube.com/watch?v=wMFPe-DwULM, where he explains what the word "why" means in scientific inquiry. When we answer a "why" question, we don't really explain a concept in its entirety. At best, we're able to remove a layer of skin off the onion, but no one has ever really reached the center. I suppose science at it's heart is really just the elucidation of intermediate cause and effect scenarios.
For the question "why did the ball fall?", "Jimmy dropped it" is a perfectly valid answer. So is "Jimmy's motor neurons passed an action potential threshold, causing the muscles in his wrist to contract". So is "the ball moved along the curvature of space caused by the earth".
To be a touch prosaic, is it simplest to cover a round hole with a round cover? No, Round holes are drilled. Covers for them can be simply cut squarely from stock. Why have a geometric match? Either way provision has usually to be made for covers to he bolted and locked down even if they are resting on a flange.
I remember a conversation we had a year or so before his death, walking in the hills above Pasadena. We were exploring an unfamiliar trail and Richard, recovering from a major operation for the cancer, was walking more slowly than usual. He was telling a long and funny story about how he had been reading up on his disease and surprising his doctors by predicting their diagnosis and his chances of survival. I was hearing for the first time how far his cancer had progressed, so the jokes did not seem so funny. He must have noticed my mood, because he suddenly stopped the story and asked, "Hey, what's the matter?"
I hesitated. "I'm sad because you're going to die."
"Yeah," he sighed, "that bugs me sometimes too. But not so much as you think." And after a few more steps, "When you get as old as I am, you start to realize that you've told most of the good stuff you know to other people anyway."
We walked along in silence for a few minutes. Then we came to a place where another trail crossed and Richard stopped to look around at the surroundings. Suddenly a grin lit up his face. "Hey," he said, all trace of sadness forgotten, "I bet I can show you a better way home."