## 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):
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;
}

{
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);

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
*/``````

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<>();
} 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];
}
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);
return alist;
}

}``````

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?

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``````

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?

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<>();
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);

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

ArrayList<ArrayList<Integer>> result = new ArrayList<>();

return result;
}

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

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);
}
}``````

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)

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
//1--->3
//1--->4

//1-->2--->5
//1-->2--->6

//1-->2-->-->5--->8
//1-->2-->-->5--->8--->10

//1--->4--->7
//1--->4--->7--->9
//1--->4--->7--->9--->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>();

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.
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);
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;
}

}``````

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?

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)``````

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.

### 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.