Google Interview Question for Software Engineer Interns


Country: United States




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

/* Interpretation of the question: Given an N-ary tree, find 
   the longest sequence (path) in it.
   Longest sequence: Longest sequence of vertices without 
   using a vertice twice by following the edges of the tree. 
   That is the longest path from one leave to an other leave or, 
   if no two leaves exist the path from the leave to the root.
 
   Solution idea:
 
   1) brute force: do from every Vertex a bfs to any other vertex
      time: O(V*V)
	  disadvantage besideds time complexity: does not work well on 
	  usual tree structure, so I had to construct a graph first. 
   2) improved brute force: just do it from every leave 
      (vertex with degree 1): minor improvement
   3) Use tree structure and do it top down in O(V):
      start with root
	  do a postorder traversal, ask each child for the maxBranchPath 
	  and the maxDiametrePath
	  -maxBranchPath is the longest path from any leave of the tree 
	  rooted at a specific node to that specific node, not includinig 
	  that node
	  -maxDiametrePath is the longest path from any leave of the 
	  tree rooted at a specific node to either any other leave of that 
	  node or to that node (latter is equal to the maxBranchPath)
	  but not including that node 
	  
  	  Keep track of the two largest maxBranchPath from the children
	  if the length of the sum of this two branch paths + 1 > 
	  maxDiameterePath a new maxDiametere is found.

	Implementation for simplicity with raw pointers
*/

#include <vector>
#include <utility>
#include <iostream>

class NNode
{
public:
	using Path = std::vector<const NNode*>;

private:
	int value_;
	std::vector<NNode*> children_;
	
	// maxDiametrePath and maxBranchPath are out parameteres
	void getMaxDiametreMaxBranch(Path& maxDiametrePath, Path& maxBranchPath) const
	{		
		maxDiametrePath.clear();
		maxBranchPath.clear();

		Path maxBranchPath2;

		for(auto c : children_)
		{
			Path diametrePath, branchPath;			
			c->getMaxDiametreMaxBranch(diametrePath, branchPath);
			if(diametrePath.size() > maxDiametrePath.size())
			{
				maxDiametrePath = std::move(diametrePath);
			}
			if(branchPath.size() > maxBranchPath.size())
			{
				maxBranchPath2 = std::move(maxBranchPath);
				maxBranchPath = std::move(branchPath);
			} 
			else if(branchPath.size() > maxBranchPath2.size())
			{
				maxBranchPath2 = std::move(branchPath);
			}
		}

		if(maxDiametrePath.size() == 0) 
		{
			maxDiametrePath.push_back(this);
		}
		maxBranchPath.push_back(this);

		int newDiametrePathSize = maxBranchPath.size() + maxBranchPath2.size(); 
		if(newDiametrePathSize > maxDiametrePath.size())
		{
			maxDiametrePath.resize(newDiametrePathSize);
			std::copy(maxBranchPath.begin(), maxBranchPath.end(), maxDiametrePath.begin());
			std::copy(maxBranchPath2.rbegin(), maxBranchPath2.rend(), 
				maxDiametrePath.begin() + maxBranchPath.size());
		}
	}

public:
	NNode(int value) : value_(value) { }

	Path getMaxDiametrePath() const
	{
		Path maxPath, maxBranch;
		getMaxDiametreMaxBranch(maxPath, maxBranch);
		return maxPath;
	}

	void addChild(NNode* child)  
	{
		children_.push_back(child);
	}	

	int getValue() const { return value_; }
};


