Google Interview Question Software Engineer Interns
Country: United States
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
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)
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;
}
}
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);
}
}
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;
}
}
- Chris October 18, 2016/* 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 */