## 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.

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.

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

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?

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

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

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

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.

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){
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;
}``````

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

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

Your solution assumes this is BST, which is untrue

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

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

What if targetB is child of targetA?

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

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

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

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

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

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

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

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.

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

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

if(root == n){
} else {
List<Node> subRes = null;
if(root.left != null){
subRes = pathToNode(root.left, n);
if(subRes != null){
}
}
if(subRes == null && root.right != null){
subRes = pathToNode(root.right, n);
if(subRes != null){
}
}
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;
}
}``````

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.

### 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.