The Complexity Hammer
I’ve been doing a lot of interviewing lately, especially of college students. There is one tendency I see a that really separates those that are good from those who still have more learning to do. This is the tendency of the good programmers to see elegant solutions to problems and the corollary that less skilled programmers solve every problem by adding more complexity. Stated another way, the thing that separates the best programmers from the rest is what happens when they run into a serious issue. In my observation, the best coders step back and look for a more elegant solution. The less skilled coders assume that their approach is correct and that another piece of state or another special case is the best choice.
Here is an example. The problem has been changed to protect the innocent. Often times I ask a question similar to the change-making problem. That is, write a program to enumerate all of the ways to make change for a dollar. A typical approach might look something like this. Note, I didn’t actually compile this code so there could be typos. If there are, I’m sure you’ll let me know.
void MakeChange()
{
int moneyLeft = 100;
for (int quarters = 0; quarters <= 4; quarters++)
{
if (quarters) moneyLeft –= 25;
for (int dimes = 0; dimes <= 10; dimes++)
{
if (dimes) moneyLeft –=10;
for (int nickles = 0; nickles <=20; nickles++)
{
(if nickles) moneyLeft –=5;
for (int pennies = 0; pennies <= 100; pennies++)
{
if (pennies) moneyLeft—;
if (0 == moneyLeft) print…;
}
}
}
}
}
I know what you are thinking, “That’s not the right way to solve this.” And you would be correct. However, I have seen a lot of people give basically this solution. Their failure to solve it correctly the first time isn’t the point of this post. Rather, it is their response to the problem. If you haven’t spotted it yet, this will only work correctly for the first time down for loops. After we get to zero, we never gain the money back from the pennies we spent during the last nickles iteration. When I point this out, the solution is too often not to step back and re-examine the problem. “Is there something wrong with this solution?” Rather the typical reaction is to assume that the solution is mostly right and to tweak it. One might think of this as a specific case of not asking the 5-Why’s. The initial reaction is often just to reset moneyLeft at the top of the quarters loop. When that doesn’t work, more variables are added. The result solution looks something like this:
void MakeChange()
{
int moneyLeft = 100;
int moneyLeftQuarters = 100;
int moneyLeftDimes = 100;
int moneyLeftNickles = 100;
for (int quarters = 0; quarters <= 4; quarters++)
{
moneyLeft = moneyLeftQuarters;
if (quarters) moneyLeft –= 25;
moneyLeftQuarters = moneyLeft;
for (int dimes = 0; dimes <= 10; dimes++)
{
moneyLeft = moneyLeftDimes
if(dimes) moneyLeft –=10;
moneyLeftDimes = moneyLeft;
for (int nickles = 0; nickles <=20; nickles++)
{
moneyLeft = moneyLeftNickles;
if (nickles) moneyLeft –=5;
moneyLeftNickles = moneyLeft;
for (int pennies = 0; pennies <= 100; pennies++)
{
moneyLeft—;
if (0 == moneyLeft) print…;
}
}
}
}
}
Not exactly an elegant solution and not one that is easy to get right. There are a lot of subtle cases to think through. Unfortunately, code like this, or code trying to be like this shows up on my white board too often. In a simple problem such as this, it is possible to keep all of the cases in your head and get it right. When the problem becomes larger, however, this is no longer the case. The programmer with the above solution will fail. Thus the solution above is not an acceptable answer even though is technically solves the problem.
If one takes a few moments to step back and re-examine the problem, it is easy enough to see that one doesn’t need to track the amount of money left. It can be trivially calculated when necessary. This is just a specific case of the principle that one should never keep state that can be calculated. Tracking such state provides no benefit and offers the possibility that it will differ from the real state. The solution might look like this:
void BetterMakeChange()
{
for (int quarters = 0; quarters <= 4; quarters++)
{
for (int dimes = 0; dimes <= 10; dimes++)
{
for (int nickles = 0; nickles <=20; nickles++)
{
for (int pennies = 0; pennies <= 100; pennies++)
{
if (100 == (quarters*25 + dimes*10 + nickles*5 + pennies)) print…;
}
}
}
}
}
Much more elegant. Fewer state variables and thus less to get wrong. All of this stems from the idea that one need not track state. There is no reason to keep a running total of the money. It’s all readily available at any moment. It is this key notion that one needs in order to come up with a much improved algorithm. As long as the programmer doesn’t step back and question the need for tracking how much money has been used/how much is left, they will be stuck adding complexity on top of complexity. This is a prescription for failure. This is not an isolated case. Now that I have noticed this tendency, I can often spot it in interviews or even in code reviews. The moral of the story: always look for the elegant solution first. Can the problem be solved by eliminating something or by looking at the problem differently? Only once you have eliminated these possibilities should you add more state. Adding state isn’t always the wrong solution, but it can be a crutch to avoid deeper thinking.
A few notes:
The initial paragraph isn’t quiet accurate. The best programmers often see the elegant solution up front and get themselves into such trouble much less often.
The final solution is not optimal. I know this. Optimizing it would not benefit the example.
Comments
Anonymous
March 15, 2010
The comment has been removedAnonymous
March 15, 2010
The comment has been removedAnonymous
March 16, 2010
The comment has been removedAnonymous
March 16, 2010
The comment has been removedAnonymous
March 16, 2010
Some free complexity analysis: the stateless example makes the "is the total accurate" comparison (4 + 1) * (10 + 1) * (20 + 1) * (100 + 1) = 116,655 times. By comparison, the stateful version makes the comparison 6,962 times (I calculated this by incrementing a global every time the comparison was executed. I an not aware of s a way to calculate this elegantly.)Anonymous
March 16, 2010
The comment has been removedAnonymous
March 16, 2010
In BetterMakeChange(), the if check only evaluates to true on the first pass through, when the change for a dollar is 0 quarters, 0 dimes, 0 nickels, and 0 pennies.Anonymous
March 17, 2010
@Rick, the equality test in BetterMakeChange() should be with 100: if (100 == (quarters25 + dimes10 + nickles*5 + pennies)) print…;Anonymous
March 18, 2010
@Chad/Rick. Good catch. I'll change it.Anonymous
March 20, 2010
A bit OT, and it's probably unreadable, but it came to me as I read your post. It loops a total of 557 times, but also uses recursion. Perhaps it will stimulate discussion :). >(defun make-change (&optional (amount 100) (coins (list 25 10 5 1))) > (when coins > (if (cdr coins) > (iter (for i from 0) > (for remains downfrom amount by (car coins)) > (while (>= remains 0)) > (appending (mapcar (curry #'cons i) > (make-change remains (cdr coins))))) > (if (zerop (mod amount (car coins))) > (list (list (/ amount (car coins))))))))Anonymous
March 21, 2010
To me, factors that would impact on how well someone goes on a task like this would be:problem solving skills
level of nervousness The interviewee that has well developed problem solving skills may be helped secondarily by having the confidence to sit back and think about it, and conversely, a nervous interviewee probably won't have that confidence. I've noticed that "sitting back and thinking about it" can't be done (well) in front of the computer, or at least, not while using the computer, because it seems to bring the thought levels down to details and pixels, not concepts and possibilities. Also, I came across some brain fitness research (can't recall the link, sorry) which relates to how well they deal with the solution being wrong. Basically, when someone is afraid (read "nervous") or tired, and fails at something, they tend to retry the same or similar solutions - thus getting stuck in a rut. This can be applied to life, and gives me some food for thought - I think it has been picked up by some self-help book authors too. But also, and slightly off on a tangent, relating more to my previous post, what may also affect the outcome is how well they know the language/tools, and thus how well they can match the problem (or sub-problems) to existing solutions. For example, regarding optimization, because of the way it is written, the lisp solution above is amenable to memoization.
Anonymous
April 03, 2010
I agree with jonathan opinion about this article Jonathan what you meant by memoization is it suppose to be memorization or something else?