## Zynga Interview Question

Interview Type: In-Person

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

Two steps:
(1)link each node with its next sibling(leftest sibling).
(2)print each level's nodes by finding the leftest node of each level then print all its siblings.
Code in C++:

``````void specificBFS(Node* root)
{
if(root == NULL) return;
//link every node with its leftest sibling
root->foo = NULL;
//print from leftest node of each level to all its siblings
for(Node* p = root; p != NULL; ){
printSiblings(p);
if(p->left != NULL) p = p->left;
else if(p->right != NULL) p = p->right;
else p = findFirstNephew(p);
}
}
{
if(p->left != NULL && p->right != NULL){
p->left->foo = p->right;
p->right->foo = findFirstNephew(p);
//here link right child with its sibling first
}
else if(p->left != NULL){
p->left->foo = findFirstNephew(p);
}
else if(p->right != NULL){
p->right->foo = findFirstNephew(p);
}
}
Node* findFirstNephew(Node* p)//find the leftest nephew
{
for(Node* sibling = p->foo; sibling != NULL; sibling = sibling->foo){
if(sibling->left != NULL) return sibling->left;
if(sibling->right != NULL) return sibling->right;
}
return NULL;
}
void printSiblings(Node* p)//print all p's siblings
{
for(; p != NULL; p = p->foo) printf("%d ", p->data);
}``````

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

Logic :
1) Start print the current node and all its siblings
2) If there is a left node , go there and print its siblings
else if it has rightnode, go there and print the siblings
3) if there is no left or right for current node, then search its siblings for one that has a left or right., Then select that node and repeat step 1)

