Sap Labs Interview Question
Developer Program EngineersTeam: Potsdam
Country: United States
Interview Type: Phone Interview
import java.util.Arrays;
import java.util.Iterator;
import java.util.Vector;
/**
*
* @author Uday Kandpal
*/
/*
* 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.
*/
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);
}
public class BinaryTree<V extends Comparable<V>> implements IBinTree<V> {
V value = null;
BinaryTree<V> left = null;
BinaryTree<V> right = null;
private Vector<V> preOrder() {
Vector<V> vector = new Vector();
if (left != null) {
vector.addAll(left.preOrder());
}
vector.add(value);
if (right != null) {
vector.addAll(right.preOrder());
}
return vector;
}
@Override
public void insert(V obj) {
if (value == null) {
value = obj;
} else if (value.compareTo(obj) == 1) {
if (left == null) {
left = new BinaryTree<>();
}
left.insert(obj);
} else {
if (right == null) {
right = new BinaryTree<>();
}
right.insert(obj);
}
}
@Override
public void insert(Vector<V> vec) {
Iterator<V> it = vec.iterator();
while (it.hasNext()) {
insert(it.next());
}
}
@Override
public boolean contains(V obj) {
if (value.compareTo(obj) == 0) {
return true;
} else if (value.compareTo(obj) == 1) {
return (left != null && left.contains(obj));
} else {
return (right != null && right.contains(obj));
}
}
@Override
public Iterator<V> iterator() {
return preOrder().iterator();
}
public static void main(String[] args) {
BinaryTree<Integer> tree = new BinaryTree<>();
Integer[] list = new Integer[]{5, 3, 2, 8, 1, 7, 4, 9};
tree.insert(new Vector<>(Arrays.asList(list)));
Iterator it = tree.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
}
}
#include<conio.h>
- Anonymous October 09, 2012main{
}