CareerCup

The second round interview: Implement a binary tree with the given interface, then discuss the implementation via remote desktop and phone.

/*
 * An interface for an sorted binary tree.
 * 
 * The interface provides methods for inserting values, checking if certain values are contained and iterating over the elements.
 * Note: Implementing classes should provide an iterator that traverse the inserted object in the sorted order.
 */
public interface IBinTree<V extends Comparable<V>> extends Iterable<V> {
	/*
	 * Insert an object into the binary tree. Note: The tree should be sorted, inserting the same object twice is allowed but the insert is expected to be stable.
	 */
	void insert(V obj);
	/*
	 * Batch-insert multiple elements.
	 */
	void insert(Vector<V> vec);
	/*
	 * Check if the object is already in the tree. Return true if it is, false otherwise. 
	 */
	boolean contains(V obj);
}

The first round: Phone interview + online coding:

You are given an array of n integers, each of which may be positive, negative or zero. Give an algorithm to identify the start and end index, i and j, of the interval whose elements form the maximal sum of all possible intervals. Assume j >=i



e.g. {1 3 -8 2 -1 10 -2 1} -> i=3 , j=5 – sum = 11



Example non-maximal sum intervals:

i=0, j=5 – sum = 7

i=2, j=4 – sum = -7