Twitter Interview Question for Software Engineer / Developers


Country: United States
Interview Type: Phone Interview




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

1. find the lowest common denominator between these two nodes.
2. find the distance between LCD to the first node,
3, find the distnace between LCD to the second node.
4. Add these two distances.

- moiskim September 19, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

If you want just one query, just use a breadth first search from the first node until the second node is found.

- Miguel Oliveira September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

binary tree by default is a directed acyclic graph with a distinguished node (root) that has 0 in-degree

so how do you do BFS from a non-root node to another non-root node?

- bigphatkdawg September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes it is, but the nodes usually have a pointer to its parent. you can use that.
this pointer is used for situations like deleting elements of the tree and is also useful here

- Miguel Oliveira September 12, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Ok.
It's a reasonable solution if parents pointers are available.

But if the question asked for the actual path, then this method would be too awkward.

- bigphatkdawg September 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First find the path (starting from root) for the first node , then the same for the second node. Then find the lowest common ancestor and the number of nodes in the requested path.

ArrayList<Node> find_path(Node current , Node n, ArrayList<Node> path){
	path.add(current);
	if (current == n)
		return path;
	if (current.left != null){
		ArrayList<Node> p1 = find_path(current.left , n , path);
		if (p1 != null)
			return p1;
	}
	if (current.right != null){		
		ArrayList<Node> p2 = find_path(current.right , n , path);
		if (p2 != null)
			return p2;
	}
	path.remove(path.remove(path.size() - 1));
	return path;
}

int find_path_nodes(Node root , Node n1 , Node n2){
	ArrayList<Node> p1 = find_path(root , n1 , new ArrayList<Node>());
	ArrayList<Node> p2 = find_path(root , n2 , new ArrayList<Node>());
	int i = 0;
	for (; i < Math.min(p1.size() , p2.size()) ; i++){
		if (p1.get(i) != p2.get(i))
			break;
	}
	return p1.size() + p2.size() - 2 * i + 1;
}

- Arian September 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

struct tree_t {
	tree_t *left, *right;
	int val;
};

tree_t *get_anchor(tree_t *root, int x, int y) {
	if (root->val >= x && root->val <= y)
		return root;
	else if (root->val < x)
		return get_anchor(root->right, x, y);
	else
		return get_anchor(root->left, x, y);
}

int get_len_one(tree_t *root, int x, int len) {
	if (root->val == x)
		return len;
	else if (root->val < x)
		return get_len_one(root->right, x, len+1);
	else
		return get_len_one(root->left, x, len+1);
}

int get_len(tree_t *root, int x, int y) {
	tree_t *anchor = get_anchor(root, std::min(x,y), std::max(x,y));
	return get_len_one(anchor, x, 0) + get_len_one(anchor, y, 0);
}

- john September 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your solution assumes this is BST, which is untrue

- Anonymous September 14, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's an algorithm that combine LCD with distance between two nodes.

public static Integer nodeDistance(Node root, int targetA, int targetB, int distance) { 
        if (root == null)
            return null;
        
        if (root.data == targetA || root.data == targetB) 
            return distance;
        
        Integer leftCount = nodeDistance(root.left, targetA, targetB, distance + 1);
        Integer rightCount = nodeDistance(root.right, targetA, targetB, distance + 1);
        
        if (leftCount != null && rightCount != null)
            return leftCount + rightCount - (2 * distance);
        
        return leftCount == null ? rightCount : leftCount;
    }

- frankierock October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What if targetB is child of targetA?

- Harish December 17, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a Scala example, including Tree implementation. I thought of a way to optimize (will update later), feedback welcome:

import scala.annotation.tailrec

object questions extends App {  
  
  sealed trait Tree[+T] {
    
    //find the distance from this node to the given descendant. zero if nodes are equal.
    def depthTo[T](dest: T, counter: Int = 0): Option[Int] = this match {
      case End => None
      case Node(v, left, right) =>
      	if(v == dest)
      		Some(counter)
      	else 
      		left.depthTo(dest, counter + 1) orElse { right.depthTo(dest, counter + 1) }
    }    
  }
  case class Node[+T](value: T, left: Tree[T], right: Tree[T]) extends Tree[T]
  case object End extends Tree[Nothing] 
  object Node {
    def apply[T](value: T): Node[T] = Node(value, End, End)
  }  
    
  def distance(root: Node[Int], n1: Int, n2: Int): Int = {
    
    //generate a path (i.e. list of nodes) from the start to the destination. O(n)
    def findPath[T](curr: Tree[T], path: List[Node[T]] = List()): List[Node[T]] = curr match {
      case End => path
      case nn @ Node(v, left, right) =>
        if(v == n1) nn :: Nil
	      else {
	        val p = nn :: findPath(left, path)
	        if(p.isEmpty)
	          nn :: findPath(right, path)
	        else
	          p
	      }
    }

    //find shortest path from a list of nodes to a given destination node. 
    @tailrec
    def findDist[T](path: List[Node[T]], counter: Int = 1): Int = path match {
      case Nil => throw new Exception("invalid binary tree: no path between nodes")
      case hd :: tl => 
        hd.depthTo(n2) match {
        	case None => findDist(tl, counter + 1) 
        	case Some(i) => i + counter
        }
    }
            
    findDist(findPath(root).reverse)
  }
  
