Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

The longest path has to be rooted in one node and it is the concatenation of the longest path on the left, the node, and the longest path on the right. For each node, find the longest path rooted on it and find the max of all.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right


class LongestPathFinder:

    def check_if_longest(self, key, l_path, r_path):
        if len(l_path) + len(r_path) + 1 > self.longest_path_len:
            self.longest_path_len = len(l_path) + len(r_path) + 1
            self.longest_path_root = key
            self.left_deepest_path = l_path
            self.right_deepest_path = r_path
            
    def find_deepest_path(self,node):
        if node == None:
            return []

        left_deepest_path = self.find_deepest_path(node.left)
        right_deepest_path = self.find_deepest_path(node.right)

        self.check_if_longest(node.key, left_deepest_path, right_deepest_path)

        if len(left_deepest_path) >= len(right_deepest_path):
            return left_deepest_path + [node.key]
        else:
            return right_deepest_path + [node.key]
                    
        
    def __init__(self,root):
        self.longest_path_root = None
        self.left_deepest_path  = []
        self.right_deepest_path = []
        self.longest_path_len = 0

        self.find_deepest_path(root)

        if self.longest_path_len == 0:
            self.longest_path = []
        else:
            self.longest_path = self.left_deepest_path + \
                                [self.longest_path_root] + \
                                list(reversed(self.right_deepest_path))

- Terio December 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the longest path will be from a leave to an other leave or from a leave to the root. So, all inner nodes, except the root are not the end points.
One way to find it, is to go from each leave upwards, storing the max. distance to a leave for each subtree and maximize left+right+1 at each node. This takes O(n) time and O(n) space.

- Chris December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do a post order traversal of the tree calculating the length of increasing and decreasing sequence for the left and right child

class Node{
	int data;
	Node left, right;
	public Node(int x){
		data=x;
		left=right=null;
	}
}
class Result{
	int inc,dec;
}
public class LCSInBT {
	public static int max;
	public static void main(String[] args) {
		Node n=new Node(6);
		n.left=new Node(5);
		n.left.left=new Node(3);
		n.left.right=new Node(4);
		n.left.left.left=new Node(2);
		n.right=new Node(7);
		n.right.left=new Node(8);
		n.right.left.right=new Node(9);
		lcs(n);
		System.out.println(max);
	}

	private static Result lcs(Node n) {
		Result res=new Result();
		if(n==null){
			res.dec=0;	res.inc=0;
			return res;
		}
		res.dec=1; res.inc=1;
		Result l=lcs(n.left);
		Result r=lcs(n.right);
		if(n.left!=null){
			if(n.left.data+1==n.data){
				res.inc+=l.inc;
			}
			if(n.data+1==n.left.data){
				res.dec+=l.dec;
			}
		}
		if(n.right!=null){
			if(n.right.data+1==n.data){
				res.inc=Math.max(res.inc,r.inc+1);
			}
			if(n.right.data==n.data+1){
				res.dec=Math.max(res.dec,r.dec+1);
			}
		}
		max=Math.max(findLen(n,l,r), max);
		return res;
	}

	private static int findLen(Node n, Result l, Result r) {
		int len=0;
		if(n.left!=null && n.right!=null){
			if(n.data+1==n.left.data && n.data==n.right.data+1){
				len=l.dec+r.inc+1;
			}
			else if(n.data==n.left.data+1 && n.data+1==n.right.data){
				len=l.inc+r.dec+1;
			}
			else if(n.data+1==n.left.data){
				len=1+l.dec;
			}
			else if(n.data==n.left.data+1){
				len=1+l.inc;
			}
			else if(n.data+1==n.right.data){
				len=1+r.dec;
			}
			else if(n.data==n.right.data+1){
				len=1+r.inc;
			}
		}
		return len;
	}

}

- Iram22 December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Postorder traversal of the tree calculating the length of increasing and decreasing sequence for both left and right child

