6
\$\begingroup\$

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<A,B> {

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

    /**
     * Constructs a right-type Either
     */
    public static <B> 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> T ifLeft(Function<A,T> 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> T ifRight(Function<B,T> f) {
        if (this.isLeft()) {
            throw new IllegalStateException();
        }
        return f.apply(b);

    }

    /**
     * @return true if this is a left, false if it is a right
     */
    public boolean isLeft() {
        return b == null;
    }

}

package flatten;

import java.util.List;

public interface FlattenTree<T> {

    /**
     * 
     * @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<T> flattenInOrder(Tree<T> tree);

}

package flatten;

public interface Function<P, R> {

    R apply(P p);
}

package flatten;

public interface Tree<T> {

    Either<T, Triple<Tree<T>>> get();


    static final class Leaf<T> implements Tree<T> {

        public static <T> Leaf<T> leaf (T value) {
            return new Leaf<T>(value);
        }

        private final T t;

        public Leaf(T t) {
            this.t = t;
        }

        @Override
        public Either<T, Triple<Tree<T>>> get() {
            return Either.left(t);
        }
    }

    static final class Node<T> implements Tree<T> {
        public static <T> Tree<T> tree (T left, T middle, T right) {
            return new Node<T>(Leaf.leaf(left), Leaf.leaf(middle), Leaf.leaf(right));
        }

        private final Triple<Tree<T>> branches;

        public Node(Tree<T> left, Tree<T> middle, Tree<T> right) {
            this.branches = new Triple<Tree<T>>(left, middle, right);
        }

        @Override
        public Either<T, Triple<Tree<T>>> get() {
            return Either.right(branches);
        }
    }
}

package flatten;

/**
 * A type that stores three values of the same type.
 */
public class Triple<V> {

    private final V l, m, r;

    public Triple(V l, V m, V r) {
        this.l = l;
        this.m = m;
        this.r = r;
    }

    public V left() {
        return l;
    }

    public V middle() {
        return m;
    }

    public V right() {
        return r;
    }

}

package flatten;

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

public class MyFlattenTree<T> implements FlattenTree<T> {


    public List<T> flattenInOrder(Tree<T> tree)   {
        if (tree == null)
                throw new IllegalArgumentException("Tree is null.");

            if (tree.get().isLeft()) {

                return Arrays.asList(tree.get().ifLeft( new Function<T, T>() { 

                    public T apply(T p) {
                        return p;
                    }

                } ));

            } else {
                return tree.get().ifRight( new Function<Triple<Tree<T>>, List<T>>() {

                            public List<T> apply(Triple<Tree<T>> p) {

                                List<T> nodes = new ArrayList<T>();
                                nodes.addAll(flattenInOrder(p.left()));
                                nodes.addAll(flattenInOrder(p.middle()));
                                nodes.addAll(flattenInOrder(p.right()));

                                return nodes; //return all fetched nodes
                            }
                    } );

            } //end if

    } //end function


    public static void main(String[] args)
    {
        Tree<Integer> nodes = Tree.Node.tree(5, 4, 9);
        Tree<Integer> root = new Tree.Node<Integer>(Tree.Leaf.leaf(1), nodes, Tree.Leaf.leaf(6));
        MyFlattenTree<Integer> myFlattenTree = new MyFlattenTree<Integer>();

        System.out.println("Flattened tree: " + myFlattenTree.flattenInOrder(root));
    }
}
\$\endgroup\$

3 Answers 3

3
\$\begingroup\$

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<T> {

    /**
     * 
     * @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<T> flattenInOrder(Tree<T> tree);

}

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

public class Tree<T> {

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

    private final Node<T> root;


    .... constuctors 

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

    private void recurseLeafNodes(Node<T> node, List<T> 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<T> implements FlattenTree<T> {

    public List<T> flattenInOrder(Tree<T> 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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ I had the same question for an interview. The following classes were provided - Tree, Either, Triple, FlattenTree, Function. Only the implementation was to be added \$\endgroup\$
    – Jay
    May 24, 2014 at 12:30
  • \$\begingroup\$ I suspect the provided interfaces are intentionally "quirky" so as to greatly reduce the chances a candidate can simply find some open-source implementation that fits the spec and copy/paste or otherwise replicate. \$\endgroup\$
    – gb96
    Nov 28, 2014 at 1:29
3
\$\begingroup\$

Which classes did you write? It looks like you wrote MyFlattenTree because the formatting and style is different from the other classes and interfaces.

So given that you have to use these classes, there isn't much of a choice of implementation. One issue is that creating a new ArrayList for each recursive call gives quadratic performance for the worst-case (unbalanced tree). You can add another method that takes a set as a parameter to add the items to.

\$\endgroup\$
2
\$\begingroup\$

Note that in your implementation of flattenInOrder the if-clause if (tree.get().isLeft()) always returns, consequently the following else is redundant and you should move the code in the else block outside (see code below).

Also note that the interface Function is pretty much java.util.function.Function provided in Java 8, so if you want to impress a potential employer for a Java job, learn and use Java 8 features wherever you can to demonstrate that you're technically at the forefront!

The following is your solution with the following changes:

  1. Java 8 Lambda expressions
  2. Added @Override annotation
  3. Removed unnecessary //end comments
  4. Removed redundant "else"
  5. Added final modifier where possible

/*
 * @see flatten.FlattenTree#flattenInOrder(flatten.Tree)
 */
@Override
public List<T> flattenInOrder(final Tree<T> tree) {
    if (tree == null)
        throw new IllegalArgumentException("Tree is null.");

    if (tree.get().isLeft()) {
        // Java 8:
        return Arrays.asList(tree.get().<T> ifLeft(p -> p));
    }
    return tree.get().ifRight(p -> {

        final List<T> nodes = new ArrayList<>();
        nodes.addAll(flattenInOrder(p.left()));
        nodes.addAll(flattenInOrder(p.middle()));
        nodes.addAll(flattenInOrder(p.right()));

        return nodes; // return all fetched nodes
    });
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.