Practice, Practice, Practice

I spent several hours last week interviewing Java developers. We needed to bring in some contractors. It was decided that we'd ask candidates to write some Java code as part of the interview process. We had a list of twenty quiz questions that ranged in difficulty. Since our time was limited, we'd restrict ourselves to one or two quiz questions per candidate.

I had mixed feelings about the quiz questions. I'm familiar with Joel Spolsky's Guerrilla Guide to Interviewing. I didn't want to be a Quiz Show Interviewer.

But there was something else nagging me. How would I fare if presented with this quiz?

One of the questions was: "Traverse a binary tree in depth-first order." I'd bet that anybody fresh out of a good data structures class would be able to whip this out quickly enough to be able to fit into the scope of a 30 minute phone conversation.

But what about a guy like me?

The only data structure I was taught as a mechanical engineer was a FORTRAN array. I was keenly aware of my ignorance when I started down the software path, so I did what I always do: sign up for a degree and start taking courses. I started down the path of an Master of Science degree in computer science. It included basics like data structures, but they taught it using Eiffel. And that was ten years ago. I'd have to dredge up those memories and express them in Java.

Even worse, I've been working as an architect for years now. The big firms that employ me tend to take a dim view of architects that write code. Programming is considered a low level, commodity, low skill task that's best left to the least expensive off-shore individuals you can find.

It made me nervous to think about how foolish I'd look taking my own interview.

So I started working through the interview questions, one by one. I spent some time this weekend on that binary tree implementation. I got through it using all the best practices I knew: Java, test driven development using TestNG, IntelliJ and refactoring, etc. It took more than thirty minutes to finish, but I'm pleased with the result. I am not fast, but I think I'm conscientious and thorough.

Practice will help with my speed. Part of the value of this exercise is to practice, practice, practice. Individuals that I have a great deal of respect for advocate the concept of constant practice, calling it code kata.

I think it's especially important for someone with "architect" in their job title. How on earth can you represent for "best practices" when you're so woefully out of practice yourself?

The other benefit? It's fun and satisfying. There's still a great sense of satisfaction, of an aesthetic for mathematical beauty, whenever I manage to pull myself through whatever rabbit hole I've fallen into. There's frustration, too, when I struggle and fall and fail. But when it works, there's nothing like it.

It's no different from any other profession. We all have to keep learning, struggling, adding new skills, re-sharpening old ones.

If you're not a programmer, you can stop reading here. (Thank you for coming at all and getting this far.)

If you are a programmer, and you're still interested, here's my solution to the first part of the problem: a binary tree in Java. I started with a Node class that encapsulated a value plus left and right child references:

package tree;