class Node{
	int data;
	Node left, right;
	public Node(int x){
		data=x;
		left=right=null;
	}
}
class Result{
	int inc,dec;
}
public class LCSInBT {
	public static int max;
	public static void main(String[] args) {
		Node n=new Node(6);
		n.left=new Node(5);
		n.left.left=new Node(3);
		n.left.right=new Node(4);
		n.left.left.left=new Node(2);
		n.right=new Node(7);
		n.right.left=new Node(8);
		n.right.left.right=new Node(9);
		lcs(n);
		System.out.println(max);
	}

	private static Result lcs(Node n) {
		Result res=new Result();
		if(n==null){
			res.dec=0;	res.inc=0;
			return res;
		}
		res.dec=1; res.inc=1;
		Result l=lcs(n.left);
		Result r=lcs(n.right);
		if(n.left!=null){
			if(n.left.data+1==n.data){
				res.inc+=l.inc;
			}
			if(n.data+1==n.left.data){
				res.dec+=l.dec;
			}
		}
		if(n.right!=null){
			if(n.right.data+1==n.data){
				res.inc=Math.max(res.inc,r.inc+1);
			}
			if(n.right.data==n.data+1){
				res.dec=Math.max(res.dec,r.dec+1);
			}
		}
		max=Math.max(findLen(n,l,r), max);
		return res;
	}

	private static int findLen(Node n, Result l, Result r) {
		int len=0;
		if(n.left!=null && n.right!=null){
			if(n.data+1==n.left.data && n.data==n.right.data+1){
				len=l.dec+r.inc+1;
			}
			else if(n.data==n.left.data+1 && n.data+1==n.right.data){
				len=l.inc+r.dec+1;
			}
			else if(n.data+1==n.left.data){
				len=1+l.dec;
			}
			else if(n.data==n.left.data+1){
				len=1+l.inc;
			}
			else if(n.data+1==n.right.data){
				len=1+r.dec;
			}
			else if(n.data==n.right.data+1){
				len=1+r.inc;
			}
		}
		return len;
	}

}

- Iram22 December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right


class LongestPathFinder:

    def check_if_longest(self, key, l_path, r_path):
        if len(l_path) + len(r_path) + 1 > self.longest_path_len:
            self.longest_path_len = len(l_path) + len(r_path) + 1
            self.longest_path_root = key
            self.left_deepest_path = l_path
            self.right_deepest_path = r_path
            
    def find_deepest_path(self,node):
        if node == None:
            return []

        left_deepest_path = self.find_deepest_path(node.left)
        right_deepest_path = self.find_deepest_path(node.right)

        self.check_if_longest(node.key, left_deepest_path, right_deepest_path)

        if len(left_deepest_path) >= len(right_deepest_path):
            return left_deepest_path + [node.key]
        else:
            return right_deepest_path + [node.key]
                    
        
    def __init__(self,root):
        self.longest_path_root = None
        self.left_deepest_path  = []
        self.right_deepest_path = []
        self.longest_path_len = 0

        self.find_deepest_path(root)

        if self.longest_path_len == 0:
            self.longest_path = []
        else:
            self.longest_path = self.left_deepest_path + \
                                [self.longest_path_root] + \
                                list(reversed(self.right_deepest_path))

- Terio December 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The longest path has to be rooted in one node and it is the concatenation of the longest path on the left, the node, and the longest path on the right. For each node, find the longest path rooted on it and find the max of all.

class Node:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right


class LongestPathFinder:

    def check_if_longest(self, key, l_path, r_path):
        if len(l_path) + len(r_path) + 1 > self.longest_path_len:
            self.longest_path_len = len(l_path) + len(r_path) + 1
            self.longest_path_root = key
            self.left_deepest_path = l_path
            self.right_deepest_path = r_path
            
    def find_deepest_path(self,node):
        if node == None:
            return []

        left_deepest_path = self.find_deepest_path(node.left)
        right_deepest_path = self.find_deepest_path(node.right)

        self.check_if_longest(node.key, left_deepest_path, right_deepest_path)

        if len(left_deepest_path) >= len(right_deepest_path):
            return left_deepest_path + [node.key]
        else:
            return right_deepest_path + [node.key]
                    
        
    def __init__(self,root):
        self.longest_path_root = None
        self.left_deepest_path  = []
        self.right_deepest_path = []
        self.longest_path_len = 0

        self.find_deepest_path(root)

        if self.longest_path_len == 0:
            self.longest_path = []
        else:
            self.longest_path = self.left_deepest_path + \
                                [self.longest_path_root] + \
                                list(reversed(self.right_deepest_path))

