Google Interview Question for SDE1s


Country: United States




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

From your example, it looks like they only care for the length of the path.
We will do following

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

public class LongestPaths
{
	public List<List<int>> longestPathWithoutRoot;
	public List<List<int>> longestPathWithRoot;
	public LongestPaths()
	{
		longestPathWithoutRoot = new List<List<int>>();
		longestPathWithRoot = new List<List<int>>();
	}
}

public List<List<int>> getLongestPaths(Node root)
{
	var longestPaths = getLongestPathsRec(root);
	return longestPaths.longestPathWithRoot;
}

private LongestPaths getLongestPathsRec(Node node)
{
	if(node == null)
	{
		return new LongestPaths();
	}
	var leftLongestPaths = getLongestPathsRec(node.left);
	var rightLongestPaths = getLongestPathsRec(node.right);
	var longestPaths = new LongestPaths();
	int bigger = 0; int length = 0;
	if(leftLongestPaths.longestPathWithoutRoot.Length > 0)
	{
		length = leftLongestPaths.longestPathWithoutRoot[0].Length;
	}
	if(rightLongestPaths.longestPathWithoutRoot.Length > 0)
	{
		if(length < rightLongestPaths.longestPathWithoutRoot[0].Length)
		{
			length = rightLongestPaths.longestPathWithoutRoot[0].Length;
			bigger = 1;
		}
		else if(length == rightLongestPaths.longestPathWithoutRoot[0].Length)
		{
			bigger = 2;
		}
	}
	if(length == 0)
	{
		longestPaths.longestPathWithoutRoot.Add(new List<int>(){node.val});
		longestPaths.longestPathWithRoot.Add(new List<int>(){node.val});
		return longestPaths;
	}
	else if(bigger == 0)
	{
		longestPaths.longestPathWithoutRoot = leftLongestPaths.longestPathWithoutRoot;
		foreach(List<int> lists in longestPaths.longestPathWithoutRoot)
		{
			lists.Add(node.val);
		}
	}
	else if(bigger == 1)
	{
		longestPaths.longestPathWithoutRoot = rightLongestPaths.longestPathWithoutRoot;
		foreach(List<int> lists in longestPaths.longestPathWithoutRoot)
		{
			lists.Add(node.val);
		}
	}
	else
	{
		longestPaths.longestPathWithoutRoot = leftLongestPaths.longestPathWithoutRoot;
		longestPaths.longestPathWithoutRoot.AddRange(rightLongestPaths.longestPathWithoutRoot);
		foreach(List<int> lists in longestPaths.longestPathWithoutRoot)
		{
			lists.Add(node.val);
		}
	}
	if(leftLongestPaths.longestPathWithRoot.Length > 0)
	{
		longestPaths.longestPathWithRoot = leftLongestPaths.longestPathWithRoot;
	}
	if(rightLongestPaths.longestPathWithRoot.Length > 0)
	{
		if(longestPaths.longestPathWithRoot.Length > 0)
		{
			if(longestPaths.longestPathWithRoot[0].Length < rightLongestPaths.longestPathWithRoot[0].Length)
			{
				longestPaths.longestPathWithRoot = rightLongestPaths.longestPathWithRoot;
			}
			else if(longestPaths.longestPathWithRoot[0].Length == rightLongestPaths.longestPathWithRoot[0].Length)
			{
				longestPaths.longestPathWithRoot.AddRange(rightLongestPaths.longestPathWithRoot);
			}
		}
		else
		{
			longestPaths.longestPathWithRoot = rightLongestPaths.longestPathWithRoot;
		}
	}
	int lengthWithCurrentRoot = 0;
	if(leftLongestPaths.longestPathWithRoot.Length > 0)
	{
		lengthWithCurrentRoot += leftLongestPaths.longestPathWithRoot[0];
	}
	lengthWithCurrentRoot++;
	if(rightLongestPaths.longestPathWithRoot.Length > 0)
	{
		lengthWithCurrentRoot += rightLongestPaths.longestPathWithRoot[0];
	}
	if(longestPaths.longestPathWithRoot.Length == 0 || longestPaths.longestPathWithRoot[0].Length <= lengthWithCurrentRoot)
	{
		bool atleastOneAdded = false;
		if(longestPaths.longestPathWithRoot.Length > 0 && longestPaths.longestPathWithRoot[0].Length < lengthWithCurrentRoot)
		{
			longestPaths.longestPathWithRoot = new List<List<int>>();
		}
		if(leftLongestPaths.longestPathWithRoot.Length > 0)
		{
			foreach(List<int> leftlist in leftLongestPaths.longestPathWithRoot)
			{
				leftlist.Add(node.val);
				foreach(List<int> rightlist in rightLongestPaths.longestPathWithRoot)
				{
					atleastOneAdded = true;
					leftlist.AddRange(rightlist);
					longestPaths.longestPathWithRoot.Add(leftlist);
				}
				if(!atleastOneAdded)
				{
					longestPaths.longestPathWithRoot.Add(leftlist);
				}
				atleastOneAdded = false;
			}
		}
		else
		{
			var list = new List<int>();
			list.Add(node.val);
			atleastOneAdded = false;
			foreach(List<int> rightlist in rightLongestPaths.longestPathWithRoot)
			{
				atleastOneAdded = true;
				list.AddRange(rightlist);
				longestPaths.longestPathWithRoot.Add(list);
			}
			if(!atleastOneAdded)
			{
				longestPaths.longestPathWithRoot.Add(list);
			}
		}
	}
	return longestPaths;
}

