These puzzles take me back to my CS classes from college. Here’s how I encountered them:
Dinning Philosophers - Operating System Theory
Traveling Salesman - Algorithm Logic
Eight Queens - Algorithm Logic
Two Generals - Operating System Theory
Towers of Hanoi - Data Structures
The interesting thing about Towers of Hanoi is that I’ve written an implementation for the problem in C,C++,C#,Java and Scheme. Each, of course, got significantly easier!
The interesting thing about Towers of Hanoi is that I’ve written an implementation for the problem in C,C++,C#,Java and Scheme. Each, of course, got significantly easier!
Javier, sounds like you’ve got a blog post on your hands to me
I’d totally forgotten about To Mock A Mockingbird since I read it in a library when I was 12.
This post’s reason enough for me to buy a copy (and also Lewis Caroll’s “Symbolic Logic” and “The Game of Logic” since I just remembered that as well and it qualifies me for free delivery)
Here’s a variation that’s actually a very boring-looking puzzle with a cute story for a solution, as opposed to Byzantine Generals or Traveling Salesman, which are the other way around.
Unfortunately, this means that by reading the amusing story, you spoil the puzzle for yourself; but until you read the story, the puzzle may seem uninteresting!
While I appreciate the fact that there is a group of people out there doing those kinds of things - I want to make sure the interview is appropriate for the job. I do want people to know that there are well known problems with well known solution. I don’t really care if they can solve them in an interview situation. In my 20 years in many different industries I can count on one hand the number of times I’ve needed to know these types of things. That doesn’t mean the work is simple or uninteresting, just different.
You never defined the field as having to be pure mathematics.
we all know 99.999… = 100… In the real world, you don’t need infinite 9s to accept that equality.
Mechanical Engineers get really precise with dimensions on parts, but there’s always a variance accounted for. There’s absolutely nothing in the real world that can exist without some varience… Even in a computer, floating point numbers will make a high enough order of 99.999… be 100.
So basically, the problem is not impossible in the real world. It’s not impossible in a computer world. It’s not impossible in an engineer’s world…The only one who would fail is the mathematician?
By the way, if anyone ever answered my riddle, I would probably be suspicious that they already knew it. I think the answer that would give me the most confidence in a candidate would be “I don’t know, but if you give me 5 minutes with Google, I’ll have a solution for you.”
@Wayne “I still think even these are useless for most jobs since these puzzles focus on comp sci problems and hardly any jobs do. Most jobs are about building CRUD application. What good is puzzle solving if you job revolves around storing stuff in a database, reporting on it and transforming it?”
Sure, few of us need to directly solve a problem such as the Towers of Hanoi, but that isn’t the point, is it? The idea is that they exercise, as Hercule Poirot called them, “the little gray cells.” I’m not automatically looking for a “pattern” to apply in my day-to-day programming, but puzzle solving, I believe, is good for the brain.
I just finished writing up an article on The Byzantine Generals problem, which is similar to the Two Generals problem - it’s an exercise in agreement protocols.
Lamport, the guy who published a nice solution that is more or less the state of the art, seemed kind of miffed that the Dining Philsophers gets so much attention, and he decided that the way to get people to pay attention to your algorithm was to turn it into a story problem:
Lambda calculus isn’t just a core concept of lisp, it’s the smallest universal programming language. Lambda calculus is universal in the sense that any computable function can be expressed and evaluated using it, just as in a Turing Machine (the two are equivalent).
I liked the generals’ communication problem, but then, I got to study internetworking under a professor who did his PhD work under Comer. It brought back memories =]
As for problems that you missed, I was reminded of a problem I was given as part of an interview for a certain Seattle-based company.
You are in a room with 2 buckets. Each one contains 100 marbles - one bucket having blue marbles, the other having white.
Arrange the marbles in the buckets so that the next person coming through the door has the highest probability of picking a blue marble at random. Additionally, roughly, what is the probablity of them picking a blue marble?
Put all white marbles at bottom of each bucket, top off each bucket with the blue marbles. The probability is then 1 that the next marble picked is blue.
(Assuming another bucket to stop marbles spilling all over floor )