## Booking.com Interview Question for SDE-2s

Country: United States

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

A simple recursive algorithm. Not checking for null because I am assuming Node[] children only contains non-null.

``````public class RightSibling {
class Node {
public Node[] children;
public Node right;
}

public void populateRightSiblings(Node node) {
for(int i=0; i<children.length; i++) {
Node child = node.children[i];
if(i < children.length - 1) {
child.right = node.children[i+1];
}
populateRightSiblings(child);
}
}
}``````

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

Sunny,
is it node.right or child.right = node.children[i+1]?

-Ram

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

This is incomplete. At depth 2 the right of the first child's right most child is not set accurately. How about this (in python):

``````class Node(object):
def __init__(self, value, children = None, right = None):
if children:
self.children = children
else:
self.children = []

self.right = right
self.value = value

def show(self, tab = 0):
print ("{0} Item {1}".format("\t" * tab, self.value))
print ("{0} Right {1}".format("\t" * tab, self.right))
for c in self.children:
c.show(tab + 1)
def setRight(root)
q = list()
q.append(root)
q.append(None)

while len(q) > 0:
n = q[0]
q.remove(n)
if n != None:
for item in n.children:
q.append(item)

if len(q) > 0:
if q[0] != None:
n.right = q[0]
else:
q.append(None)

root.show(0)``````

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

Here's an approach with O(d) extra space, where d is the depth of the tree.

``````public void populateRightSiblings(Node root) {
if (root == null || root.children == null || root.children.length < 2) {
return;
}
Deque<Node> queue = new ArrayDeque<Node>();
List<Node> rightMost = new ArrayList<>();
int level = 0;
int currentLevelCount = 1;
int nextLevelCount = 0;
while (!queue.isEmpty()) {
Node node = queue.poll();
Node [] children = node.children;
nextLevelCount += children.length;
currentLevelCount--;
if (currentLevelCount == 0) {
level++;
currentLevelCount = nextLevelCount;
nextLevelCount = 0;
}
for (int i = 0; i < children.length-1; i++) {
children[i].right = children[i+1];
}
if (level >= rightMost.size()) {
} else if (children != null && children.length != 0) {
rightMost.get(level).right = children[0];
rightMost.set(level, children[children.length-1]);
}
}
}``````

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

private static class Node {
public Node[] children;
public Node right;
private int value;

public Node(int value) {
this.value = value;
}

private void populateRightSiblings(Node node) {
if (node == null || node.children == null || node.children.length < 2)
return;

if (node.children.length > 1) {
Node lastChild = node.children[node.children.length - 1];
node.right = lastChild;
}

for (Node child : node.children) {
populateRightSiblings(child);
}
}

@Override
public String toString() {
return String.valueOf(value);
}
}

public static void main(String[] args) {
Node _1 = new Node(1);
Node _6 = new Node(6);
Node _8 = new Node(8);
Node _11 = new Node(11);
Node _13 = new Node(13);
Node _15 = new Node(15);
Node _17 = new Node(17);
Node _22 = new Node(22);
Node _25 = new Node(25);
Node _27 = new Node(27);

_1.children = new Node[]{_6};
_8.children = new Node[]{_1,_11};
_13.children = new Node[]{_8,_17};
_17.children = new Node[]{_15,_25};
_25.children = new Node[]{_22,_27};

Node root = _13;
root.populateRightSiblings(root);
System.out.println(root);
}

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

private static class Node {
public Node[] children;
public Node right;

private void populateRightSiblings(Node node) {
if (node == null || node.children == null || node.children.length < 2)
return;

if (node.children.length > 1) {
Node lastChild = node.children[node.children.length - 1];
node.right = lastChild;
}

for (Node child : node.children) {
populateRightSiblings(child);
}
}
}

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

``````/**
* @author Omid Ghiasi Tarzi
*/
static void setRights(Node node) {
Node preNode = null;
for (Node child : node.children) {
child.right = preNode;
preNode = child;
setRights(child);
}
}``````

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.