- Terio December 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
import java.lang.Math;
public class BTLongestConsecutivePath {
  public static void main(String[] args) {
    BT t = new BT();
    t.add(6);
    t.add(2);
    t.add(1);
    t.add(0);
    t.add(3);
    t.add(4);
    t.add(5);
    t.postorder();
    System.out.println(t.searchLongestPath());
  }

  public static class BT {
    Node root;
    ArrayList<Integer> array;
    public BT() {
      this.root = null;
      this.array = new ArrayList<Integer>();
    }
    public void add(int val) {
      root = add(root, val);
    }
    public Node add(Node root, int val) {
      if(root == null) return new Node(val, null, null);
      else {
        if(root.val < val) {
          root.right = add(root.right, val);
          return root;
        } else if(root.val > val) {
          root.left = add(root.left, val);
          return root;
        } else {
          return root;
        }
      }
    }
    public void inorder() { inorder(root); }
    public void inorder(Node root) {
      if(root != null) {
        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
      }
    }
    public void postorder() { postorder(root); }
    public void postorder(Node root) {
      if(root != null) {
        postorder(root.left);
        postorder(root.right);
        array.add(root.val);
        System.out.println(root.val);
      }
    }
    public ArrayList<String> searchConsecutive() {
      ArrayList<String> consecutive = new ArrayList<String>();
      String str = "";
      for(int i = 0; i < array.size()-1; i++) {
        if(Math.abs(array.get(i)-array.get(i+1)) == 1) {
          if(str.length() == 0) {
            str += array.get(i)+","+array.get(i+1)+",";
          } else {
            str += array.get(i+1)+",";
          }
        } else {
          if(str.length() != 0) consecutive.add(str);
          str = "";
        }
      }
      return consecutive;
    }
    public String searchLongestPath() {
      ArrayList<String> consecutive = searchConsecutive();
      int original_size = consecutive.size();
      for(int i = 0; i < original_size; i++) {
        for(int j = 0; j < original_size; j++) {
          if(i != j) {
            String str1 = consecutive.get(i);
            String str2 = consecutive.get(j);
            if(Math.abs(str1.charAt(str1.length()-2)-str2.charAt(str2.length()-2)) == 1) {
              for(int x = str2.length()-2; x >= 0; x-=2) {
                str1 += str2.charAt(x)+",";
              }
              consecutive.add(str1);
            }
          }
        }
      }
      int length = 0;
      int index = -1;
      for(int i = 0; i < consecutive.size(); i++) {
        if(consecutive.get(i).length() > length) {
          length = consecutive.get(i).length();
          index = i;
        }
      }
      return index == -1 ? "" : consecutive.get(index);
    }
  }

  public static class Node {
    Node left, right;
    int val;
    public Node(int val, Node left, Node right) {
      this.val = val;
      this.left = left;
      this.right = right;
    }
  }

}

