Missing level of technical depth (Flatten Tree)

I recently have given a coding test in a reputable IT company. There were three coding questions.

They refused me by saying that


as we felt they didn't demonstrate the level of technical depth we're seeking from candidates

Question 1 : Missing level of technical depth (Recursive to Iterative)

Question 3 : Missing level of technical depth (Common Ancestor)

and this is 2nd question.


Question 2:


Implement a method that, given a tree as a parameter, will return an
in order traversal of that tree. Your implementation should throw an
IllegalArgumentException if the tree is null. Your implementation must
implement the FlattenTree interface


For example a tree like:

/|\
1 | 6
 /|\
5 4 9

would result in the list [1,5,4,9,6]. Your class must be named flatten.MyFlattenTree

Answer 2:

```
package flatten;

/**
* A type which stores one of either of two types of value, but not both.
*
*/
public class Either {

/**
* Constructs a left-type Either
*/
public static Either left(A a) {
if (a == null) throw new IllegalArgumentException();
return new Either(a, null);
}

/**
* Constructs a right-type Either
*/
public static Either right(B b) {
if (b == null) throw new IllegalArgumentException();
return new Either(null, b);
}

private final A a;
private final B b;

private Either(A a, B b) {
this.a = a;
this.b = b;
}

/**
* Applies function f to the contained value if it is a left-type and returns the result. Throws an IllegalStateException if this is a right-type Either.
*/
public T ifLeft(Function f) {
if (!this.isLeft()) {
throw new IllegalStateException();
}
return f.apply(a);

}

/**
* Applies function f to the contained value if it is a right-type and returns the result. Throws an IllegalStateException if this is a left-type Either.
*/
public T i

For an interview question, I would consider this to be "Way Overkill". I'm going to assume it works (it looks functional), but it has a lot of abstraction that is not necessary.

Some of the significant items I see are:

-
Your Tree interface has an inner static-final class Leaf, and Node. I strongly object to interfaces that have embedded concrete implementations embedded... and the visibility of those implementations is suspect.... the Interface is public, but the inner static classes are only package-private (neither public nor private).

-
The 'Either' class is .... unnecesary, as with the Triple class.

as I look at that specification, and the code, I can't help but think you have missed the 'simple solution' that they were looking for.....

Now, the spec says: Your implementation must implement the FlattenTree interface

Did the spec include the interface for the Tree? If it did, that's horrible, and as a person being interviewed I would say the Tree interface was broken. If they jsut gave you the interface definition:

public interface FlattenTree {

    /**
     * 
     * @param tree the Tree to flatten
     * @return a list containing all the leaf values in t, in left-to-right order
     * @throws IllegalArgumentException if t is null
     */
    List flattenInOrder(Tree tree);

}

... and it is up to you to define the Tree, then the code would simply be:

public class Tree {

    private class Node {
        private Node left, mid, right;
        T value;
        Node(Node left, Node mid, Node right, T value) {
            this.left = left;
            this.mid = mid;
            this.right = right;
            this.value = value;
        }
    }

    private final Node root;

    .... constuctors 

    public List getLeafNodeValues() {
        List toreturn = new ArrayList<>();
        recurseLeafNodeValues(root, toreturn);
        return toreturn;
    }

    private void recurseLeafNodes(Node node, List result) {
        if (node == null) {
            return;
        }
        if (node.left == null && node.mid == null && node.right == null) {
            result.add(node.value);
        }
        recurseLeafNodes(node.left,  result);
        recurseLeafNodes(node.mid,   result);
        recurseLeafNodes(node.right, result);
    }

}

and your interface implementation would be:

public class MyFlattenTree implements FlattenTree {

    public List flattenInOrder(Tree tree)   {    
        if (tree == null) {
             .... complain
        }
        return tree.getLeafNodeValues();
    }
}

Note, the recursion is clear, the decision making in the recursion is clear. There are no Function instances, no Eithers ... either, etc.

The problem is conceptually simple, but all I see is over abstraction. What is unclear is whether it was you who introduced it, or the interviewers.

StackExchange Code Review Q#51545, answer score: 3