Worst case Complexity is O(n*n) + O(nlog(n)), as we will be looking for all possible path. Although the avg case complexity would be O(n) + O(log(n)).

- sonesh May 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<List<Integer>> getLongestPath(TreeNode root) {
    List<List<Integer>> results = new LinkedList<List<Integer>>();
    if (root == null)
      return results; 
    TreeNode maxNode = root;
    Integer maxDist = new Integer(0);
    Hashtable<TreeNode, Integer> nodes = new Hashtable<TreeNode, Integer>(); 
    // calculate longest path to child(s) for all nodes and 
    // find a node that has max sum of longest paths to its left and right child nodes
    getMaxDepth(root, maxNode, maxDist, nodes);
    // get all possible paths to farest nodes from left and right
    LinkedList<LinkedList<TreeNode>> leftPaths = new LinkedList<LinkedList<TreeNode>>();
    LinkedList<LinkedList<TreeNode>> rightPaths = new LinkedList<LinkedList<TreeNode>>();
    if (maxNode.left != null)
      pathsToDeepest(maxNode.left, true, new LinkedList<TreeNode>(), leftPaths, nodes);
    else
      leftPaths.add(new LinkedList<TreeNode>());
    if (maxNode.right != null)
      pathsToDeepest(maxNode.right, false, new LinkedList<TreeNode>(), rightPaths, nodes);
    else
      rightPaths.add(new LinkedList<TreeNode>());
    // join left path(s), node and right path(s) 
    for(LinkedList<TreeNode> lp:leftPaths) {
      List<Integer> list = new LinkedList<Integer>();
      for(TreeNode n:lp)
        list.add(n.val);
      list.add(maxNode.val);
      for(LinkedList<TreeNode> rp:rightPaths) {
        List<Integer> inner = new LinkedList<Integer>(list);
        for(TreeNode n:rp)
          inner.add(n.val);
        results.add(inner);
      }
    }
    return results;
  }
  // find a node with longest path to its child
  public static int getMaxDepth(TreeNode n, TreeNode maxNode, Integer maxDist, Hashtable<TreeNode, Integer> nodes) {
    if (n == null || (n.left == null && n.right == null)) {
      return 0;
    }
    int left = n.left == null ? 0 : getMaxDepth(n.left, maxNode, maxDist, nodes) + 1;
    int right = n.right == null ? 0 : getMaxDepth(n.right, maxNode, maxDist, nodes) + 1;
    if(maxDist < left + right) {
      maxNode = n;
      maxDist = left + right;
    }
    if (n.left != null) nodes.put(n.left, left);
    if (n.right != null)  nodes.put(n.right, right);
    return Math.max(left, right); 
  }
  // create paths from a node to its most distance child(s)
  public static void pathsToDeepest(TreeNode n, boolean addFirst, LinkedList<TreeNode> path, 
    LinkedList<LinkedList<TreeNode>> allPaths, Hashtable<TreeNode, Integer> nodes) {
    if (n == null)
      return;
    int left = n.left != null ? nodes.get(n.left) : 0;
    int right = n.right != null ? nodes.get(n.right) : 0;
    if (addFirst)
      path.addFirst(n);
    else 
      path.add(n);
    if (left == right) {
      if (left != 0) {
        LinkedList<TreeNode> pathC =  new LinkedList<TreeNode>(path);
        pathsToDeepest(n.left, addFirst, path, allPaths, nodes);
        pathsToDeepest(n.right, addFirst, pathC, allPaths, nodes);
      } else {
        allPaths.add(path);
      }
    }
    if (left > right)
      pathsToDeepest(n.left, addFirst, path, allPaths, nodes);
    if (left < right)
      pathsToDeepest(n.right, addFirst, path, allPaths, nodes);
  }