- Obed Tandadjaja December 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class LongestPathInBinaryTree {

    private static class Node {
        
        Node left;
        Node right;
        
        int payload;
        
        public String toString() { return ""+payload; }
    }
    
    public static void main(String[] args) {
               
        Node n7 = new Node(); n7.payload = 7;
        Node n6 = new Node(); n6.payload = 6;
        
        Node n4 = new Node(); n4.payload = 4;
        Node n5 = new Node(); n5.payload = 5; n5.left = n6; n5.right = n7;
        
        Node n2 = new Node(); n2.payload = 2; n2.left = n4; n2.right = n5;
        Node n3 = new Node(); n3.payload = 3;
        
        Node n1 = new Node(); n1.payload = 1;  n1.left = n2;  n1.right = n3;
        
        System.out.println(getLongestPath(n1, 0));
    }
    
    private static LinkedList<Node> getLongestPath(Node root, int level) {
    
        LinkedList<Node> result = new LinkedList<Node>();
        
        LinkedList<Node> leftPath = null;
        if (root.left != null) leftPath = getLongestPath(root.left, 1);
        
        LinkedList<Node> rightPath = null;
        if (root.right != null) rightPath = getLongestPath(root.right, 1);
        
        if (level > 0) {
            List<Node> childPath = compare(leftPath, rightPath);
            if (childPath != null) result.addAll(childPath);
            result.add(root);
        }
        else {
            if (leftPath != null) result.addAll(leftPath);
            result.add(root);
            if (rightPath != null) {
                for (Iterator<Node> it = rightPath.descendingIterator(); it.hasNext();) {
                    result.add(it.next());
                }
            }
        }
        
        return result;
    }
    
    private static List<Node> compare(List<Node> l , List<Node> r) {
        if (l == null && r == null) return null;
        
        if (l == null) return r;
        
        if (r == null) return l;
                
        return r.size() >= l.size()? r: l;
    }    
}

- PR December 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Generate child-to-parent consecutive depth map for each node
    * Find the longest ascending sequence if its left child < itself
    * Find the longest descending sequence if its left child > itself
    * Find the longest ascending sequence of its right child < itself
    * Find the longest descending sequence if its right child > itself
    * 0 sequence if any child is null
    * 0 sequence if any child is equal to itself
- Find the node with longest consecutive node in above map
    * Take the longer sequence if both children has same order sequence
    * Sum the sequence if two children has difference order sequence

Details: //cpluspluslearning-petert.blogspot.co.uk/2017/01/bts-find-longest-consecutive-path_13.html

Test

void TestFindTheLongestOrderedSeq()
{
    std::vector<double> input = { 1.0, 2.0, 3.0, 4.0, 5.0 };
    TreeNode<double> *root = NULL;
    //              3
    //      1               4
    //          2               5
    root = ConstructTreeOnSortedValueBFS(input);
    auto path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });

    input = { 6.0, 7.0, 8.0, 9.0 };
    TreeNode<double> *subTree1 = ConstructTreeOnSortedValueDFS(input);
    input = { 10.0, 11.0, 12.0, 13.0 , 14.0 };
    TreeNode<double> *subTree2 = ConstructTreeRecursive(input);
    input = { 15.0, 16.0, 17.0, 18.0 };
    TreeNode<double> *subTree3 = ConstructTreeOnSortedValueDFS(input);
    input = { 19.0, 20.0, 21.0, 22.0 , 23.0 };
    TreeNode<double> *subTree4 = ConstructTreeRecursive(input);

    TreeNode<double> *leftestNode = FindLeftestNode(root);
    assert(leftestNode != NULL);
    leftestNode->left = subTree1;
    //              3
    //         1        4
    //      8     2        5
    //    6   9
    //  7
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0 });

    TreeNode<double> *rightestNode = FindRightestNode(root);
    assert(rightestNode != NULL);
    rightestNode->left = subTree2;
    //              3
    //         1        4
    //      8     2         5
    //    6   9          12
    //  7            10      13
    //                  11      14
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });

    TreeNode<double> *firstLeftRighestNode = FindRightestNode(root->left);
    assert(firstLeftRighestNode != NULL);
    firstLeftRighestNode->right = subTree3;
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10       13
    //               16            11      14
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });

    TreeNode<double> *firstRightLeftestNodeOfS2 = FindRightestNode(subTree2->left);
    assert(firstRightLeftestNodeOfS2 != NULL);
    firstRightLeftestNodeOfS2->left = subTree4;
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10       13
    //               16           11      14
    //                         21
    //                    19     22
    //                       20       23
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0 });

    TreeNode<double> *rightestNodeOfS2 = FindRightestNode(subTree2);
    assert(rightestNodeOfS2 != NULL);
    for (size_t i = 0; i < 8; ++i) {
        rightestNodeOfS2->right = new TreeNode<double>(100.0 + i);
        rightestNodeOfS2 = rightestNodeOfS2->right;
    }
    //                    3
    //         1              4
    //      8     2                   5
    //    6   9     17          12
    //  7         15   18   10     13
    //              16           11      14
    //                        21              100
    //                    19     22            101
    //                      20       23          102
    //                                                  103
    //                                                     104
    //                                                        105
    //                                                          106
    //                                                            107
    // clean up
    path = FindTheLongestOrderedSeq(root);
    TestResult<double>(path, { 1.0, 3.0, 4.0, 5.0, 12.0, 13.0, 14.0, 100.0,
        101.0, 102.0, 103.0, 104.0, 105.0, 106.0, 107.0});

    // clean up
    DeleteTree_TD(&root);
}

