The Shyam

Using Polymorphism instead of Conditionals

Interviewing nowadays with tech companies has become run of the mill. You have phone screens, then you are brought on for on site interviews. And in each one of these, you are asked one mind-bending, off-ball algorithm question after another. I personally have been on both sides of the interview table, having asked and been asked my fair share of these. And after a while, I started questioning whether these questions provided any insight into how interviewees think other than their knowledge of algorithms.

It was then that I decided I wanted to try and find out if the candidates really understood polymorphism and other concepts, rather than their knowledge of algorithms, since every other interviewer would be covering that. And that was when I stumbled upon this gem of a question, which also underlies a fundamental concept of object oriented programming.

The question is simple. “Given a mathematical expression, like 2 + 3 * 5, which can be represented as a binary tree, how would you design the classes and code the methods so that I can call evaluate() and toString() on any node of the tree and get the correct value.”. Of course, I would clarify that populating the tree was out of the scope of the problem, so they had a filled in tree to work with. It also gives me a chance to figure out how the candidate thinks, whether he asks whether filling in the tree is his problem or whether he just assumes stuff. You could preface this question with another about Tree’s and traversal to check the candidate’s knowledge and whether this one would be a waste of time or not.

Now, one of three things can happen at this point. One, the candidate has no clue about trees and traversals, in which case there is no point proceeding down this line. Second, which seems to happen more often than not, is the candidate gives a class and method like the following :
class Node {
char operator;
int lhsValue, rhsValue;
Node left, right;

public int evaluate() {
int leftVal = left == null ?
lhsValue : left.evaluate();
int rightVal = right == null ?
rhsValue : right.evaluate();
if (operator == '+') {
return leftVal + rightVal;
} else if (operator == '-') {
// So on and so forth.
// Same for toString()
}
}
}

Whenever I see code like the example above, it just screams that whoever is writing it has no clue about how to work with Polymorphism. While I agree that some conditionals are needed, like checks for boundary conditions, but when you keep working with similar variables, but apply different operations to them based on condition, that is the perfect place for polymorphism and reducing the code complexity.

In the above case, the biggest problem is that all the code and logic is enclosed in a single method. So when a candidate presents me with this solution, the first thing I ask is what happens when we need to add another operation, like division or something. When the prompt answer is that we add an if condition, that is when I prompt and ask if there is not a cleaner solution, which would keep code separate. Finally, often, you depend on third party libraries for functionality. Well, in those cases, you won’t be able to edit the original source code, leaving you cursing the developer who wrote it for not allowing an extensible design.

The ideal answer would, for this question, be that Node is an interface with evaluate() and toString(). Then, we have different implementations of Node, like a ValueNode, an AdditionOperationNode, and so on and so forth. The implementations would look as follows :
interface Node {
int evaluate();
String toString();
}

public class ValueNode
implements Node {
private int value;
public int evaluate() {
return value;
}
public String toString() {
return value + "";
}
}

public class AdditionOperationNode
implements Node {
Node left, right;
public int evaluate() {
return left.evaluate()
+ right.evaluate();
}
public String toString() {
return left.toString() + " + "
+ right.toString();
}
}

You could go one step further and have an abstract base class for all operations with a Node left and right, but I would be well satisfied with just the above solution. Now, adding another operation is as simple as just adding another class with the particular implementation. Testing-wise, each class can be tested separately and independently, and each class has one and only one responsibility.

Now there are usually two types of conditionals you can’t replace with Polymorphism. Those are comparatives (>, <) (or working with primitives, usually), and boundary cases, sometimes. And those two are language specific as well, as in Java only. Some other languages allow you to pass closures around, which obfuscate the need for conditionals.

Of course, one might say that this is overkill. The if conditions don’t really make it hard to read. Sure, with the example above, maybe. But when was the last time you had just one level of nesting? Most times, these conditionals are within conditionals which are within loops. And then, every bit of readability helps. Not to mention there is a combinatorial explosion of the amount of code paths through a method. In that case, wouldn’t it be easier to test that the correct method is called on a class, and just test those individually to do the right thing?

So next time you are adding a conditional to your code, stop and think about it for a second, before you go ahead and add it in.

