programming and human factors
by Jeff Atwood
Software developers do have a proclivity for puzzles. Perhaps that's why books like To Mock a Mockingbird exist. It's a collection of logic puzzles which is considered an introduction to lambda calculus, one of the core concepts of Lisp.
Such puzzle questions are de rigueur for many programming interviews, though they're often abused. There is a downside to thinking of programming languages as solutions to arbitrarily difficult abstract mathematical puzzles. That's probably why Lisp has a rich reputation for being powerful but simultaneously dense and impenetrable.
I prefer to think of programming languages as utilitarian tools for real world problems. They let me accomplish pragmatic (and often prosaic) goals. PHP is about as unsexy a language as you'll ever find, but does that matter when it's the technology driving the current Boardwalk and Park Place of the web world? I'm not a fan of puzzle questions in interviews; I'd rather have potential developers give me a presentation or write a reasonably useful program in the real development environment they'll be using on the job. Solve all the puzzles you want, but the only one we're getting paid to solve is the customer's problem.
That said, many fundamental computer science concepts can be summarized well in puzzle form, which aids tremendously in teaching and learning these key concepts. Here's a quick list of the classic computer science puzzles that I remember from my university days:
|
Dining Philosophers Concurrency and Deadlocks |
Five philosophers sit around a circular table. In front of each philosopher is a large plate of rice. The philosophers alternate their time between eating and thinking. There is one chopstick between each philosopher, to their immediate right and left. In order to eat, a given philosopher needs to use both chopsticks. How can you ensure all the philosophers can eat reliably without starving to death? |
|
Travelling Salesman P=NP |
A salesperson has a route of cities that make up his or her beat. What's the most efficient sales route that visits each city exactly once, and then returns to the home city? |
|
Eight Queens Algorithm Design |
Given eight queens on a standard 8 x 8 chessboard, how many unique positions-- exclusive of rotations and mirror images-- can those eight queens occupy without attacking each other? |
|
Two Generals Communication Protocols 
|
Two armies, each led by a general, are preparing to attack a city. The armies are encamped outside the city on two mountains separated by a large valley. In order to capture the city, the generals must attack at exactly the same time. The only way for the generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders, so there's a chance any given messenger will be captured. Each general has no way of knowing if their messenger arrived. How do the generals coordinate their attack? |
|
Towers of Hanoi Recursion |
You have a stack of discs, from largest to smallest, that slide on to the first peg of a three peg board. Your goal is to move the entire stack of discs from the first peg to the third peg. However, you can only move the topmost disc of any peg, and smaller discs must always be placed on larger discs. How many moves will it take? |
I consider this the "greatest hits" of classic computer science puzzles. But I'm sure I've forgotten a few. Are there any other puzzles I've missed that express fundamental computer science concepts, the type that would be taught in a typical undergraduate computer science course?
Interesting way to tie puzzles back to what programmers really do. However, 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?
Wayne Allen on September 13, 2007 2:11 AMRe: random "solving" the two generals problem
The problem isn't asking for a solution that works *most* of the time, it's asking for a solution that works *no matter what*. The whole point is that such a solution is impossible.
It's definitely possible (and not very hard) to come up with a strategy that works 99.99999% of the time (for as many 9s as you want).
andy on September 13, 2007 2:11 AMJeff,
I'm a big fan of Dennis Shasha's "Dr. Ecco" series of books and magazine puzzle columns. If you've never read any of them, I'd encourage you to take a look.
Matthew Cuba on September 13, 2007 2:14 AMIt's not that LISP is dense and impenetrable, although Common Lisp took it a good long way down that road. Unfortunately, many Lisp programmers were dense and impenetrable.
Lisp had a lot of nice features that never got used because Lisp vendors never understood their market, outside of research universities.
A. Lloyd Flanagan on September 13, 2007 2:14 AMI remember one called the "Sleeping Barber" problem, related to communication between separate processes.
http://en.wikipedia.org/wiki/Sleeping_barber_problem
Ben Reichelt on September 13, 2007 2:24 AMIf I recall correctly, the eight queen problem is not about how many queens can be placed, the number of queens is always N for a NxN chess board. The problem is how to place the queens, and how many different solutions there are.
Einar on September 13, 2007 2:34 AMHere's a great history of the traveling salesman problem.
http://www.tsp.gatech.edu/index.html
If you prove this is a NP-complete problem (not just NP-hard), you could win a $1,000,000 dollar millennium prize:
http://www.claymath.org/millennium/P_vs_NP/
--
one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like [travelling salesman] certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer.
--
Boston only has two outbound routes and New York only has inbound routes, therefore the problem can not be solved. ;)
Also, the two generals problem is easily sovlable in the real world - you acknowledge the fact that a transaction may fail, and include sufficient auditing and administration tools to allow detection and repair of failures. And for those who haven't studied the real world, the probability of six thousand messages being lost (after the first one is lost, given a dumbass with a backhoe hitting the network link at the wrong time) is approximately 100%. Any system designed with a suitable strategy to cope with a failure (whether the probability of failure is 99.999999999% or 0.000000001% will be equally effective.
The problem can not be solved - but in the real world you can always have a plan B to account for the reality.
Honestly, you can whinge about "probability" all you like, but if "the chance of failure is the same as your chance of winning the lottery" is your justification for not providing a strategy to cope with errors then I don't want to use your software. And if you do provide quality software, then you're acknowledging that there is always a possibility of failure.
Besides, if you try the "6 acknowledgement messages and then commit" approach to transactional reliability, your system will be a lot slower than most, and lets be fair - the odds of a network outage that can't be automatically repaired pretty quickly is already quite low.
Bob on September 13, 2007 2:42 AMI've a coworker dealing with management of an outsourced program who is backtracking on just about everything she promised in writing, including giving the money back.
I'd love to see a similar problem used for the yet-to-be-hired programmer to figure out.
And honestly, isn't dealing with people one of the hardest puzzles out there
Because of the nature of the situation, truthful and accurate, I can't post my name, but I'm a regular reader.
as for other "fundamental" puzzles - perhaps the classic "conway's game of life"? not an actual puzzle (althought you can create puzzles using it) but quite scientific and entertaining at the same time.
sz on September 13, 2007 2:48 AMEinar, thanks for the correction. I didn't quite finish writing the Eight Queens description up and I didn't realize it before I pressed the post button. The question is not "how many queens can exist on a chessboard of a given size without attacking each other" (although that's interesting, too).
Jeff Atwood on September 13, 2007 2:52 AMthe two generals problem is easily sovlable in the real world -
If two generals is too easy, you should move on to byzantine generals.
http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
You now have (n) generals who must decide to attack unanimously. And here's the other twist: some of them are traitors.
Jeff Atwood on September 13, 2007 3:06 AMI think all job interviews are missing one essential skill test: can the person touch type?
There's something wrong if you work in tech and you still have to hunt-and-peck and look at the keyboard while you type.
Screw hiring smart people -- hire people who don't make typos.
engtech @ IDT on September 13, 2007 3:19 AMSierpinski Triangle
Recursion
http://en.wikipedia.org/wiki/Sierpinski_triangle
Short of spending a day looking over the shoulder of a candidate, there really is no remotely save way to be sure that they are capable enough to hire. Gets even worse if you have to hire someone to do something that YOU YOURSELF don't understand (aka some expert sub-field). It's odd that programmers with their desire to solve problems haven't come up with a decent hiring solution yet.
J. Stoever on September 13, 2007 3:21 AMBy the way, you forgot the "sleeping barber", a classic programming problem to process communication and synchronicity (is that a word ?) that involves deadlocks and starvation.
Good article about it: http://en.wikipedia.org/wiki/Sleeping_barber_problem
J. Stoever on September 13, 2007 3:42 AM"Screw hiring smart people -- hire people who don't make typos."
That's why static type systems were created. ;)
Scott on September 13, 2007 3:43 AMI love these puzzles: http://projecteuler.net.
I don't know about others, but the problems I solve at work often look a lot like some of these puzzles.
--Donnie
Donnie on September 13, 2007 4:01 AMRE: Wayne
The majority of developers to develop CRUD apps for IT shops, but there's still a good number of us out there who work on more complex systems... embedded environments, physics simulations, routing, graphics, protocols, kernels, etc. I'll be the first to say that solving these puzzles goes a LONG way toward success in those environments. I use this stuff every day.
Michael on September 13, 2007 4:22 AMThese 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!
Javier Lozano on September 13, 2007 4:26 AMThe 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 :)
Jeff Atwood on September 13, 2007 4:33 AMI'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)
Gareth on September 13, 2007 4:52 AMYou didn't mention the firing squad problem:
http://en.wikipedia.org/wiki/Firing_squad_synchronization_problem
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!
http://groups.google.com/groups?selm=gq8aevcqsav78sv2ko1e02lahv24vfthob@4ax.com
(several messages down in the thread)
RE: Michael
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.
Wayne Allen on September 13, 2007 5:20 AMHey Andy....
you say 99.9999999% is possible, but not 100%.
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?
General Guy Again on September 13, 2007 5:28 AM"we all know 99.999... = 100... In the real world"
It does in the math world too...
x = 99.999...
10x = 999.999...
10x-x = 999.999... - 99.999...
9x = 900
x = 100
99.999... = 100
To get infinite 9's probability the generals would have to communicate infinitely
name on September 13, 2007 6:18 AMIn real life, they are both on a mountain with nothing in between, so they could just wave flags and start running :p
J. Stoever on September 13, 2007 6:22 AMBy 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."
J. Stoever on September 13, 2007 6:24 AM@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.
Matthew Cuba on September 13, 2007 7:33 AMthe generals should decide when to attack *before* they get to the freakin' valley. duh!
plan-ahead on September 13, 2007 7:35 AMHey Now Jeff,
Towers of Hanoi is such a classic. The 8 queens is really good too (I enjoy chess). One of my favorite puzzles I was presented in my university days that has fundamental CS concepts is the 'Birthday Paradox' there are quite a few variations here are two http://en.wikipedia.org/wiki/Birthday_paradox http://en.wikipedia.org/wiki/Wikipedia:Reference_desk/Science/Birthday_probability_question
Thx,
Catto
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.
http://marknelson.us/2007/07/23/byzantine/
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:
http://research.microsoft.com/users/lamport/pubs/pubs.html#byz
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).
Andrew Gwozdziewycz on September 13, 2007 9:35 AMThe Knapsack problem - dynamic programming.
http://en.wikipedia.org/wiki/Knapsack_problem
Doug on September 13, 2007 9:53 AMI 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?
Bladesjester on September 13, 2007 11:44 AMRE: blue marbles problem
I might regret this, but:
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 :) )
David Dawkins on September 13, 2007 12:45 PM@Bladejester: half the white marbles in the bottom of each bucket and fill-em-up with blue?
bjorn on September 13, 2007 12:46 PMI've *just* come from reading the dining philosophers problem in Algorithmics: The Spirit of Computing!
[ICR] on September 13, 2007 1:11 PMFizzBuzz
Scott on September 13, 2007 1:33 PMHi, did you changed the font face today?
It looks good on IE, but horrible on Firefox :-) (just to let you know).
Ravi Wallau.
Ravi on September 13, 2007 1:37 PM@Scott - Don't EVEN start that again!
Steven Harman on September 13, 2007 1:49 PM"Solve all the puzzles you want, but the only one we're getting paid to solve is the customer's problem."
That's true unless you want to work for Google. Then you have to solve all kinds of puzzles.
Dave on September 13, 2007 1:52 PMSolution to the "impossible" two generals problem... (pasted from my own post on the site I read this article at).
I disagree with the General problem being unsolvable...there's a factor that can be utilized to make the probability of success ~= 100% for all cases where a messenger has a -reasonable- chance of sending the message..... -time-
I'll assume the messenger succeeds 50% of the time, and that it takes 1 hour to send a messenger. (probably higher success rate with lower time to send)
Start by offering an attack time a month in advance. Re-send every hour until you get a confirm.
Second general re-sends his confirm every hour until he gets a confirm, then sends a final confirm.
The chances of 6 sends ALL failing approach zero. This algorithm would work for 6 sends in 24 hours time, giving 29 more days (or 696 hours) for the first general to receive the final message and confirm the attack.
The failure chance in this (somewhat) reasonable argument is 3.0417465060722557176241158493362e-210... that is to say, the same chance that both generals will get struck by lightning or an internal revolution will make the attack moot while they siege the city for a month.
I know the puzzle is supposed to ignore 'reality', but when the odds are under the odds of the computer glitching and reporting incorrectly, (or 1-x = 1 in windows calc), I still win.
The generals problem is only insoluble if you live in a 2d world, even then if that world were a circle ... and the valley in the real world would have to start somewhere a long way from the city with a river going down the middle of it so you could either travel to the top of the valley and pass messages there, or go via the sea.
Francis Fish on September 14, 2007 2:02 AMI studied VB as my first language back in school and had to implement Towers of Hanoi for my final assignment. Now I'm in University 8 years later and I have to implement towers of hanoi in Lisp as a once off laboratory session.
Logic problems and programmatic problems are always going to go hand in hand. They're useful when learning to get a grasp of the concepts involved. However, they should only be used in the very base subjects. Once first year is over, throw out the games, and assign some real world type problems.
From your list I've only had to do the Towers. Have never heard of any of the others in regards to my CS course. I've studied the concepts, but not the stories or games behind them.
While I'm at it.. how important is engineering mathematics in software development these days? Unless you're hired to work on scientific or complex systems which I'm guessing would be the minority of projects. The whole CS education system should be overhauled - learn too much of what you don't need to know or can discover very simply on your own, and don't learn enough of the stuff that matters.
`Josh on September 14, 2007 2:08 AMBy the way, the IA folks have found an iterative way to solve the Hanoi towers problem :)
Miguel Ping on September 14, 2007 2:54 AM@BladesJester:
Empty the blue marble bucket, pour half the white marbles in to it. Put half of the blue marbles in each bucket so they fully cover the white marbles.
Probability should be close to 100% of picking a blue marble. You'll get That Guy who digs to the bottom though, so maybe 99%. ;)
Telos on September 14, 2007 3:08 AMHere are my comments on 1 of 17 google interview puzzle questions:
http://www.pixelbeat.org/docs/google_gender_ratio_puzzle/
Google recently announced this year's Code Jam competition and included a couple of practice problems. The second one sounds like a standard Traveling Salesman, but can anyone tell me if the first one falls into a common 'class' of problem?
The problems are here: http://services.google.com/blog_resources/Google_CodeJam_Practice.pdf
Essentially, the problem describes a series of contiguous rectangular areas of different sizes (think of the skyline of a city). You are then asked to determine the size of the largest rectangle that would fit into that shape.
I've solved that problem relatively easily, but probably in the least efficient means possible. I iterate through each rectangle then calculate the size of the largest area that rectangle is a part of. I'm just curious as to a more efficient method of solving the problem.
Richard on September 14, 2007 3:16 AM@telos
Nope. Re-read my post. The marble is picked completely at random. For all intents and purposes, every marble is at the top of the bucket that contains it. The person reaches into one of the two buckets, and grabs a random marble.
It's an exercise in manipulating probability. Quill got it right.
Of course, my smart-arsed first answer was to toss the white marbles out the window and split the blue marbles between the two buckets =]
Bladesjester on September 14, 2007 3:24 AMAh, but you specified the next PERSON coming through the door would pick a blue marble. People aren't entirely random. :P
Yes, I cheat... as long as it works it's good.
I had an interview once where I got a puzzle question, I don't remember it exactly but 5 (?) people with a flashlight needed to cross a bridge two at a time in under a certain amount of time. They each had different speeds and traveled as fast as the slowest guy in the pair... you had to get everyone across the bridge in X minutes.
My solution was to have the fastest guy carry the slowest guy at the end, so that the speed would average out and get in just under the limit.
The interviewer couldn't say I was wrong, just that I'd solved it incorrectly. ;)
Telos on September 14, 2007 3:36 AM"and also Lewis Caroll's "Symbolic Logic" and "The Game of Logic""
I wont those books soooo bad.
And g is right about TSP and NP-Complete. What is interesting is that there are a whole class of problems that are provable to be NP-Complete by showing that one can be transformed into another, already known to be NP-Complete (using polynomial-time reduction). So if you prove that one is tractable they all are tractable (solvable in polynomial-time).
[ICR] on September 14, 2007 5:37 AM@ Richard: I have no idea about the class, but how about this: pick out the lowest height of the buildings, multiply it by the total width of all buildings, and use this as a comparison? You want to end up with "clusters" of buildings and add either a new building left or right with the least penalty, thereby reducing the candidates with every pass. Wild-ass guess, by the way.
Thanks for the link - it's a nice puzzle :)
Rob Janssen on September 14, 2007 5:45 AMIf anyone's interested, I coded up a little example of Software Transactional Memory in C# - it neatly solves the Dining Philosophers and Sleeping Barbers problem, without needing any locks or events in client code. (Obviously they're present somewhere deeper though!).
This is the fourth and final part of the articles, but it links back to the others:
http://www.feedghost.com/Blogs/BlogEntry.aspx?EntryId=17791
Stu
Stu Smith on September 14, 2007 5:54 AMI firmly believe there is four fields of programming.
1) Data capturing, processing it and then output. 80% goes to validating user input, 5% to processing and 15% to output. You can always re-process valid data and the output, but never bad input.
2) Solving "math" or puzzles. (You can get to 1000 by 1+1+1.. or the better way) The "better way" is the solution. But 1+1+1 still gets you there.
3) Better ways to do output. Better graphics/graphs, more flexible reports, etc.
4) Guessing user intentions. When a user search for "world cup" does he really means "Soccer World Cup" etc. [ 1) would ensure valid input, 2) would resolve the fastest search method and 3) the output quality] But listing the output "alpha numeric" would be wrong, as 45% of the users were looking for the "Soccer world Cup" and not the "Athletic World" cup.
1..3) Is pure program logic but 4) is linked to listening to your customers and learning their needs. You can be a master at 1..3 but if you failed at 4) you are doomed.
PS. I still hunt and peck on the keyboard and I write programs with a user interface that is not in my mother language. But I did not loose any clients in 4 years, because I listen to them. Saving 0.001 milliseconds in processing time, does NOT make you a better programmer!
THERE IS NO PUZZLE TO LEARN YOU HOW TO LISTEN TO YOUR CUSTOMER!
Cornie on September 14, 2007 5:58 AM[QUOTE]The Knapsack problem - dynamic programming.[/QUOTE]
I put Knapsack is in the same category of Traveling Salesman. Both are (presumably) NP-complete problems that lend themselves to some interesting heuristic-based pretty good "solutions", stochastic algorithm-based (such as genetic algorithms) better "solutions", and, of course, the actual, guaranteed, optimal solution that takes way too long to compute on large instances of the problem.
"THERE IS NO PUZZLE TO LEARN YOU HOW TO LISTEN TO YOUR CUSTOMER!"
Indeed. But without puzzles there is no way to do what you heard the customer wants :P (Yes, I know you know that, I'm just teasing).
@Richard: The way I've thought the problem is using dynamic programming, since each iteration is calculated using the solution of the previous subproblem and the newly added building.
Consider you iterate the buildings starting from the skyline, then you add the largest building adjacent to it, then the largest one adjacent to the block, etc. At each iteration, you compute the area of the block as (blockWidth * minHeight), where minHeight is the height of the shortest building in the block. The problem can be seen as
f(n) = max ( f(n-1), (width * minHeight) )
where n is the number of the iteration. Note that each iteration takes constant time, therefore it is linear on the quantity of buildings.
Now that I re-read it I'm not sure whether it is dynamic programming or not. But well, it's a solution.
As for other famous problems, I would add the "recently" solved one concerning whether it is possible to paint the world map (ie a planar graph) using 4 colours (in such a way that two adjacent countries don't have the same colour).
Don't forget the "Puzzler" from Car Talk on National Public Radio:
http://cartalk.com/content/puzzler/
They're not always math puzzles and rarely puzzles to do anything with computer science but they're always entertaining.
How about Four-colour map theorem?:
http://en.wikipedia.org/wiki/Map_coloring
And its big brother, graph colouring:
http://en.wikipedia.org/wiki/Graph_coloring
Not strictly speaking puzzles, but they certainly have some game elements to them.
Graham Stewart on September 14, 2007 7:48 AMNot being a math person, I tend to think of programming languages as...languages. They are nothing more than another way to speak, except you are speaking to a machine.
This is why I don't tend to get into many math puzzles, I prefer linguistics puzzles like cypher cracking and such.
Mattkins on September 14, 2007 8:14 AMHere's some we had to do.
There are 35(?) soldiers at the MASH unit and Colonel Potter has 1 weekend pass. The soldiers will stand in a circle around him and count off. Every fifth one will be eliminated from the circle. The last man standing gets the pass to Seoul for the weekend. In what initial position does Max Clinger need to stand to get the pass?
One prof gave us the counterfeit coins problems for homework (12 coins, one is counterfeit and weighs slightly more or slightly less than the rest. Given a balance scale, determine the counterfeit in 3 weighings). I already knew the riddle, so I "solved" it easily. Then I wrote an inductive proof showing how many weighings would be needed for X number of coins. The teacher was so pleased that I had combined two parts of the class. I had never seen him happier.
Frank on September 14, 2007 8:28 AMIn real software development world these days, I my opinion, Tower of Babel is more relevant example than Tower of hanoi!!
http://en.wikipedia.org/wiki/Tower_of_Babel
:-)
param on September 14, 2007 8:45 AMJeff, I'm afraid what you say about the travelling salesman problem and P-versus-NP is garbled.
The travelling salesman problem is *known* to be NP-complete (and also NP-hard, which is implied by NP-complete). What would get you the Clay prize is proving either that P=NP (in which case the travelling salesman problem would be in P, because it's in NP) or that P != NP (in which case the travelling salesman problem would not be in P, because it's NP-hard). So it's where TSP falls relative to class P, not relative to class NP, that you need to establish to win $1M.
(TSP is in class P iff you can always solve any instance of it in time that's at most some_fixed_polynomial(n) where n is the number of places the salesman has to visit. A decision problem -- one where the question is always "does there exist some configuration such that ...?" -- is in class NP iff the problem of checking a particular configuration is in class P. An optimization problem like TSP is said to be in class P, or class NP, or whatever, iff the problem "is the solution to the optimization problem at least ...?" is always in P, or NP, or whatever. Given an efficient solution to that problem, you can then solve the optimization problem efficiently by binary search.)
g on September 14, 2007 8:49 AMPuzzles are a great way to find out how deep someone's understanding of problem solving process really is.
However, today's IT marketplace is flooded with automatons who are not hired to think or solve problems but to pound "templated code." And then we hear how many people can't write code. This is because they cannot think (for themselves) either.
Don't forget the Little Schemer books on lisp. Lots of good examples on how to apply lisp and think through problems. "Schemer" refers to Scheme, a Lisp implementation (freely available) - for those who are not familiar with Lisp "marketplace."
There is also a book called "How to move mountain Fiji?" which has a lot of puzzles from Microsoft interviews.
Sam on September 14, 2007 9:04 AM@bladesjester
Place 99 blue marbles in the bucket of whites marbles and leave one blue marble by itself. There is now have 100% chance to pick the lone blue if they go to that bucket and 49.5% to pick a blue if they choose the mixed bucket.
Ran across the one recently.
Quill on September 14, 2007 9:12 AM@Quill
ding ding ding!
And here I thought I was going to have to post the answer myself after the first couple got it wrong =]
Bladesjester on September 14, 2007 12:40 PMThe first computer problem I solved on my own - 25 years ago with lots of thinking at age 10 - was the towers from hanoi. I remember doing some experiments with coins and then coming up with a interative solution, not a recursive one. This made me somehow proud.
After programming for 25 years and solving lots of problems, I'm still proud of solving that problem as my first one on my own (there was no internet back then ;-)
Peace
-stephan
CCP tested me not too long ago and prolly their most mind bending question was:
Given a list of of resister, return a value true or false wether a resistance can be met with any combination of resistors in series or parrallel circuit.
David on September 15, 2007 3:39 AMre: `Josh on September 14, 2007 01:08 AM .. how important is engineering mathematics in software development these days?
I would say that graph theory and queuing theory are exceptionally valuable, even if the student does not remember the formulae afterwards. (They can always find them online) Many stupid system and network sizings are based on ignorance of even the concepts of these two subjects. And yes, sizing the target system, or developing software to fit in a target system are parts of the software development job.
In analyzing message error rates in communications systems where bit error probabilities are low (e.g. 1E-4) or very low (e.g. 1E-6), I have found it useful to use a few terms in a Taylor series. Even with double precision accuracy the message error rate as calculated by a spreadsheet for a 1400 byte message at a bit error rate of 1e-6 is likely to be way off. =1-(1-0.000001)^(1400*8)
DAKra on September 15, 2007 8:30 AMOne of my favorites, "Every programmer knows why sewer lids are round, but why are septic tank lids square?"
Another favorite:
1) Pick a number between 1 and 9
2) Subtract 5
3) Multiply by 3
4) Square the number
5) Add the digits of that number together, for example, if you number is 83, you would add 8 and 3 and get 11.
6) If the resulting number is less than 5, add five, otherwise subtract 4
7) Multiply by 2
8) Subtract 6
9) Assign a letter to your number. A=1, B=2, C=3, D=4, E=5, etc
10) Pick a country that begins with your letter
11) Pick an animal that begins with the second letter from your country
12) think of the color of that animal
Why are you thinking about a gray elephant in Denmark?
he decided that the way to get people to pay attention to your algorithm was to turn it into a story problem:
And that's really the heart of this post, isn't it? Tell a story if you want people to understand the problem.
Jeff Atwood on September 17, 2007 3:24 AMThe puzzles may have little to do with programming aptitude, and little relevance to any real-world situations. However (um, make that in italics [i] [/i]) these puzzles and the answers can show a lot about the candidate's skills. It's a way of getting the candidate a bit off-balance to see how he (or she) handles an unexpected situation.
There could be anything from ignorance, "Hanoi has towers?" to overconfidence, "Oh, that's a trapdoor-knapsack problem. It's unsolvable." Whatever the initial answer, a few followup questions can give a clue to the interviewee's problem-solving skills and ability to work with a team (in this case, the interviewer).
Which is why technical skills are often NOT the things you look for in a new employee. You assume the job skills are as stated on the resume, because you really can't assess that outside a couple of months probationary period. What your need to determine in a short interview is the people skills: Can this person take instruction? Give instruction? Is he arrogant or cooperative?
Yeah, I know some coders could be fine locked in a windowless closet, with a pizza shoved through the slot at mealtimes, but most of us have to talk to other people. If you can't be patient with an end-user and persuasive with a superior, The company may be better off with someone else.
Izzy on September 17, 2007 5:14 AMThis post makes me nostalgic and takes me back to those good old college days.
Though this problem does not come under any puzzle, recursion used to fascinate me a lot.
especially using Ackermans funtion to crash your computer !!.
I vaguely remembers there was a section on "Knights and Knaves" in this book. The knights always tell the truth while the knaves always lie. :-)
sing chyun on September 18, 2007 11:22 AMHey guys this is cool stuff
In NYU, I had a classmate keep asking me questions about how to accomplish things in constant time and constant memory, such as finding out whether a linked list contains a loop or not by using an algorithm with constant memory. I told him something along the lines of "test for a loop of length k by remembering the current link, then a loop of length k+1 from the current link, etc. until you get to the end of the list or find a loop"
Then he asked me how to implement a buffer that can have read, write and clear all in constant time. But you can use as much memory as you need. I said timestamp .... but there was a better, more abstract way. I forgot what it was.
Where can I find more such puzzles?
AND HEY CHECK THIS MATHEMATICAL PUZZLE OUT. WHAT DO YOU THINK OF IT?? :)
ENJOY,
GREG
and what kind of stupid problem is the two generals problem (as stated) .... obviously if there is a chance all messengers get captured then this problem can never be solved in all cases. A 10 year old can see that.
Gregory Magarshak on September 18, 2007 11:40 AMhm
Gregory Magarshak on September 18, 2007 11:42 AMIt's actually an introduction to combinatory logic, not LC. The two are considered functionally equivalent but aren't exactly the same.
Steve Jenson on September 19, 2007 10:19 AM@bladesjester
If you meant this to be a mathematical problem, then you should state the conditions more clearly to present it as a purely mathematical problem. I have heard this problem before, but your description of the problem lends itself to some creative answers because it describes a real world situation. A person choosing a marble randomly in a room from two buckets has too many variables to determine the probability.
Observations:
1) You did specify that the new person would choose a marble at random from inside one of the buckets.
2) You specified a that a *person* would choose "randomly" which introduces a lot of variables.
3) You did not specify that the choice of bucket was completely random as well as the choice of marble.
Potential solutions that exploit the above observations:
1)Put all of the marbles in one bucket. Put the other bucket on top of of the full one upside-down. Put a single blue marble inside the rim of the bottom of the upside-down bucket. A bucket has two concave surfaces, either of which can be considered "inside" under normal assumptions. Under topographical assumptions, neither could be considered "inside" the bucket.
1) Melt the plastic of both buckets. Put the white marbles into this goo and reform the plastic into a new bucket made of plastic and white marbles. Place the blue marbles into this new bucket. Both the white and blue marbles are inside of both buckets.
2) Leave a post-it note: "Take One" on the blue marble bucket.
2) Completely fill one bucket until it is brimming with all of the white marbles and pee. Leave the blue marble bucket as is.
23) Put all of the white marbles in one bucket, then the second bucket with blue marbles on inside of that bucket covering the white marbles.
23) Cover the white marble bucket with your shirt and turn it upside-down. Slide your shirt away to leave the white marbles contained by the upside-down bucket. Then place the full blue bucket on top of the upturned white bucket.
3) Stack the buckets so you can climb to the ceiling. Hide the white marbles bucket in the ceiling.
There's quite a few good ones here:
http://www.ocf.berkeley.edu/~wwu/riddles/intro.shtml
One of the first ones we worked with in college was the Cannibals and Missionaries Problem.
http://www.learn4good.com/games/puzzle/boat.htm
Fairly simple, but a good warm up to some of the harder ones.
Aston on February 6, 2010 10:14 PMThe comments to this entry are closed.
Subscribe in a reader
Subscribe via email
|
|
Traffic Stats |