Shyam has posted 8 posts at DZone. You can read more from them at their website. View Full User Profile

Using Polymorphism instead of Conditionals

09.25.2009
| 9048 views |
  • submit to reddit
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.

References
Published at DZone with permission of its author, Shyam Seshadri. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Artur Biesiadowski replied on Fri, 2009/09/25 - 10:40am

When you will be going for interview yourself, you will meet a guy, who given 3rd solution will scream "You have no clue about patterns" and start complaining why you are not considering having more than one type of string representation, why hardcode evaluate() and toString(), but not for example typeCheck() etc and will only accept Visitor pattern as proper answer. (with separate visitor for evaluation and toString, with nodes holding only the data, without actual behaviour).

 

Stevi Deter replied on Fri, 2009/09/25 - 11:15am

Since you present this as an interview question you use, I'm curious how successful has it been for you?

Mladen Girazovski replied on Fri, 2009/09/25 - 11:51am

The first time i saw somebody replacing conditionals with polymorphism was in Fowlers Book about refactoring, i think (but not too certain) it was also used in a composite.

Here is another example: http://www.youtube.com/watch?v=4F72VULWFvc

 

Jilles Van Gurp replied on Fri, 2009/09/25 - 12:07pm

The flip side of the coin is that sometimes things are just really simple and introducing lots of interfaces and classes to solve a simple problem is maybe just overengineering. Reinventing the wheel is often a side effect BTW. And I wouldn't want people to spend time on parsers, evaluating trees, and other stupid low level stuff that has long been automated for us. 5x the number of classes is also 5x the number of unit tests to write and 5x the number of classes to document, understand, etc. Complexity is a necessary evil and not a goal.

But I see where you are going. The real issue with conditionals is BTW testability. Having lots of branches in one method means that you have a lot of ground to cover in your unit test for that method (and essentially you're looking at a combinatorial explosion of possibilities here). You can easily recognize the junior programmer by class and method length measured in LOC. Simply put classes and methods with low cohesian and high coupling are difficult to test, maintain, understand and easy to break.

Testable code is all about keeping things simple and proper use of design patterns, dependency injection, etc which facilitate that, naturally leads to code that is really easy to test. 

For that reason I regard having lots of returns, breaks, throws, etc. in a method as huge code smell because I know the unit test is going to suck in either coverage or complexity, both of which will kill you when you need to refactor (and that's really a when and not a if as I'm sure we all know).

Andrew Arrigoni replied on Fri, 2009/09/25 - 3:49pm

Are you including such things as enforcing proper order of operations? ( and )? Or is thinking that far just bonus points? :)

Ray Walker replied on Fri, 2009/09/25 - 4:42pm

Admittedly it is cleaner looking from an initial development and development extensibility standpoint, but not from a troubleshooting and memory footprint standpoint. You're using twice the memory as the initial "conditional" example. Further, you're moving each possibility away in proximity (in the source) because you have a unique class for every possible mathematical operation. The maintainer has to chase each one down rather than just having them all in one place. Additionally, overloading is not really polymorphism and that point is missing here. Your solution requires your users to have to instantiate a different class for every type of operation then want to evaluate. If it were truly polymorphic, you'd have a base class and factory method that everyone instantiates and interfaces with requiring no specialized knowledge of what kind of evaluation object it was going to get. Your solution is the basis for a major proliferation of classes especially if I start adding calculus operators. A maintenance nightmare. I applaud your effort, and, again, it does look cleaner, so point well taken, but at what cost to the machine's memory usage? And at what cost to the one that has maintain the explosion of classes added to cover all the mathematical operators?

Eran Harel replied on Sat, 2009/09/26 - 6:54am

I believe you just failed the interview @Retromingent.

If you are going to implement a driver, a real-time peace of code, or some software that is to run on some mini device, then it makes sense to think about the memory footprint of a ValueNode instance.

In most cases, (at least for enterprise software) maintainability is much more important. My experience shows that when developers perform premature optimizations, they fail miserably - later on someone comes and replaces their code with a clean implementation like presented above, and the performance actually improves... lesson learned.

Philippe Lhoste replied on Sat, 2009/09/26 - 3:54pm

@StormTAG: You are not paying attention. The nodes are already in a tree, ie. they are already ordered with regard to operator priorities, or changes of such priorities given by usage of parentheses.

Building the tree is said to be outside of the scope of the exercice.

I appreciate the lesson: I come from a procedural world, I had hard time to grasp the OO concepts, and even if I think I am starting to grasp them, I still tend to think procedurally, sometime.

And I am not alone, when I see the code I work on daily... :-D

@Retromingent: Excuse me, but I don't see how it consumes twice the memory. Somehow, it might even consume less memory, as it doesn't store the operator symbol...

jeroen dijkmeijer replied on Sun, 2009/09/27 - 5:22am

I probably would answer that java is a suboptimal language for solving these types of problems. Scala is better fit for problems like this. An example on the world wide web is here

 

Sreenivasa Majji replied on Sun, 2009/09/27 - 2:49pm

As dr_jerry said, is Scala, Erlang solve the problem better than Java? It's a good interview question for a candidate fresh out of college, but any experienced person will tell you that existing API/Tools solve this kind of problem unless you are creating a new language.

Jeroen Wenting replied on Mon, 2009/09/28 - 4:54am

