Hi, did you changed the font face today?
It looks good on IE, but horrible on Firefox 
(just to let you know).
Ravi Wallau.
ā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.
Solution 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.
I 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.
By the way, the IA folks have found an iterative way to solve the Hanoi towers problem
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%. 
Here 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.
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 =]
Ah, but you specified the next PERSON coming through the door would pick a blue marble. People arenāt entirely random. 
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.
"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).
@ 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
If 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
I firmly believe there is four fields of programming.
- 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.
- 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.
- Better ways to do output. Better graphics/graphs, more flexible reports, etc.
- 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!
[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 (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.