xyz Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
    }

- Anonymous May 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

}

- sriram.itech May 12, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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))
  }
}

- emir10xrec May 31, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 June 27, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 June 27, 2018 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More