Anyone stating that "Scala is better" automatically fails the interview for me. Maybe Scala is indeed better, but I wasn't asking about Scala, I was asking about Java (or maybe C++). MAYBE if he qualified his answer, stating exactly why in his opinion Scala might be a better solution, he'd get a break and get told to implement it in Java anyway as that's what he's been told to use, but that's about it.
Maintainability again. We have a lot of people (and so do our customers to whom we supply coding services) who have Java expertise, noone uses Scala in the real world.
Also, I'd expect the first answer from people as it's the first thing that would enter your mind. It's after all a standard tree traversal system everyone gets taught in programming 101. Only after building that and thinking about the consequences for a bit (time you're not typically granted in an interview) will most people come up with a polymorphic solution (and I'd take that abstract base class as not just the "perfect" but the only solution, I love the things).

Erin Garlock replied on Mon, 2009/09/28 - 3:58pm

Assume a balanced binary tree of depth 3 -> 2^3 - 1 = 7 total nodes, 4 of which are leaf nodes (value/int).  (Note that the word "node" used above does not mean "class Node")  An example equation would be:  4*3+5*6 = 42

Assume in implementation 1, there are only 4 possible math operations (+-*/), iterated through in the listed order (+-*/)

In implementation 1 there are the following metrics:

3 calls to evaluate() [2^(n-1) - 1]

3 math operations [2^(n-1) - 1]

13 if() evaluations [(2+(x/2))*(2^(n-1)-1)]  where x = the number of math operations supported and x/2 is the average seekto find the correct operation.

In  implementation 2  there are the following metrics:

7 calls to evaluate() [2^n - 1]

3 math operations [2^(n-1) - 1]

0 if() evaluations

 

Which is more efficient?  Lets change the equation to 40/4/5/2 = 1


Implementation 1:

3 calls to evaluate()

3 math operations

18 if() evaluations (division is the 4th math operation in the big if/else) (added 5 more if() operations)

Implementation 2

7 calls to evaluate()

3 math operations

0 if() evaluations

 

So which is faster?  1 call to evaluate() or [2+x/2] if() evaluations?  Look out if all your math operations happen to fall at the bottom of the if/else list or your if/else list is large!!

Erin Garlock replied on Mon, 2009/09/28 - 10:24am

Correction on the second equation: (40/4)/(10/2) = 2  (the original 40/4/5/2 = 1 isn't binary balanceable and order of operations IS important.  The metrics presented match the corrected equation.

Andrew Arrigoni replied on Mon, 2009/09/28 - 11:22am in response to: Philippe Lhoste

@Phillippe Lhoste: You're making the assumption that they are in the correct order in the tree with regard to operator priorities, which is fine. In an interview, however, I'd rather ask the question. :)

 

Ray Walker replied on Mon, 2009/09/28 - 12:12pm in response to: Eran Harel

Ouch! While your point is well taken, the lack of optimization is a foregone conclusion (ie., intuitively obvious) and so not an on-the-fly optimization or my opinion. (I cited a memory inefficiency that is provable, and a bad practice that is also provable.) But you are right about premature optimizations--they do tend to be wrong. A point I make regularly myself. My point was really about the true usage of these coding exercises. Demonstrating knowledge in one thing, but demonstrating insight into the its efficiency, being able to prove it, are signs of not just text-book knowledge but familiarity. If you've already done this time and time again (which I have), then you already know the consequences.

John Liptak replied on Mon, 2009/09/28 - 6:20pm

There are more basic questions to ask before getting to a solution. The biggest one I've not seen addressed is the type of the values (integer, real, complex, etc.).
I would not recommend going to a full Visitor double dispatch solution unless you have to deal with differing types.
Again, those are good follow up questions I would expect in reply to the question.

C0dep0et P U replied on Tue, 2009/09/29 - 12:20am

Do you give your candidates a computer and ask them to code up the solution or do you ask them to think in front of a white board with you watching over them? Do you think it might have any difference if he were allowed to code it out on a machine in the language of his choice?

I think people programmers tend to get into a flow while they are actually keying out code. While the white board can be used to check and display some high level concepts, draw out a high-level architecture (that might be difficult to put into words),if you are actually asking people to do domain modelling, asking them to do it on a machine would be much fairer to them.

I am from an upfront design world, and I have experienced how difficult it might be to sit and come up with a  flaw-less design in UML, but once I switched to agile I realized why it actually works. It works because you continuously refactor your code to arrive at the best Object oriented solution. You seldom start off with the best one.

Now when on the job, you expect this to be a natural work-flow, why expect the candidates to bang out the best solution on the white board? (I am assuming  that you are providing him only with a white board, if not I take back my comments)

Erin Garlock replied on Tue, 2009/09/29 - 7:25am

The idea of the interview question isn't to come up with the "best" possible solution.  The question is designed to ferret out how the candidate thinks about problems. 

I've had so many candidates that look great on paper but are terrible at conveying ideas in the interview.  Perhaps it's just me and my interviewing style, but if you can't convey thoughts, especially when the format & expectations of an interview should be well understood, I really am not interested in hiring the person.  To me hiring a clear communicator with decent programming skills is much more valuable than hiring a superb programmer with terrible communication skills.

If initially given a solution like implementation #1, I'd ask if they could do it in a polymorphic way.  I think it's a fair compromise since interviews tend to be stressful, particularly for newer programmers.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.