``````void printfBFS (node* root) {
if (root==NULL) return;
node *tmp = root;
while (tmp) {
cout << tmp->data;
tmp = tmp->foo;
}
if (root->left) printBFS (root->left);
else if (root->right) printfBFS (root->right);
else {
while (root) {
if (root->left) {
return printfBFS (root->left);
break;
} else if (root->right) {
return printfBFS (root->left);
break;
}
root = root->foo;
}
return;
}``````

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

It seems that the foo is not pointing to the next sibling as input, but you are asked to "have foo point to the next sibling node" while "print the BFS".
it says "Node *foo //uninitialized - use it the way you like "

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

My idea is to recursively print each level, and let the "foo" of the next level (if there is) connected. Always find the first valid node of next level for recursion. Below code is verified:

struct Node{
int data;
Node* left;
Node* right;
Node* foo;
Node(int a):left(NULL), right(NULL), data(a), foo(NULL) {}
};

void BFS(Node *root){
if(root == NULL){
return;
}
Node *start = root;
while(root != NULL){
printf("%d, ", root->data);
if(root->left != NULL){
if(root->right != NULL){
root->left->foo = root->right;
}
else{
Node *sib = root->foo;
while((sib != NULL) && (sib->left == NULL) && (sib->right == NULL)){
sib = sib->foo;
}
if(sib == NULL){
root->left->foo = NULL;
}
else if(sib->left != NULL){
root->left->foo = sib->left;
}
else{
root->left->foo = sib->right;
}
}
}
if(root->right != NULL){
Node *sib = root->foo;
while((sib != NULL) && (sib->left == NULL) && (sib->right == NULL)){
sib = sib->foo;
}
if(sib == NULL){
root->right->foo = NULL;
}
else if(sib->left != NULL){
root->right->foo = sib->left;
}
else{
root->right->foo = sib->right;
}
}
root = root->foo;
}

while((start != NULL) && (start->left == NULL) && (start->right == NULL)){
start = start->foo;
}
if(start == NULL){
return;
}
else if(start->left != NULL){
BFS(start->left);
}
else{
BFS(start->right);
}
return;
}

int _tmain(int argc, _TCHAR* argv[])
{
Node Node1(1);
Node Node2(2);
Node Node3(3);
Node Node4(4);
Node Node5(5);
Node Node6(6);
Node Node7(7);
Node Node8(8);
Node Node9(9);
Node Node10(10);
Node Node11(11);
Node Node12(12);
Node1.left = &Node2;
Node1.right = &Node3;
Node2.left = &Node4;
Node3.left = &Node5;
Node3.right = &Node9;
Node4.right = &Node6;
Node6.left = &Node7;
Node6.right = &Node8;
Node9.left = &Node10;
Node9.right = &Node11;
Node11.right = &Node12;
BFS(&Node1);
return 0;
}

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

void LevelWithoutQueue(struct Node *node){
if(!node)
return;
while(node){
cout<<node->data;
if(node->left){
if(!node->foo){
node->foo=node->left;
}
else{
struct Node *foo=node->foo;
while(foo && foo->foo)
foo=foo->foo;
foo->foo=node->left;
}
}
if(node->right){
if(!node->foo){
node->foo=node->right;
}
else{
struct Node *foo=node->foo;
while(foo && foo->foo)
foo=foo->foo;
foo->foo=node->right;
}
}
node=node->foo;
}
}

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

Dudes here is the algo:-
Lets assume we have exposed two methods on node with name first and second.

node.first => if node has left child return it otherwise return right child
node.second => if node has right child return it otherwise return left child

The call below recursive function

Node connect(root){
if node.right == null && node.left == null
return root
node.left.foo = node.right.foo
node.left.second = node.right.first
connect(root.left)
connect(root.right)
return root;
}

Of-course you need to take care of some null cases in above algo. Implementing NULL pattern on node would make it easier to handle null cases.

And now print all levels, as they are already connected so it can be printed without any trouble.

Space complexity - O(h), where h is the height of the tree.
Time complexity - O(n), n is no of nodes

Feel free to point out any correction.

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

Solution:
Given 'foo' of a node points to its adjacent/sibling node (all nodes at same depth).
Logic is to loop until all the siblings are visited( All nodes on same depth level).
Move to the next depth level by moving to next left node.

``````public static void printBFS(Node<?> root){
if(root != null){
Node<?> temp = root;
while(temp != null){
System.out.print(temp.data+" - ");
temp = temp.getFoo();
}
if(root.getLeft() != null){
printBFS(root.getLeft());
}

}
}``````

Here is the complete implementation,

``````public class LevelOrder {

/**
* @param args
*/
static class Node<T>{
Node<?> left,right,foo;
T data;

Node(T val){
data = val;
}

/**
* @return the left
*/
public Node<?> getLeft() {
return left;
}

/**
* @return the right
*/
public Node<?> getRight() {
return right;
}
/**
* @return the foo
*/
public Node<?> getFoo() {
return foo;
}
/**
* @param left the left to set
*/
public void setLeft(Node<?> left) {
this.left = left;
}
/**
* @param right the right to set
*/
public void setRight(Node<?> right) {
this.right = right;
}
/**
* @param foo the foo to set
*/
public void setFoo(Node<?> foo) {
this.foo = foo;
}

}

public static void printBFS(Node<?> root){
if(root != null){
Node<?> temp = root;
while(temp != null){
System.out.print(temp.data+" - ");
temp = temp.getFoo();
}
if(root.getLeft() != null){
printBFS(root.getLeft());
}

}
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Node<Integer> one = new Node<Integer>(20);
Node<Integer> two = new Node<Integer>(10);
Node<Integer> three = new Node<Integer>(25);
Node<Integer> four = new Node<Integer>(7);
Node<Integer> five = new Node<Integer>(15);
Node<Integer> six = new Node<Integer>(22);
Node<Integer> seven = new Node<Integer>(5);
Node<Integer> eight = new Node<Integer>(21);
Node<Integer> nine = new Node<Integer>(24);
Node<Integer> ten = new Node<Integer>(17);
Node<Integer> eleven = new Node<Integer>(28);

one.setLeft(two);
one.setRight(three);
two.setLeft(four);
two.setRight(five);
three.setLeft(six);
three.setRight(eleven);
four.setLeft(seven);
five.setRight(ten);
six.setLeft(eight);
six.setRight(nine);

one.setFoo(null);
two.setFoo(three);
four.setFoo(five);
five.setFoo(six);
six.setFoo(eleven);
seven.setFoo(ten);
ten.setFoo(eight);
eight.setFoo(nine);

printBFS(one);

}

}``````

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.