Amazon Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
// for pair i, the child is children[i], parent is parents[i]
public BinaryTreeNode convert(int[] children, int[] parents) {
HashMap<Integer, BinaryTreeNode> nodes = new HashMap<>();
// resolve root
int rootValue = this.getRootValue(children, parents);
BinaryTreeNode root = new BinaryTreeNode(rootValue);
nodes.put(rootValue, root);
for(int i = 0; i < children.length; i ++) {
int child = children[i];
BinaryTreeNode childNode = nodes.get(child);
if(childNode == null) {
childNode = new BinaryTreeNode(child);
nodes.put(child, childNode);
}
int parent = parents[i];
BinaryTreeNode parentNode = nodes.get(parent);
if(parentNode == null) {
parentNode = new BinaryTreeNode(parent);
nodes.put(parent, parentNode);
}
// set parent child relationship
childNode.setParent(parentNode);
if(parentNode.getLeftChild() == null)
parentNode.setLeftChild(childNode);
else
parentNode.setRightChild(childNode);
}
return root;
}
private int getRootValue(int[] children, int[] parents) {
HashSet<Integer> ancestors = new HashSet<>();
for(int parent : parents)
ancestors.add(parent);
for(int child : children)
ancestors.remove(child);
return ancestors.iterator().next();
}
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
/**
* Objective: To return root node, given pairs of child, parent nodes
* of the tree.
*
* @author Sunil
*
*/
public class Node {
HashSet<Node> children = new HashSet<Node>();
boolean hasParent = false;
int data;
public static void main(String[] args) {
// Sample input
Node root = constructTree(new String[]{"3,2","4,2","7,5","8,5","2,1","5,1"});
System.out.println("Root node: "+root.data);
}
private static Node constructTree(String[] strings) {
if(strings == null) {
System.out.println("Provide tree input!");
return null;
}
HashMap<Integer, Node> nodeMap = new HashMap<Integer, Node>();
for (int i = 0; i < strings.length; i++) {
try {
StringTokenizer str = new StringTokenizer(strings[i],",");
int child = Integer.parseInt(str.nextToken());
int parent = Integer.parseInt(str.nextToken());
Node c = nodeMap.get(child);
if(c == null) { // Node not yet added
c = new Node();
c.data = child;
nodeMap.put(child, c);
}
Node p = nodeMap.get(parent);
if(p == null) { // Node not yet added
p = new Node();
p.data = parent;
}
// Add child to parent node
c.hasParent = true;
p.children.add(c);
nodeMap.put(parent, p);
} catch(Exception ex) {
System.out.println("Invalid tree input!");
return null;
}
}
for(Node node: nodeMap.values()) {
if(!node.hasParent)
return node; // Found the root
}
return null; // If root not found return null
}
}
Assuming input is a list of strings each of the form "a,b"
- bp February 21, 2014