Google Interview Question
Software Engineer InternsCountry: 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