- peter tang January 13, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static List<TreeNode> longestPath0(TreeNode node, List<TreeNode> longestPath, boolean descending) {
        if (node == null)
            return new ArrayList<>(longestPath);

        //we are asked to include a path that is already passed
        if (longestPath.size() > 0) {
            if ((descending && lastElement(longestPath).getValue() - 1 == node.getValue()) ||
                    (!descending && lastElement(longestPath).getValue() + 1 == node.getValue())
                    ) {
                ArrayList<TreeNode> list = new ArrayList<>();
                list.addAll(longestPath);
                list.add(node);

                List<TreeNode> leftLongest = longestPath0(node.getLeft(), list, descending);
                List<TreeNode> rightLongest = longestPath0(node.getRight(), list, descending);

                return leftLongest.size() > rightLongest.size() ? leftLongest : rightLongest;
            } else {
                return longestPath;
            }
        } else {
            List<List<TreeNode>> resultsHolder = new ArrayList<>();
            List<TreeNode> leftDesc = longestPath0(node.getLeft(), Collections.emptyList(), descending);
            List<TreeNode> leftAsc = longestPath0(node.getLeft(), Collections.emptyList(), !descending);

            List<TreeNode> rightDesc = longestPath0(node.getRight(), Collections.emptyList(), descending);
            List<TreeNode> rightAsc = longestPath0(node.getRight(), Collections.emptyList(), !descending);


            List<TreeNode> leftDescNodeIncluded = longestPath0(node.getLeft(), Collections.singletonList(node), descending);
            List<TreeNode> leftAscNodeIncluded = longestPath0(node.getLeft(), Collections.singletonList(node), !descending);

            List<TreeNode> rightDescNodeIncluded = longestPath0(node.getRight(), Collections.singletonList(node), descending);
            List<TreeNode> rightAscNodeIncluded = longestPath0(node.getRight(), Collections.singletonList(node), !descending);

            resultsHolder.add(leftAsc);
            resultsHolder.add(leftDesc);
            resultsHolder.add(rightAsc);
            resultsHolder.add(rightDesc);
            resultsHolder.add(leftDescNodeIncluded);
            resultsHolder.add(leftAscNodeIncluded);
            resultsHolder.add(rightDescNodeIncluded);
            resultsHolder.add(rightAscNodeIncluded);
            resultsHolder.add(join(leftAscNodeIncluded, rightDescNodeIncluded));
            resultsHolder.add(join(leftDescNodeIncluded, rightAscNodeIncluded));

            return resultsHolder.stream().max((o1, o2) -> Integer.compare(o1.size(), o2.size())).get();
        }
    }

    private static List<TreeNode> join(List<TreeNode> left, List<TreeNode> right) {
        ArrayList<TreeNode> result = new ArrayList<>();

        for (int i = left.size() - 1; i > 0; i--) {
            result.add(left.get(i));
        }
        result.addAll(right);

        return result;
    }

    private static TreeNode lastElement(List<TreeNode> longestPath) {
        return longestPath.get(longestPath.size() - 1);
    }

    private static List<TreeNode> longestPath(@NonNull final TreeNode node) {
        return longestPath0(node, Collections.emptyList(), false);
    }

- otherman January 20, 2017 | 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