xyz Interview Question
Country: United States
public Node firstAncestor(Node leftNode, Node rightNode){
Node root1 = null;
Node root2 = null;
Stack<Node> stackLeft = new Stack<Node>();
while(leftNode.parent != null){
stackLeft.push(leftNode.parent);
}
Stack<Node> stackRight = new Stack<Node>();
while(rightNode.parent != null){
stackLeft.push(rightNode.parent);
}
int size = Math.min(stackLeft.size(), stackRight.size());
Node temp = null;
while(size-- >0){
if(stackLeft.peek() != stackRight.peek())
break;
temp = stackLeft.pop();
stackRight.pop();
}
return temp;
}
class Node(var value: Int, var parent: Option[Node] = None, var left: Option[Node] = None, var right: Option[Node] = None) {
override def toString: String = s"Node($value)"
}
object Prob {
def path(n1: Node, prevPath: Seq[Node] = Seq()): Seq[Node] =
n1.parent match {
case Some(parent) =>
path(parent, prevPath ++ Seq(n1))
case None =>
prevPath ++ Seq(n1)
}
def commonParent(n1: Node, n2: Node): Node = {
// find paths up to root node
val n1Path = path(n1).reverse
val n2Path = path(n2).reverse
// pair paths beggining from the root node
val zipped = n1Path.zip(n2Path)
// find first non common node in path
val indexOfFirstNonCommon = zipped.indexWhere(p => !p._1.eq(p._2))
if (indexOfFirstNonCommon == -1) {
zipped.last._1
} else {
// the node before the first non common node is the common parent
zipped(indexOfFirstNonCommon - 1)._1
}
}
def setupParentChild(parent: Node, left: Option[Node], right: Option[Node]): Unit = {
parent.left = left
parent.right = right
left.foreach(_.parent = Some(parent))
right.foreach(_.parent = Some(parent))
}
def main(args: Array[String]): Unit = {
val n1 = new Node(1)
val n2 = new Node(2)
val n3 = new Node(3)
val n4 = new Node(4)
val n5 = new Node(5)
val n8 = new Node(8)
val n9 = new Node(9)
val n10 = new Node(10)
val n11 = new Node(11)
setupParentChild(n1, Some(n2), Some(n3))
setupParentChild(n3, Some(n4), Some(n5))
setupParentChild(n4, Some(n10), None)
setupParentChild(n5, Some(n8), Some(n9))
setupParentChild(n9, None, Some(n11))
println(commonParent(n10, n11))
println(commonParent(n1, n2))
println(commonParent(n8, n9))
}
}
package firstCommonAncestor;
import java.util.ArrayList;
import java.util.List;
public class FirstCommonAncestorFinder {
public Node firstCommonAncestor(Node root, int val1, int val2){
List<Direction> directions1 = findDirectionList(root, val1);
List<Direction> directions2 = findDirectionList(root, val2);
Node runner = root;
for(int indexDir1 = 0, indexDir2 = 0;
indexDir1 < directions1.size() && indexDir2 < directions2.size();
indexDir1 ++, indexDir2++) {
Direction d1 = directions1.get(indexDir1);
Direction d2 = directions2.get(indexDir2);
if( d1 != d2){ return runner; }
runner = d1 == Direction.LEFT? runner.left: runner.right;
}
return runner;
}
private List<Direction> findDirectionList(Node node, int val) {
return findDirectionList(node, val, new ArrayList<>());
}
private List<Direction> findDirectionList(Node node, int val, List<Direction> directions) {
if(node == null){return null;}
if(node.val == val){
return directions;
}else{
List<Direction> pathLeft = findDirectionList(node.left, val,
addDirectionToList(directions, Direction.LEFT));
if(pathLeft!= null){return pathLeft;}
return findDirectionList(node.right, val, addDirectionToList(directions, Direction.RIGHT));
}
}
private List<Direction> addDirectionToList(List<Direction> directions, Direction direction){
List<Direction> includeDir = new ArrayList<>(directions);
includeDir.add(direction);
return includeDir;
}
}
package firstCommonAncestor;
import java.util.ArrayList;
import java.util.List;
public class FirstCommonAncestorFinder {
public Node firstCommonAncestor(Node root, int val1, int val2){
List<Direction> directions1 = findDirectionList(root, val1);
List<Direction> directions2 = findDirectionList(root, val2);
Node runner = root;
for(int indexDir1 = 0, indexDir2 = 0;
indexDir1 < directions1.size() && indexDir2 < directions2.size();
indexDir1 ++, indexDir2++) {
Direction d1 = directions1.get(indexDir1);
Direction d2 = directions2.get(indexDir2);
if( d1 != d2){ return runner; }
runner = d1 == Direction.LEFT? runner.left: runner.right;
}
return runner;
}
private List<Direction> findDirectionList(Node node, int val) {
return findDirectionList(node, val, new ArrayList<>());
}
private List<Direction> findDirectionList(Node node, int val, List<Direction> directions) {
if(node == null){return null;}
if(node.val == val){
return directions;
}else{
List<Direction> pathLeft = findDirectionList(node.left, val,
addDirectionToList(directions, Direction.LEFT));
if(pathLeft!= null){return pathLeft;}
return findDirectionList(node.right, val, addDirectionToList(directions, Direction.RIGHT));
}
}
private List<Direction> addDirectionToList(List<Direction> directions, Direction direction){
List<Direction> includeDir = new ArrayList<>(directions);
includeDir.add(direction);
return includeDir;
}
}
- Anonymous May 12, 2018public Node firstAncestor(Node leftNode, Node rightNode){ Node root1 = null; Node root2 = null; Stack<Node> stackLeft = new Stack<Node>(); while(leftNode.parent != null){ stackLeft.push(leftNode.parent); } Stack<Node> stackRight = new Stack<Node>(); while(rightNode.parent != null){ stackLeft.push(rightNode.parent); } int size = Math.min(stackLeft.size(), stackRight.size()); Node temp = null; while(size-- >0){ if(stackLeft.peek() != stackRight.peek()) break; temp = stackLeft.pop(); stackRight.pop(); } return temp; }