## Google Interview Question for Software Engineer / Developers

• -3

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

Graph has Vertices and Edges, I am not sure what they mean by leaf node in a Graph. What does it mean? Can some one calrify what exactly the question is?

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

why it is a graph, sounds like a tree.

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

what do u mean by Starting Node and Ending Node in a Graph?

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

To find the path, start at the end and work your way back (since each node only has one parent) if the start node is not found fail.

Now then, how do you define "Finding a leaf node"?

1) If a finding a leaf node means finding a node with "no children" on the path, then the only possible leaf node on the path from start point to end point (inclusive) is the end point, and only if the end point has no children.

2) if a finding a leaf node means finding a node that has childless children, then, as you traverse back, check all children of each node in the path to see if any are childless

3) if finding a leaf node means finding each childles child of each node in the path, then, as you travers back, check all children of each node and count how many have no children themselves.

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

Union DFS (start node) with DFS (end node)? While DFS from start node, insert all nodes into a hashtable, and when searching from end node, do not traverse nodes already in the hashtable.

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

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

I think this is recursive. If found end node. press teh boolean button for the parent. Add at the end to whatever state keeping structure you have. When you recourse back, rinse, up to the top.

When you call your boolean should always be false. It is only when you return that it can become true.

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

Do the level order traversal of the given tree (graph) from the starting node to the end node and record all the nodes with no children.

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

I am assuming that when we traverse from starting node to the ending node, we should record all the intermediate leaf nodes (if encountered any ).

BFS aka Level order traversal should work.

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

Preorder traverse the tree and annotate each node with the enter time and leave time, the difference between leave time and enter time of the leaf node is one. (time start at one and metric is one).

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

I think this is actually a graph with a source and sink. There can be leaf nodes in between which have no child nodes. End node is a special leaf node.

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

Assuming the graph is a binary tree :

``````boolean populateList(Node root, LinkedList<Node> list, Node start, Node end) {
if (root != null) {
if (root.left == null && root.right == null)
{
if (root == start)
if (list != null)
if (root == end)
return true;
}
else {
if (populateList(root.left, list, start, end))
return true;
if (root == start)
if (root == end)
return true;
return populateList(root.right, list, start, end);
}
}

return false;
}``````

Comment hidden because of low score. Click to expand.

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.