The code is shown in Java - but the two styles are applicable to any object-oriented programming language.
The problem to solve
The problem is a slightly reduced version of the parsing part of this robot blocks programming contest problem. To slightly reduce the problem I just use the first two commands and treat the input as a string rather than a file.
Therefore, the problem is to parse input that looks like this:
10 move 4 over 3 move 3 onto 5 quiti.e. the first line is the number of blocks (used to set up the robot), the last line is "quit" (that's just how the input is - has no effect on the robot) and the lines in between are commands (each line is one command, e.g. "move over" is a single command with two parameters, the source block and the destination block).
No validation is needed - the input will always be well formed - there are no tricks in the question - it is as it looks.
The input will be used to control a robot. You can come up with whatever api you want - you can treat it as if you will be implementing the robot at some point too.
Now your turn
Please have a go at implementing this in Java or a similar language - (parsing input like that shown) - allow a maximum of one hour. If you have any questions about the problem, take the answer as being whatever makes it simplest - there are no tricks to this.
What did you end up with?
I've seen a lot of solutions to this over the last year. That is because I've been doing a lot of interviewing for my client (using the best interview question) and have used this example many times.
What most people end up with
Here's a solution in the most popular style:
package com.oocode;
import static java.lang.Integer.parseInt;
import java.util.ArrayList;
import java.util.List;
import com.oocode.Command.Type;
public class RobotParser {
private final int numberOfBlocks;
private final List
and:package com.oocode;
public class Command {
private final int sourceBlock;
private final int destinationBlock;
private final Type type;
public Command(int sourceBlock,
int destinationBlock,
Type type) {
this.sourceBlock = sourceBlock;
this.destinationBlock = destinationBlock;
this.type = type;
}
public enum Type {
MOVE_OVER,
MOVE_ONTO
}
public int getSourceBlock(){
return sourceBlock;
}
public int getDestinationBlock(){
return destinationBlock;
}
public Type getType() {
return type;
}
}
This is a decent representative of this style. I've chosen a shortish variation of the style to keep down the amount of code you have to wade through (although it could have been slightly shorter still if I'd parsed the command type using the enum). A popular variation is to have a Command interface and different implementations for MoveOverCommand and MoveOntoCommand. One thing that is quite nice about the problem is that there is scope in the solutions for showing different programming style and taste.
As far as the "two styles" that I'm talking about, the important feature is that the RobotParser has getters for the numberOfBlocks and the Commands, which are NoJos.
An alternative solution
Hardly anyone implements this alternative style:
package com.oocode;
import static java.lang.Integer.parseInt;
public class RobotParser {
private final Robot robot;
public RobotParser(Robot robot) {
this.robot = robot;
}
public void parse(String input) {
String[] lines = input.split("\n");
int numberOfBlocks = parseInt(lines[0]);
robot.setNumberOfBlocks(numberOfBlocks);
for (int i = 1; i < lines.length - 1; i++) {
String line = lines[i];
String[] parts = line.split(" ");
int sourceBlock = parseInt(parts[1]);
int destinationBlock = parseInt(parts[3]);
if(parts[2].equals("over")) {
robot.moveOver(sourceBlock, destinationBlock);
} else {
robot.moveOnto(sourceBlock, destinationBlock);
}
}
}
}
and:
package com.oocode;
public interface Robot {
void moveOver(int sourceBlock, int destinationBlock);
void moveOnto(int sourceBlock, int destinationBlock);
void setNumberOfBlocks(int numberOfBlocks);
}
A variation of this would be to have a RobotFactory which creates a Robot for a given number of blocks, to prevent the possibility of command methods being called before "setNumberOfBlocks". I would expect the implementation to use a BufferedReader if it were reading from a file rather than a string input. As before, I've gone for a short variation of this style.
In this style, the important feature is that there are no getters, and no Command class or classes. You could possibly describe this solution as being an example of "tell don't ask".
And finally ...
Most of the solutions I have seen to the problem have been during interviews that I have conducted. During these interviews, most solutions are the first style and hardly any of the second style.
I don't know whether the popularity of the first style is skewed by it being an interview situation, by the demographics of the people I am interviewing or for some other reason. Most of the interviewees didn't use TDD but did write automated unit tests after the code. However, the majority of those using TDD still produced the first style.
What do you think? What would you do? Which style is "better"? Is that a valid question? If you come up with a different solution that you think is interesting then please put a comment with a link to your blog - please don't paste code in your comments or they will get too long and probably won't format well anyway.
I'm looking forward to seeing something completely different - regex anyone? I don't know - I'm sure there are other styles but the first one shown is, by far, the one I have seen most often when interviewing for Java developers. (And, of course, different languages could produce completely different styles).
And finally - does anyone have good names for these two styles (maybe "getter style" vs "doer style")?
Copyright © 2009 Ivan Moore
6 comments:
Hi Ivan, I realise I am going off on a tangent, but you may still find this interesting...
One thing that struck me is that although it is true that the two systems are written in two very different styles, if you look at the systems from the point of view of their extensibility, then both systems make it easy to add new Robots, but hard to add new Commands. This is because in Open Closed Principle terms, they are closed against the addition of Robots, but not against the addition of Commands, i.e. when you add a new Robot, you just write new code (the code for the new Robot):
+ ShinyNewRobot implements Robot
+ {
+ public void moveOver(...){...}
+ ...
+ public void moveOnto(...){...}
+ }
but when you add a new command, you have to change existing code, i.e. every Robot (to implement the new command).
IronMan implements Robot
{
public void moveOver(...){...}
public void moveOnto(...){...}
+ public void moveInANewWay(...){...}
}
...
Terminator implements Robot
{
public void moveOver(...){...}
public void moveOnto(...){...}
+ public void moveInANewWay(...){...}
}
This works well if you know you won't be adding new commands but may have to add new robots.
If things are the other way round however you may want to reorganise the systems so that they are closed against the addition of new commands. To do this, you move the robot movement logic into the commands:
MoveOver implements Command
{
public void moveIronMan(){...}
public void moveTerminator(){...}
}
MoveOnto implements Command
{
public void moveIronMan(){...}
public void moveTerminator(){...}
}
Now it is easy to add a new command (because you are writing new code, not changing existing code):
+ FancyNewCommand implements Command
+ {
+ public void moveIronMan(){...}
+ public void moveTerminator(){...}
+ }
but hard to add a new Robot (because you have to change existing code):
MoveOver implements Command
{
public void moveIronMan(){...}
public void moveTerminator(){...}
+ public void moveShinyNewRobot(){...}
}
MoveOnto implements Command
{
public void moveIronMan(){...}
public void moveTerminator(){...}
+ public void moveShinyNewRobot(){...}
}
Having to choose between making it easy to add new Robots or to make it easy to add new Commands, is an instance of what Puig calls 'The Spreadsheet Conundrum' (see Prefactoring ) , and which moffdb explains here .
I have looked a bit more at the maintainability of the two systems you described.
Because I have to show a bit of code, I have put the rest of this comment here.
I suspect that the style that your candidates choose will be sensitive to exactly how you word the requirement. If you start by saying "the problem is to parse input that looks like this" then you'll get style 1. If you say "the problem is to feed input like this to a robot" then you're more likely to get style 2. I think a (really) good (or suspicious) candidate might push back a bit on the requirement, asking stuff like "Do you need to do anything else with the result of the parsing apart from drive the robot right now?"
It seems to me the first style builds an abstract syntax tree, which is how parsers and compilers are usually tought in school, while the other interprets the commands directly.
Now, with your requirements an AST isn't really needed, but it would still be my first shot because this is how I am used to thinking about parsing.
In a real compiler, you would want to do more analysis on the AST before intepreting it (error-checking, optimisations, register allocations etc).
On the other hand, this code looks more like assembly than high level code, so maybe comparing this question to a compiler might not be appropriate.
Hi Philip,
Many thanks for your interesting comments. In pairing interviews, try to frame the question such that I'm looking for a simple clean solution just to the problem as set. Your comments make me think I should also ask candidates to describe the dimensions in which their solutions are more or less easy to extend.
Hi Ivan,
Nat Pryce has recently posted an article that discusses the Message Obsession and Primitive Obsession code smells. Whilst not exactly an answer to your question, it might be interesting to a reader of this post.
http://natpryce.com/articles/000816.html
Post a Comment