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.