- vk May 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is known as the 'Diameter of binary tree' problem and a solution can be found on geeksforgeeks.

- dhc May 30, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can first find the nodes which have the maximum sum of heights of the left and right sub trees. After that, for each such node (top_node below), we find all longest paths in the left sub tree and in the right sub tree. Then we combine the paths to find all paths having the maximum length.

#include <iostream>
#include <vector>

using namespace std;

class Node {
public:
	Node(int val)
	{
		val_ = val;
		left_ = NULL;
		right_ = NULL;
	}
	int val_;
	Node *left_;
	Node *right_;
};

int GetHeight(Node *n, int &longest_paths_len,
	vector<Node *> &longest_paths_top_nodes)
{
	if (!n) {
		return 0;
	}
	int left_height = GetHeight(n->left_, longest_paths_len, longest_paths_top_nodes);
	int right_height = GetHeight(n->right_, longest_paths_len, longest_paths_top_nodes);
	int max_len = left_height + 1 + right_height;
	if (max_len >= longest_paths_len) {
		if (max_len > longest_paths_len) {
			longest_paths_top_nodes.clear();
		}
		longest_paths_len = max_len;
		longest_paths_top_nodes.push_back(n);
	}
	return max(left_height, right_height) + 1;
}

void FindLongestPath(Node *n, vector<Node *> &path, int &longest_paths_len,
	vector<vector<Node *>> &longest_paths)
{
	if (n) {
		path.push_back(n);
		if (path.size() >= longest_paths_len) {
			if (path.size() > longest_paths_len) {
				longest_paths.clear();
			}
			longest_paths.push_back(path);
			longest_paths_len = path.size();
		}
		FindLongestPath(n->left_, path, longest_paths_len, longest_paths);
		FindLongestPath(n->right_, path, longest_paths_len, longest_paths);
		path.pop_back();
	}
}