public class Node<T extends Comparable<T>>
implements Comparable
{
private T value;
private Node<T> left;
private Node<T> right;

public Node(T value)
{
this(value, null, null);
}

public Node(T value, Node<T> left, 
Node<T> right)
{
this.setValue(value);
this.left = left;
this.right = right;
}

public T getValue()
{
return value;
}

public void setValue(T value)
{
if (value == null)
throw new IllegalArgumentException("node value 
cannot be null");

this.value = value;
}

public Node<T> getLeft()
{
return left;
}

public void setLeft(Node<T> left)
{
this.left = left;
}

public Node<T> getRight()
{
return right;
}

public void setRight(Node<T> right)
{
this.right = right;
}

public boolean isLeaf()
{
return ((this.left == null) && 
(this.right == null));
}

public int compareTo(Object o)
{
Node<T> other = (Node<T>) o;

return this.getValue().compareTo(other.getValue());
}

@Override
public boolean equals(Object o)
{
if (this == o)
{
return true;
}
if (o == null || getClass() != o.getClass())
{
return false;
}

Node node = (Node) o;

if (!value.equals(node.value))
{
return false;
}

return true;
}

@Override
public int hashCode()
{
return value.hashCode();
}

@Override
public String toString()
{
return value.toString();
}
}

Of course I wrote a TestNG class to unit test it:

package tree;

import static org.testng.Assert.*;
import org.testng.annotations.Test;

@Test
public class NodeTest
{
/**
* For any non-null reference value x, x.equals(null) 
* must return false.
*/
public void testNotNull()
{
Node<String> x 
= new Node<String>("test");

assertFalse(x.equals(null));
}

/**
* It is reflexive: For any reference value x, 
* x.equals(x) must return true.
*/
public void testReflexive()
{
Node<String> x 
= new Node<String>("test");

assertTrue(x.equals(x));
assertEquals(0, x.compareTo(x));
}

/**
* It is symmetric: For any reference values x and y, 
* x.equals(y) must return
* true if and only if y.equals(x) returns true.
*/
public void testSymmetric()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("something else");

assertTrue(x.equals(y) && y.equals(x));
assertTrue((x.compareTo(y) == 0) 
&& (y.compareTo(x) == 0));
assertFalse(x.equals(z));
assertTrue(x.compareTo(z) > 0);
}

/**
* It is transitive: For any reference values x, y, 
* and z, if x.equals(y) returns
* true and y.equals(z) returns true, 
* then x.equals(z) must return true
*/
public void testTransitive()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("test");

assertTrue(x.equals(y) && 
y.equals(z) && 
z.equals(x));
assertTrue((x.compareTo(y) == 0) && 
(y.compareTo(z) == 0) && 
(z.compareTo(x) == 0));
}

public void testHashCode()
{
Node<String> x 
= new Node<String>("test");
Node<String> y 
= new Node<String>("test");
Node<String> z 
= new Node<String>("something else");

assertTrue(x.hashCode() == y.hashCode());
assertFalse(x.hashCode() == z.hashCode());
}

public void testToString()
{
String expected = "expected";

Node<String> node 
= new Node<String>(expected);
assertEquals(node.toString(), expected);
}

@Test(expectedExceptions = NullPointerException.class)
public void testCompareToNull()
{
Node<String> x 
= new Node<String>("test");

x.compareTo(null);
}

public void testCompareTo()
{
Node<String> x 
= new Node<String>("x");
Node<String> y 
= new Node<String>("y");
Node<String> z 
= new Node<String>("z");

assertTrue((x.compareTo(x) == 0) && 
(x.compareTo(y) <  0) && 
(x.compareTo(z) <  0));
assertTrue((y.compareTo(x) >  0) && 
(y.compareTo(y) == 0) && 
(y.compareTo(z) <  0));
assertTrue((z.compareTo(x) >  0) && 
(z.compareTo(y) >  0) && 
(z.compareTo(z) == 0));
}

@Test(expectedExceptions = IllegalArgumentException.class)
public void testNullValue()
{
Node<String> x   
= new Node<String>(null);
}

public void testIsLeaf()
{
Node<String> x 
= new Node<String>("test");

assertTrue(x.isLeaf());

x.setLeft(new Node<String>("left"));
x.setRight(new Node<String>("right"));

assertFalse(x.isLeaf());

assertEquals("left", x.getLeft().getValue());
assertEquals("right", x.getRight().getValue());
}
}

Then I wrote a BinaryTree:

package tree;

import java.util.Arrays;
import java.util.List;