  val ex1 = Node(1, Node(2, Node(4), Node(5)), Node(3))
    
  println(distance(ex1, 2, 4))  
}

- dlandis November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Scala! People here barely know the mainstream languages. Don't expect to get any feedback :-)

- Anonymous November 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findbnodes(TNode* node, int k1, int k2)
{
int minv = -1;
findbnodes(node, k1, k2, 1, minv);
return minv;
}

int findbnodes(TNode* node, int k1, int k2, int cdepth, int &minv)
{
if (node == NULL)
{
return -1;
}

int ldepth = findbnodes(node->left, k1, k2, cdepth + 1, minv);
int rdepth = findbnodes(node->right, k1, k2, cdepth + 1, minv);

if (node->val == k1 || node->val == k2)
{
if (ldepth > 0)
{
minv = ldepth - cdepth + 1;
}
else if (rdepth > 0)
{
minv = rdepth - cdepth + 1;
}
return cdepth;
}
else if (ldepth >0 && rdepth > 0)
{
minv = ldepth - cdepth + rdepth - cdepth + 1;
return ldepth;
}
else if (ldepth >0)
{
return ldepth;
}
else if (rdepth >0)
{
return rdepth;
}
return -1;
}

- Anonymous December 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

traverse the tree to find the two nodes and search for int *A, int *B:

if node == *A (or *B )and the other pointer is 0, return 1

else if node == *A (or *B )and the other pointer is NOT 0, return (recurse with A = 0)

else if one of A / B is zero, return (recurse + 1)

else if both are none zero return the sum of recurse_left, recurse_right

recursion decision based on value of *A, *B and current node, basically a binary search tree type situation

- rk January 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int findPathLength(Node left, Node right) {
If ( left == null || right == null)
throw new IllegalArgumentException();
if ( left == right )
return 0;

Node leftParent = left.getParent();
Node rightParent = right.GetParent();
if ( leftParent == rightParent )
return 1;

return 2+ findPathLength(leftParent, rightParent);
}

- Kirill February 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution :

1. Distance bet root node and first node - d1
2. Distance bet root node and second node - d2
3. Distance bet root and lca - d3

4. Ans : d1 + d2 - 2*d3

- Aravind August 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we can just in-order traverse this binary tree ? During traversal we can find the head (either first node or second), then keep recording the path to the remainder node as the tail.

- Ben September 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class NodeLength{
public:
    int result = -1;
    
    int findNode(TreeNode* root, TreeNode* nd1, TreeNode* nd2, int len){
        if(root == NULL)    return 0;
        
        int plen1 = findNode(root->left, nd1, nd2, len+1);
        int plen2 = findNode(root->right, nd1, nd2, len+1);
        if(result == -1){
            if(plen1 != 0 && plen2 != 0){
                result = plen1 + plen2;
                return result;
            }
            
            if(root == nd1){
                if(plen2 != 0){
                    result = plen2 - len;
                    return result;
                }else
                    return len;
            }
            if(root == nd2){
                if(plen1 != 0){
                    result = plen1 - len;
                    return result;
                }
                return len;
            }
            if(plen1 != 0)  return plen1;
            if(plen2 != 0)  return plen2;
            return 0;
        }
        return 0;
    }
    
    int driver(TreeNode* root, TreeNode* nd1, TreeNode* nd2){
        findNode(root, nd1, nd2, 0);
        return result;
    }
};

- wwu October 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class TreeDistance {
	
	class Node {
		int v;
		Node left, right;
		
		public Node(int v){
			this.v = v;
			left = right = null;
		}
	}
	
	
	public TreeDistance() {
	}
	
	static List<Node> pathToNode(Node root, Node n){
		if(root == null || n == null){
			return null;
		}
		
		List<Node> result = new LinkedList<Node>();
		if(root == n){
			result.add(n);
		} else {
			List<Node> subRes = null;
			if(root.left != null){
				subRes = pathToNode(root.left, n);
				if(subRes != null){
					result.add(root);
					result.addAll(subRes);
				}
			}
			if(subRes == null && root.right != null){
				subRes = pathToNode(root.right, n);
				if(subRes != null){
					result.add(root);
					result.addAll(subRes);
				}
			}
			if(subRes == null){
				result = null;
			}
		}
		return result;
	}
	
	static int computeTreeDistance(Node root, Node n1, Node n2) throws Exception{
		
		if(root == null || n1 == null || n2 == null){
			throw new IllegalArgumentException();
		}
		
		List<Node> pathToN1, pathToN2;
		
		pathToN1 = pathToNode(root, n1);
		pathToN2 = pathToNode(root, n2);
		
		// one of nodes not present
		if(pathToN1 == null || pathToN2 == null){
			throw new Exception("One of the nodes not in the tree");
		}
		
		int d1 = pathToN1.size(), d2 = pathToN2.size();
		int res = d1 + d2;
		boolean done = (d1==0 || d2==0) || (pathToN1.get(0) != pathToN2.get(0));
		while(!done){
			res = res-2;
			pathToN1.remove(0);
			pathToN2.remove(0);
		}
		return res;
	}
}

- just_do_it May 12, 2015 | 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