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 9would 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));
}
}
