Google is gaining a reputation for asking interview questions of new job candidates that sound like IQ test questions. These things are bizarre logic problems, some of which you might have already heard and already know how to solve — though Google, I’m sure, tends to use more difficult and less known variations. Other employers sometimes use similar interview techniques.
I’ve stumbled across a relatively new weblog at blogspot.com called Classic Puzzles. In it, the author presents bizarre logic puzzles of exactly the sort favored by certain employers of programmers. These puzzles are exactly the sort of thing that (supposedly) helps to demonstrate your ability to reason through algorithm design when you’re engaged in a software development project, particularly where code efficiency is important. For instance, the solutions to some of the puzzles that will probably show up in that weblog can be directly translated into well-known sorting algorithms.
One of the puzzles presented postulates a set of thirteen balls (or twelve — it’s really the same solution for either number, with an added chance of finishing early in the case of the thirteenth ball), one of which is a different weight from the rest. The solution requires that the maximum needed number of weighings with a simple balance-scale is minimized. Thus, while thirteen balls affords an opportunity to finish with only one weighing by determining that all balls except the thirteenth weigh exactly the same, the important measure is how many weighings are required in the worst-case scenario. The answer, by the way, requires only three weighings. I’ll leave it to you to discover it, or to look it up on the Classic Puzzles weblog if you want to “cheat”.
Another of the puzzles on that weblog is the “two eggs” problem where you must determine the highest safe floor of a 100-storey building from which you may drop a particular type of egg without the egg breaking, and without any idea how tough these eggs are before you start. This problem is known as a “two eggs” problem because you are allowed to break a grand total of two eggs in the process of discovering the highest safe floor for dropping eggs. The correct solution will require you to achieve an answer in the smallest possible number of drops, which means that starting at the first floor and working your way up one at a time will take far too long to be acceptable.
I managed to figure out the answers to both of these on my own in a matter of minutes, despite the fact that the closest I’ve ever come to either one of these problems before was an eight-ball version of the thirteen balls problem (which is considerably easier to solve and far better known). Having considered these problems, and their solutions, at some length I’ve decided that neither one of the solutions is exactly what most interests me. Instead, I’m more interested in developing an algorithm not just to solve the problem as presented, but to solve the problem without knowing how many balls, or how many floors in the building, at the time when the algorithm is developed.
I’m curious, for instance, whether there is an α(n) solution to an n balls problem, where α(n) is a function that produces an extremely slowly accelerating curve — not quite O(1), but in practical terms darned close to it. If O(1) looks like gibberish to you, check out the Wikipedia article about Big O notation. In simple terms, O(1) means that the time to complete an operation on a given data set is constant, no matter how big the data set is. By contrast, O(n) means that the time to completion progresses linearly, in exact proportion to how many items are in the data set.
I managed to work out a system for solving the two egg problem for n storey buildings while I was solving the problem. It was the simplest path to completion for me. I thought about it, and realized that unlike the n balls problem it does not lend itself to a constant operation period the way a given data set size for weighing balls does. The maximally efficient system will be one that very consciously aims to be solved in a specific number of operations, and the trick is to determine that number. One must drop from a given storey, then if it breaks start at one and work your way up to the next time it breaks. If it doesn’t, jump up to a higher number by adding one less than the last number you added. For instance, with a ten storey building, you’re best off starting at the fourth floor and, assuming you never break an egg before getting to the tenth, add three, then try again after adding two. This means that if it breaks on the first try at the fourth floor, you max out at four tries, with four, then one, then two, then three. If it doesn’t break, but does at seven, it still only takes four: four, seven, five, six. And so on. The same principle applies to twenty, forty, a hundred, or any other number of storeys in the building.
This magic starting number can be determined by counting backward from the number of total storeys in the building, in increments that increase in size by one each time. To arrive at four, I started with ten and subtracted one. Next, I subtracted two, then I subtracted three. 10 – 1 = 9. 9 – 2 = 7. 7 – 3 = 4. It’s that simple. There’s a two stage calculation involved: first, determine your “magic number”, and second, apply your test using that number as your starting point.
I haven’t yet attacked the problem of a set of n size for the n balls problem, basically because I didn’t have the epiphanic moment while solving the problem of realizing the underlying principle of it that I did with the two eggs problem. Do any of you have ideas for how to approach it?