13 comments

  1. anonymous
    September 22, 2009 at 11:41 am

    I’d say that in this situation, it really is overkill, and it detracts from the readability and maintainability of the code as written.

    I’d beware drawing conclusions about how they approach a simple problem like this. I don’t think it’s necessarily a good thing if your first instinct as to how to represent and evaluate a tree of operations and values in memory is a tree of big objects inheriting from abstract “operation” and “operand” classes. It’s more or less overengineering.

    If you want to evaluate how well the candidate applies OO to big problems that actually deserve a proper object model, perhaps you could ask him to show you sample code he’s written previously illustrating such, and discuss the pros and cons of the abstractions he designed?

  2. argh
    September 22, 2009 at 3:13 pm

    Anytime I hear someone mention using polymorphism instead of conditionals, this is the example they give. The slight extension to this example is evaluating parse trees in an OO style compiler.

    Beyond those two examples (really just one example), I don’t know where else this technique is applicable. Most of the time a simple ‘if’ statement is much more concise and clear.

  3. September 22, 2009 at 5:03 pm

    [...] Using Polymorphism instead of conditionals when programming [...]

  4. [...] rest is here:  Using Polymorphism instead of Conditionals « The Shyam! SHARETHIS.addEntry({ title: "Using Polymorphism instead of Conditionals « The Shyam!", url: [...]

  5. greybeard
    September 22, 2009 at 8:15 pm

    @ argh

    The main reason for using polymorphism instead of conditionals/switch-cases is to be able to vary the logic based on discreet selectors. In this case, it’s operands in an expression tree, but in others it may be how to notify entities when an exception is encountered. Or what the proper way is to compute a cash disbursement based on potential receivers’ account status. These are just a couple of areas where this style can be applied.

    Of course, taken to the extreme, trivial logic ends up segregated from the main flow and readability can be negatively impacted. Like most things in the programming craft, there are tradeoffs to consider and all that lot.

    This example is very well covered in the book “Refactoring” by Fowler and Beck (IIRC). There are numerous techniques covered that can really help a developer decide when to use these kinds of approaches.

    HTH.

  6. September 22, 2009 at 9:29 pm

    Why not ask him to program it in the three different ways?

    1. Polymorphism
    2. Conditional statement
    3. Data-driven

    That would test his versatility, because there are times for each of them.

  7. September 23, 2009 at 7:09 am

    Shyam, this example doesn’t call for class polymorphism. It calls for genericity. Your goal is to instantiate several nodes, each with different `eval()` and `to_string()` functions. The simplest way is to treat these functions as ordinary member variables. To let them be parametrers of the `Node()` constructor.

    With this scheme, a `Node` is nothing more than a pair of functions : `eval()` and `to_string()`. You don’t even have to use inheritance. Sure, you still have to define `eval()` and `to_string()` for each case, so my solution looks hardly better than yours.

    Except when talking about the “step further” you mentioned. I can take this step easily, after the fact, without modifying anything: I just have to write functions which generate `eval()` or `to_string()` for subsets of all possible cases. Such a subset could be the binary operations. I just need to write a `Node gen_eval(Binary_op)` function or somthing.

    Parameter passing (here in a constructor) is a simple concept. Even when the “thing” being passed is a function, this is simpler than class polymorphism. The only reason the more complicated, less flexible approach was the right one here is because my approach is more verbose in mainstream OO languages.

    The simpler concept is more verbose. Kind of silly, don’t you think?

    • Shyam
      September 23, 2009 at 11:06 am

      I’m going to try to reply to all the comments in this one.

      @argh: greybeard addressed most of my points, but for an example other where it should have been used : http://code.google.com/p/js-test-driver/source/browse/trunk/JsTestDriver/src/com/google/jstestdriver/ui/CapturedBrowsersPanel.java. The contains method on line 80 here totally argues that it needs a FirefoxSlaveBrowser, IESlaveBrowser and it should ahve a getIcon rather than all this. The if conditional would totally go away, and I think it is more readable.

      @anonymous: When I ask such a question, I lay down a few requirements first, which I should have mentioned in the blog post. One is, I do tell them that initially we have a few operators, but there might be a need to add more later. And I do ask how it would be extensible in the sense that even if the source code is not directly available, you should be able to add an operation (this might be a later follow up after an initial iteration, of course).

      @Eric: For conditional statements, I have more interesting questions, which check his control structure flow. Something which involves both ifs and fors. for 3.) is an interesting idea, any suggestions or examples for that? I am not sure exactly what you are expecting there. Something else I love to ask is what makes classes and methods untestable, or give an example of a horridly untestable class including static initialization blocks and ask how they would test it.

      @Loup, I love it, except in Java, functions are not a first class citizen. I love closures, and I wish Java had them. But until then, we are stuck with this approach.

  8. September 23, 2009 at 11:03 am

    @Loup — I think you just implemented Eric’s #3. It works wonderfully in languages like Lisp or JavaScript where functions are first class objects.

    To comment on the post itself:

    I’m definitely adding this to my interviews, using Eric’s three methods!
    I actually wrote a much more complicated version of this when I implemented Leibnitz, my clone of Apple’s Graphing Calculator. Every item in the parse tree can not only evaluate itself, but also render itself. Addition and multiplication are actually N-ary, so a single node can sum or multiply an arbitrary number of values. This helps with rendering parentheses cleanly.

  9. Gowtham
    September 24, 2009 at 10:34 pm

    Also please note that the Design patterns books point at using Polymorphism just for very simple cases of if, else and switch statements as a switch case code smell, so I won’t do this unless I see atleast 2+ repetitions of same conditional. Doing it just for a single conditional would make it speculative generality.

  10. [...] with questions about pointers and functional programming, digging into a person’s understanding of encapsulation and polymorphism makes for a good technical [...]

  11. ktn
    November 8, 2009 at 6:27 pm

    Do you really find tech interviews consisting of algorithm-related questions? (like what, detail quicksort vs. bubblesort? various flavors of b-trees?)
    God, i hope this is an anomaly (i honestly can’t remember when I’ve actually implemented a new general algorithm); I can’t really think of a less insightful question.

    There are certainly times when closures are useful, but @Loup’s suggestion is certainly not one of them; there’s another important oo-concept, viz encapsulation, after all

  12. [...] is pretty much always going to result in cleaner code. Ways to achieve shallower nesting are using polymorphism instead of conditionals, extracting methods, or using method objects. GA_googleAddAttr("AdOpt", "1"); [...]

Leave reply

Back to Top