public class BinaryTree<T 
extends Comparable<T>>
{
private Node<T> root;

public BinaryTree()
{
this(null);
}

public BinaryTree(Node<T> root)
{
this.root = root;
}

public Node<T> getRoot()
{
return this.root;
}

public boolean contains(T value)
{
return contains(this.root, value);
}

private boolean contains(Node<T> node, T value)
{
// empty tree can't contain the value; value 
// cannot be null
if ((node == null) || (value == null))
{
return false;
}

if (value.equals(node.getValue()))
{
return true;
}
else if (value.compareTo(node.getValue()) < 0)
{
return contains(node.getLeft(), value);
}
else
{
return contains(node.getRight(), value);
}
}

public void insert(T value)
{
this.root = insert(this.root, value);
}

public void insert(List<T> values)
{
if ((values != null) && 
(values.size() > 0))
{
for (T value : values)
{
insert(value);     
}
}
}

public void insert(T [] values)
{
if ((values != null) && 
(values.length > 0))
{
insert(Arrays.asList(values));
}
}
private Node<T> insert(Node<T> node, 
T value)
{
if (node == null)
{
return new Node<T>(value);
}
else
{
if (value.compareTo(node.getValue()) < 0)
{
node.setLeft(insert(node.getLeft(), value));
}
else
{
node.setRight(insert(node.getRight(), value));           
}
}

return node;
}

public int size()
{
return size(root);
}

private int size(Node<T> node)
{
if (node == null)
{
return 0;
}
else
{
return (size(node.getLeft()) + 
1 + 
size(node.getRight()));
}
}

public int height()
{
return height(root);
}

private int height(Node<T> node)
{
if (node == null)
{
return 0;
}
else
{
int leftHeight = height(node.getLeft());
int rightHeight = height(node.getRight());

return (Math.max(leftHeight, rightHeight) + 1);
}
}

public boolean isEmpty()
{
return (root == null);
}
}

And a TestNG unit test:

package tree;

import static org.testng.Assert.assertFalse;
import static org.testng.Assert.assertTrue;
import static org.testng.AssertJUnit.assertEquals;
import org.testng.annotations.BeforeTest;
import org.testng.annotations.Test;

import java.util.Arrays;
import java.util.List;

@Test
public class BinaryTreeTest
{
private BinaryTree<Integer> tree;
private Integer [] data = { 5, 3, 9, 1, 4, 6, };

@BeforeTest
public void setUp()
{
tree = new BinaryTree<Integer>();
tree.insert(data);
}

public void testIsEmpty()
{
assertFalse(tree.isEmpty());
assertTrue(new BinaryTree<Integer>().isEmpty());
}

public void testSize()
{
assertEquals(tree.size(), data.length);
}

public void testHeight()
{
int expected = 3;
assertEquals(tree.height(), expected);
}

public void testGetRoot()
{
Node<Integer> expected 
= new Node<Integer>(data[0]);
assertEquals(tree.getRoot(), expected);
}

public void testContains()
{
for (int value : data)
{
assertTrue(tree.contains(value));
assertFalse(tree.contains(value*1000));
}
}

public void testInsertList()
{
// When you insert a list, you get it back without 
// alteration using a pre-order, depth-first traversal.
List<String> data 
= Arrays.asList("F","B","A","D","C","E","G","I","H");
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

// Check the size
assertEquals(tree.size(), data.size());

// Now check the values
BinaryTreeIterator<String> iterator 
= new DepthFirstIterator<String>(tree);
int i = 0;
while (iterator.hasNext())
{
assertEquals("i = " + i, iterator.next(), 
data.get(i++));
}
}

public void testInsertArray()
{
// When you insert a list, you get it back without 
// alteration using a pre-order, depth-first traversal.
String [] data = {"F","B","A","D","C","E","G","I","H",};
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), data.length);     

BinaryTreeIterator<String> iterator 
= new DepthFirstIterator<String>(tree);
int i = 0;
while (iterator.hasNext())
{
assertEquals("i = " + i, iterator.next(), 
data[i++]);     
}
}

public void testInsertNullList()
{
List<String> data = null;
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), 0);
}

public void testInsertNullArray()
{
String [] data = null;
BinaryTree<String> tree 
= new BinaryTree<String>();
tree.insert(data);

assertEquals(tree.size(), 0);
}
}

This was the ground work. The real solution meant writing iterators to traverse the BinaryTree. If you're reading closely, you'll see that I used a DepthFirstIterator in the unit test for BinaryTree.

I'll post those next time. In the meantime, I'll keep practicing.