Interview Question Software Engineer / Developers

• 0

Here is a good one i recently came accorss.
Really appriciate if someone could help me code this in Java

The Tree Structure is

``````34
/       |      \
3        56      12
/    \                |
89       7             22
|
78``````

Print elements of a n-ary tree(a tree which may have more than two elements) breadth first reverse starting with the last level
nodes and up. The code need to fit the following method and interface.

method name: void displayBFSReverse (Node head);

Where Node implements the interface:

interface Node {

public String getNodeData ();

public List<Node> getChildren ();

}

The function should return:
78 22 7 89 12 56 3 34

Country: United States
Interview Type: Phone Interview

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

Algo:
Use 1 stack and 1 queue.. Add node to queue. Get the top node from queue. Push all children in queue. When all children have been pushed, add the node to stack and repeat. at end print the stack....

psuedocode:

``````initQueue(Q)
initStack(S)
enqueue(Q, root)
while (!isEmpty(Q) {
node = dequeue(Q);
for (i = 0; i < node->childrens; i++)
enqueue(Q, node[i]);

push(S,node);
}

while(!isEmpty(S))
print(pop(s));``````

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

insert the nodes in the queue like normal BFS .but use a dequeue and insert till all elements are done. after that remove from the rear of the queue(the side where last element was inserted).

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

<Extended Problem>
It would have been interesting if the question also asked to print the level number along with its elements. To be more clear, since this is ReverseBFS, an output like:
Level n : Node 100,99,88,
Level n-1: ......
Level n-2: ...................

Just wondering with the same datastructure of queue that we are currently using, can we also infer level?

Simply pushing the values in Queue (right to left), and then pushing them to stack (so that values can later be printed left to right) won't fetch us level number. Am I right here?
Do we need a dummy separator element for marking the end of a level?

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

it is simple, but your answer is wrong Singleton. You know nothing about the internal structure of a Node. You just have the interface. nothing in the problem statement says that you know there is a node.left or a node.right. you just have access to children. The simplest and most obvious method is to use recursion.

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

How do you plan to do it using recursion. We basically want a queue to get children and with recursion you can simulate the working of stack. It would be helpful if you elaborate your idea and I am missing something.

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

#In normal BFS, we normally start with putting root in a queue. Then while queue is not empty, we take the front node, enqueue it's 2 (or n) children, and print the node's data.
#The variation in this problem would be - instead of printing the node's data, push the node onto a stack. And when the queue becomes empty, print all stack nodes.

Makes sense?

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

it should work. But when you enqueue child nodes, be sure that you do it from right to left (in the reversed order).

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

``````package interview.tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class Q13870718
{
static class Node
{
private String data;
private List<Node> children;

public Node(final String data)
{
this.data = data;
this.children = new ArrayList<Node>();
}

public Node(final String data, final Node... children)
{
this.data = data;
this.children = new ArrayList<Node>(Arrays.asList(children));
}

public String getNodeData()
{
return this.data;
}

public List<Node> getChildren()
{
return Collections.unmodifiableList(this.children);
}
}

public static void displayBFSReverse(final Node head)
{
Stack<Node> s = new Stack<Node>();
Node cur;
while((cur = q.poll()) != null)
{
s.push(cur);
for (Node child : cur.getChildren())
{
q.offer(child);
}
}

while(!s.empty())
{
System.out.print(s.pop().getNodeData() + " ");
}
}

public static void main(String[] args)
{
Node tree = new Node(
"34",
new Node("3",
new Node("89"),
new Node("7")),
new Node("56"),
new Node("12",
new Node("22",
new Node("78"))));

System.out.print("BFSReverse: "); displayBFSReverse(tree); System.out.println();
}
}``````

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

``````public static void displayBFSReverse2(final Node head)
{
for (int i = h; h > 0; i--)
{
}
}

public static void printLevel(final Node head, final int level)
{
if(level == 0)
{
}
else
{
for (int i = head.getChildren().size(); i--> 0; )
{
}
}
}

private static int height(final Node head)
{
{
return 0;
}
else
{
int h;
for (int i = 1; i < head.getChildren().size(); i++)
{
if(max < h)
{
max = h;
}
}
return 1 + max;
}
}``````

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

Why do people put their homework question as google interview questions???

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

What makes you think its homework, home works are mostly straight forward questions, I was once asked to reverse a n-ary tree in an interview, does that sound like homework to you as well. This is an interview question :)

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

we can implement it with bredth first search algo using stack

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

public void BFSTranverse(Node startNode) {
while (startNode != null) {
if (startNode.childs != null && startNode.childs.size() > 0) {
for (int i = 0; i < startNode.childs.size(); i++) {
}
}
count ++;
startNode = queue.size() > count ? queue.get(count) : null;
}
Collections.reverse(queue);
for (Node node: queue) {
System.out.print(node.data + " ");
}
}

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

store the nodes you walk in normal BFS in a list. Reverse the list. Print.

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

Use BFS, but instead of printing the node values, push it to the stack.
Once BFS gets completed, print the stack.

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

``````public void displayTree_BreadthFirst(Node root) {
Stack<Node> stack = new Stack<Node>();
stack.push(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.printf("%3d", node.element);
if (node.left != null) {
stack.push(node.left);
}
if (node.right != null) {
stack.push(node.right);
}
}
System.out.println();
while (!stack.isEmpty()) {
System.out.printf("%3d", stack.pop().element);
}
}``````

Output:
Regular BFS = 1 2 3 4 5 6
Reverse BFS = 6 5 4 3 2 1

Space = Queue + Stack.

Question sounds fairly simple, was it asked without additional storage or only using a Queue and no stack?

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

Hi Singleton, its not a binary tree, its a n-ary tree, so assuming a left and a right node is incorrect.

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

This is definitely homework question!!
This guy has posted the same question under Google and Amazon..
Even if u were asked the same question in both the interviews(probability is very less) why is there any need to put the same question twice?

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

Its not home work, i asked it twice cuz i needed more answers, who asks this in a homework, nywyas, but i agree I am at fault as i posted it twice, sorry but i am desperate for a good answer :)

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

``````void ReverseBFS(Node* root)
{
if (!root)
return;

List<Node*> children = root->getChildren();

while(!end of children) {
ReverseBFS(child);
}

cout << root->PrintData();
return;
}``````

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

That's actually incorrect. If you look at the example input,
once you've reached the leaf nodes under node 3, according to your logic, just print.

So it will print out 89 and 7 before it does print 78. You need a way of determining that you've parsed the entire tree.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

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.