int main()
{
	NNode n1(1);
	NNode n2(2);
	NNode n3(3);
	NNode n4(4);
	NNode n5(5);
	NNode n6(6);
	NNode n7(7);
	NNode n8(8);
	NNode n9(9);
	NNode n10(10);
	NNode n11(11);
	NNode n12(12);
	NNode n13(13);
	NNode n14(14);
	NNode n15(15);

	n14.addChild(&n15);
	n11.addChild(&n14);
	n9.addChild(&n13);
	n7.addChild(&n11);
	n7.addChild(&n12);
	n7.addChild(&n10);	
	n7.addChild(&n9);
	n6.addChild(&n8);
	n2.addChild(&n6);
	n2.addChild(&n7);
	n1.addChild(&n2);
	n1.addChild(&n3);
	n1.addChild(&n4);
	n1.addChild(&n5);

	std::cout << "max diametre path from n1" << std::endl;
	for(auto n : n1.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl << std::endl << "max diametre path from n6" << std::endl;
	for(auto n : n6.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl << std::endl << "max diametre path from n5" << std::endl;
	for(auto n : n5.getMaxDiametrePath())
		std::cout << n->getValue() << " ";

	std::cout << std::endl;
	return 0;

}

/* output:
max diametre path from n1
15 14 11 7 2 6 8 

max diametre path from n6
8 6 

max diametre path from n5
5
*/

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

public class Solution {
	private static final int nary;

	class Node {
		public Node[] nodes;
		public int data;
		public boolean endNode;
		
		public Node(int data, boolean endNode=false) {
			this.data = data;
			this.endNode = endNode;
			if(!this.endNode)
				this.nodes = new Node[nary];
		}
	}

	public static void main(String[] args) {
		nary = 4;
		Node root = new Node(1);


	}

	public static ArrayList<Node> longestPath(Node node) {
		ArrayList<Node> list
		if(node.endNode) {
			list = new ArrayList<>();
			list.add(node);
		} else {
			ArrayList<Node>[] returns = new ArrayList<Node>[nary];
			int highestCount = 0;
			int highest = 0
			for(int i=0; i < nary; i++) {
				returns[i] = longestPath(node.nodes[i]);
				if(returns[i].size() > highestCount)
				{
					highestCount = returns[i].size();
					highest = i;
				}
			}
			list = returns[highest];
			list.add(node);
		}
		return list;
	}

	public static ArrayList<Node> longestSubsequence(Node root) {
		ArrayList<Node>[] returns = new ArrayList<Node>[nary];
		int highestCount = 0;
		int highest = 0
		int secondHighestCount = 0;
		int secondHighest = 0;
		for(int i=0; i < nary; i++) {
			returns[i] = longestPath(root.nodes[i]);
			if(returns[i].size() > highestCount)
			{
				secondHighest = highest;
				secondHighestCount = highestCount
				highestCount = returns[i].size();
				highest = i;
			} else if(returns[i].size() > secondHighestCount) {
				secondHighestCount = returns[i].size();
				secondHighest = i;
			}
		}
		ArrayList<Node> alist = returns[secondHighest];
		Collections.reverse(alist);
		alist.add(root)
		alist.add(returns[highest]);
		return alist;
	}

}

- aforarup October 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

What does it mean by longest sequence? Does it necessarily mean longest path in which case its always leaf to leaf?

- mrsurajpoudel.wordpress.com October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Imagining this as the longest path problem :

// to store all the paths x/y/z form
ALL_PATHS = list()
// how to enumerate all root to leaf
def enumerate_paths( node , path ){
    if ( empty(node.children) ) {
       // add the path, because node is leaf
       ALL_PATHS += path
       return // nothing more is to be done
    }
    for ( c : node.children ){
       // recurse into it
       enumerate_paths ( c , path +'/' + c.id )
    }
}
// enumerate all the paths
enumerate_paths ( root, '' )
/* all these paths are from root to leaf,
so find a pair such that :
1. The overlap is only at root
2. And is max length */
len = #|ALL_PATHS|
max = [ '' , '' , 0 ]
for ( i : [0:len] ){
   for ( j : [i + 1 : len] ){
       p1 = ALL_PATHS[i] ; p2 = ALL_PATHS[j]
       a = p1.split('/') ; b = p2.split('/')
       total_len = size(a) + size(b)
       // a.0 == b.0 means overlap, e.g. /x/y , /x/z
       if ( a[0] != b[0] && total_len > max.2 ){
          max.0 = p1 ; max.1 = p2 ; max.2 = total_len
       }
   }
}
// here we have everything
println ( max )
// and note that we are still less than 42 lines

- NoOne October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

why not do in-order traversal, then use DP to find longest subsequence?

- Anonymous October 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Note that n-ary tree is nothing but an acyclic Directed-Graph with a starting node given (root).
The longest sequence from leaf to leaf is the pair of longest two root-to-leaf paths. We will return the longest two paths in n-ary tree.
So, we use our own Directed-Graph data structure to solve this problem.

Output: [[1, 5, 15, 21, 19], [1, 2, 7, 9, 11, 25]], where 1 is the root.

// No weight of edges considered.
public class DiGraph<T>{
    	private class GraphNode<T>{
    		private T data;
    		private HashSet<GraphNode<T>> neighbors;

    		public GraphNode(T data){
        		this.data = data;
        		neighbors = new HashSet<>();
    		}
	}
    	private HashMap<T, GraphNode<T>> allNodes;
}

public class LongestPathN_aryTree {

    public ArrayList<ArrayList<Integer>> getLongestPath(GraphNode<Integer, Integer> startNode){
        if(startNode == null) return null;

        Queue queue = new Queue();
        queue.enqueue(startNode);

        ArrayList<Integer> list = new ArrayList<>();
        list.add(startNode.getData());
        queue.enqueue(list);

        // We do not have to store all Paths and then find the longest two.
        // We save/update the longest two paths each time a leaf node is met.

        // init variables for referencing maxSizePath and secondMaxSizePath
        int maxListSize = -1;
        ArrayList<Integer> maxList = null;

        int secondMaxListSize = -1;
        ArrayList<Integer> secondMaxList = null;

        while(!queue.isEmpty()){
            GraphNode<Integer, Integer> currNode = (GraphNode<Integer, Integer>) queue.dequeue();
            ArrayList<Integer> currPath = (ArrayList<Integer>)queue.dequeue();
            int currPathSize = currPath.size();
            if(currNode.getNeighbors().size() == 0){
                if(maxListSize < currPathSize){
                    secondMaxListSize = maxListSize;
                    secondMaxList = maxList;

                    maxListSize = currPathSize;
                    maxList = currPath;
                }else if(secondMaxListSize < currPathSize){
                    secondMaxListSize = currPathSize;
                    secondMaxList = currPath;
                }

                continue;
            }

            for(GraphNode<Integer, Integer> nbr : currNode.getNeighbors()){
                ArrayList<Integer> currPathCopy = new ArrayList<>(currPath);
                currPathCopy.add(nbr.getData());

                queue.enqueue(nbr);
                queue.enqueue(currPathCopy);
            }
        }

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        result.add(secondMaxList);
        result.add(maxList);

        return result;
    }

    public static void main(String[] args) {
        DiGraph<Integer,Integer> graph = new DiGraph<>();

        graph.addEdge(1, 2);
        graph.addEdge(1, 5);
        graph.addEdge(1, 3);
        graph.addEdge(1, 4);
        graph.addEdge(2, 7);
        graph.addEdge(7, 9);
        graph.addEdge(2, 10);
        graph.addEdge(5, 15);
        graph.addEdge(15, 21);
        graph.addEdge(9, 11);
        graph.addEdge(21, 19);
        graph.addEdge(11, 25);

        LongestPathN_aryTree longestPathN_aryTree = new LongestPathN_aryTree();

        GraphNode<Integer, Integer> graphNode = graph.getNode(1);

        ArrayList<ArrayList<Integer>> result = longestPathN_aryTree.getLongestPath(graphNode);

        System.out.println(result);
    }
}

- jsayyy October 30, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

What about doing a topological sort and then start a BFS from first TS result element?
Complexity would be O(V)

- Cristi November 07, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class NtreeUtil {
	
	public static void main(String[] args) {
		Ntree root = createNtree();
		getLongestSequence(root);
		
	}
	
	/**         1
	 		  / | \
             /  |  \
            2   3   4
           / \      |  
          5   6     7   
          |         |
          8         9
          |         |
		 10		   11
	 * @return
	 */
	public static Ntree createNtree(){
		
		Ntree root = new Ntree(1);
		//1--->2
		root.addChildren(2);
		//1--->3
		root.addChildren(3);
		//1--->4
		root.addChildren(4);
		
		//1-->2--->5
		root.getChildren(2).addChildren(5);
		//1-->2--->6
		root.getChildren(2).addChildren(6);
		
		//1-->2-->-->5--->8
		root.getChildren(2).getChildren(5).addChildren(8);
		//1-->2-->-->5--->8--->10
		root.getChildren(2).getChildren(5).getChildren(8).addChildren(10);
				
		//1--->4--->7
		root.getChildren(4).addChildren(7);
		//1--->4--->7--->9
		root.getChildren(4).getChildren(7).addChildren(9);
		//1--->4--->7--->9--->11
		root.getChildren(4).getChildren(7).getChildren(9).addChildren(11);
		return root;
	}
	
	
	
	
	
	/**
	 * USE BFS and see which nodes are leafs  and which have max depths.
	 * Remember two nodes. 
	 * @param root
	 */
	static void getLongestSequence(Ntree root){
		Queue<Ntree> parentQueue = new LinkedList<Ntree>();
		Queue<Ntree> childQueue = new LinkedList<Ntree>();
		
		parentQueue.add(root);
		int currentHeight =1;
		int maxHeight1 =0, maxHeight2=0;
		Ntree node1=null, node2=null;
		while(!parentQueue.isEmpty()){
			Ntree currentNode = parentQueue.poll();
			
			//Remember the leaf node1 which is at max height.
			if(currentHeight>maxHeight1){
				node1 = currentNode;
				maxHeight1 = currentHeight;
			}
			//Remember the leaf node2 which is at max height other than node1.
			if((currentHeight> maxHeight2) &&(currentNode.getData() != node1.getData())){
				node2 = currentNode;
				maxHeight2 = currentHeight;
			}
			
			//Load all children lets visit later in to seperate Queue.
			childQueue.addAll(currentNode.getChildren());
			if(parentQueue.size() !=0 ){
				System.out.print(currentNode.getData() +"-->");
			}else{
				//Ok we are moving to next level.
				System.out.print(currentNode.getData() +"\n");
				
				//OK all done with Parent
				parentQueue = childQueue;
				childQueue  = new LinkedList<Ntree>();
				currentHeight++;
			}
			
		}
		System.out.println(" Longest path statrts from :"+ node1.getData() +"  to "+ node2.getData());
	}
	
	
}


// Here is the class which is the DTO 

public class Ntree {
	private int data;
	private Set<Ntree> children = new LinkedHashSet<Ntree>();

	public Ntree(int data){
		this.data = data;
	}
	
	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

	public Set<Ntree> getChildren() {
		return children;
	}

	public void setChildren(Set<Ntree> children) {
		this.children = children;
	}

	public Set<Ntree> addChildren(int data){
		Ntree childNode = new Ntree(data);
		getChildren().add(childNode);
		return getChildren();
	}

	public Ntree getChildren(int data){
		for(Ntree child:children){
			if(child.getData() == data){
				return child;
			} 
		}
		return null;
	}

	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + data;
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Ntree other = (Ntree) obj;
		if (data != other.data)
			return false;
		return true;
	}
	
	
}

- reddymails November 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think longes sequence is always leaf to leaf. So just for each node find max depthLeft+maxDepthRight and find maximum of them. Is it so simple or I didn't get it?

- Zhassan November 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node(object):
    def __init__(self, data):
        self.data = data
        self.child = []
    
    def longest_seq(self):
        seq = []
        cnt = 1 + self.longest_seq_helper(-1) + self.longest_seq_helper(1)
        seq.append(cnt)
        
        for child in self.child:
            seq.append(child.longest_seq())
        
        return max(seq)
        
    
    def longest_seq_helper(self, direction):
        data = self.data
        seq = [0]
        for child in self.child:
            cnt = 0
            if child.data - data == direction:
                cnt += 1
                cnt += child.longest_seq_helper(direction)
            seq.append(cnt)
        return max(seq)

- Nitish Garg December 26, 2016 | 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