vector<vector<Node *>> FindLongestPaths(Node *root)
{
	vector<Node *> longest_paths_top_nodes;
	int longest_paths_len = 0;
	GetHeight(root, longest_paths_len, longest_paths_top_nodes);

	vector<vector<Node *>> longest_paths;
	for (Node *top_node : longest_paths_top_nodes) {
		int longest_paths_len = 0;
		vector<Node *> path;

		vector<vector<Node *>> left_longest_paths;
		FindLongestPath(top_node->left_, path, longest_paths_len, left_longest_paths);

		longest_paths_len = 0;
		path.clear();

		vector<vector<Node *>> right_longest_paths;
		FindLongestPath(top_node->right_, path, longest_paths_len, right_longest_paths);

		if (left_longest_paths.empty()) {
			left_longest_paths.push_back(vector<Node *>());
		}

		if (right_longest_paths.empty()) {
			right_longest_paths.push_back(vector<Node *>());
		}

		for (auto const &left_path : left_longest_paths) {
			for (auto const &right_path : right_longest_paths) {
				path.clear();
				path.insert(path.end(), left_path.begin(), left_path.end());
				reverse(path.begin(), path.end());
				path.push_back(top_node);
				path.insert(path.end(), right_path.begin(), right_path.end());
				longest_paths.push_back(path);
			}
		}
	}

	return longest_paths;
}

int main()
{
	Node n1(1);
	Node n2(2);
	Node n3(3);
	Node n4(4);
	Node n5(5);

	n1.left_ = &n2;
	n1.right_ = &n3;
	n2.left_ = &n3;
	n2.left_ = &n4;
	n2.right_ = &n5;

	vector<vector<Node *>> paths = FindLongestPaths(&n1);

	for (auto const &path : paths) {
		for (Node *n : path) {
			cout << "->" << n->val_;
		}
		cout << "\n";
	}
	return 0;
}

- Alex June 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Same concept as of Alex, but shorter code:

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None



p = TreeNode(1)
p.left = TreeNode(2)
p.right = TreeNode(3)
p.left.left = TreeNode(4)
p.left.right = TreeNode(5)


def glp(tree, lp):
    if tree is None:
        return []
    left = [tree.val] + glp(tree.left, lp)
    right = [tree.val] + glp(tree.right, lp)

    lp.append(left[::-1] + right[1:])

    if len(left) > len(right):
        return left
    else:
        return right


def getLongestPath(tree):
    longest_path = []
    tmp = []
    glp(tree, longest_path)
    print longest_path

getLongestPath(p)

- abhishek August 20, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

share my java codes

public static List<List<Integer>> findLongestPath(TreeNode root){
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){
            return res;
        }
        
        helperFindPath(root,res);
        return res;
    }
    
    public static List<List<Integer>> helperFindPath(TreeNode root,List<List<Integer>> res){
          List<List<Integer>> ans = new ArrayList<>();
          if(root==null){
              List<Integer> list = new ArrayList<>();
              ans.add(list);
              return ans;
          }
          if(root.left==null && root.right==null){
              List<Integer> temp = new ArrayList<>();
              temp.add(root.val);
              ans.add(temp);
              return ans;
          }
        
          List<List<Integer>> left_list = helperFindPath(root.left,res);
          List<List<Integer>> right_list = helperFindPath(root.right,res);
         
          for(List<Integer> left:left_list){
              for(List<Integer> right:right_list){
                  List<Integer> temp = new ArrayList<>();
                  temp.addAll(left);
                  temp.add(root.val);
                  temp.addAll(right);
                  if(res.size()!=0 && res.get(0).size()<temp.size()){
                      res.clear();
                      res.add(temp);
                  }else if(res.size()==0 || res.get(0).size()==temp.size()){
                      res.add(temp);
                  }
                  
                  if(left.size()>right.size()){
                      List<Integer> list = new ArrayList<>();
                      list.add(root.val);
                      list.addAll(left);
                      ans.add(list);
                  }else if(left.size()<right.size()){
                      List<Integer> list = new ArrayList<>();
                      list.add(root.val);
                      list.addAll(right);
                      ans.add(list);
                  }else{
                      List<Integer> list1 = new ArrayList<>();
                      List<Integer> list2 = new ArrayList<>();
                      list1.add(root.val);
                      list1.addAll(left);
                      list2.add(root.val);
                      list2.addAll(right);
                      ans.add(list1);
                      ans.add(list2);
                  }
              }
          }
          
          return ans;
          
    }

- tiandiao123 September 07, 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