Facebook Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

Another simple Java solution similar to some of the C++ ones. We could avoid having 2 additional fields by extracting them into a value type that can be returned.

private static Node<Integer> head;

private static Node<Integer> tail;

private static void flattenRecursive(Node<Integer> n) {
	if (n == null) {
		return;
	} else {
		flattenRecursive(n.left);
		if (head == null) {
			head = n;
			tail = head;
		} else {
			tail.right = n;
			n.left = tail;
			tail = n;
		}
		flattenRecursive(n.right);
	}
	// Could make the list circular here
}

- dph March 30, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

But here aren't you basically flattening the given Binary Tree into a Doubly Linked List?

- Nikhil June 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

This is the solution that I though in the interview.

So in order to make the tree a linked list you need to get the the last element from the list from the right and the first element from the list of the left.

Previously I've solved it returning a Tuple<Node,Node> with the first and last node of the "list".
But this is the right solution some variables could be removed but it is a mess not to have then for reference.

public static Node ConvertToList(Node root)
{
	Node first = root;
	Node last = root;

	if(root == null)
		return null;

	Node previous = ConvertToList(root.Left);
	Node next = ConvertToList(root.Right);

	root.Left = root;
	root.Right = root;

	if(previous != null)
	{
		first = previous;
		last = first.Left;

		last.Right = root;
		root.Left = last;
		first .Left = root;
		root.Right = first;
		
		last = root;
	}

	if(next != null)
	{	
		last = next.Left;
		last.Right = first;
		next.Left = root;
		root.Right = next;
	}

	return first;
}

- Nelson Perez February 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

I ran into a similar question in the past. The difference is that the final list was not circular. Here is the code I wrote for that question. Again, this is not the full answer since the list is not circular, but a simple tweak would do the job.

def listfy(node):
        if node is None: 
            return None, None
        
        # Listfy the children first so the current node only needs to be 
        # inserted between the lists created from its children
        l_head = l_tail = r_head = r_tail = None
        if node._left:
            l_head, l_tail =listfy(node._left)
        if node._right:
            r_head, r_tail = listfy(node._right)
            
        if not l_tail and not r_head:
            return node, node
        else:
            # if there is a list to the left, the current node becomes 
            # the new tail of that list and the head of the full list remains 
            # the same. Otherwise, the current node is the head of the 
            # current list.
            if l_tail:
                l_tail._right = node
                node._left = l_tail
            else:
                l_head = node
            
            # If there is a list to the right, the current node becomes
            # the new head of that list and the tail of the full list remains
            # the same. Otherwise, the current node is the tail of the
            # the current list.
            if r_head:
                node._right = r_head
                r_head._left = node
            else:
                r_tail = node
                
        return l_head, r_tail

- daniel.a.p March 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Something like the following:

We modify an inorder traversal to keep track of pointers to the "current" Node we are on in the list. We can also keep track of the head and tail of the list and after the inorder traversal, we simply link up the ends of the lists to make it circular.

I wrote this quickly, so there may be some syntax bug with the pointer logic (haven't done C pointers in a while) but I think it is the correct logic:

makeCircularList(Node treeHead) {
	
	Node *head;
	Node *tail;
	Node *current; 
	
	modInorder(treeHead, current, head, tail);

	tail -> right = *head;
	head -> left = *tail;
}


modInorder(Node n, Node *current, Node * head, Node * tail) {
	
	if (n == NULL) {

		return;
	}

	Node previous;

	if (*head == NULL) {

		head = &n;
	}

	tail = &n;

	previous = modInorder(n.left, current);

	current -> right = n;
	current = &n;
	current -> left = previous;

	modInorder(n.right, current)

}

- SK February 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure if it works as the signature of the function changed when you call it.

But I did had the same mistake as I forgot to make the current.Right.Left = current and current.Left.Right = current to make it a double linked list even though in the pseudo code I did.

- Nelson Perez February 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include "stdafx.h"
#include "stack"
#include "iostream"


using namespace std;
struct node {
	node(int val, node* left, node* right):val(val),left(left),right(right){}
	node(int val):val(val),left(NULL),right(NULL){}
	node* left;
	node* right;
	int val;
};

node* prev_node = NULL;
node* first = NULL;

void build_double_list(node* root)
{
	if(!root) {
		return;
	}
	build_double_list(root->left);

	if(!prev_node){
		first = root;
	}
	else {
		root->left = prev_node;
		prev_node->right = root;
		
	}
	prev_node = root;
	
	build_double_list(root->right);
}

node* convert_to_double_list(node* root)
{
	build_double_list(root);
	if(!first) {
		return NULL;
	}
	first->left = prev_node;
	prev_node->right = first;
	return first;
}



int _tmain(int argc, _TCHAR* argv[])
{
	//node n1(1),n2(2),n4(4),n7(7),n9(9),//leaf nodes
	//	n3(3,&n2,&n4),n5(5,&n1,&n3),n8(8,&n7,&n9),n6(6,&n5,&n8);//n6 is root
	//// output is 1 5 2 3 4 6 7 8 9

	node n6(6);
	node* circ_double_ptr = convert_to_double_list(&n6);

	node* cur = circ_double_ptr;
	do {
		cout << cur->val << " ";
		cur = cur->right;
		_ASSERT(cur->left->right == cur);
		_ASSERT(cur->right->left == cur);
	}
	while(cur != circ_double_ptr);


	return 0;
}

- Anonymous February 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Node * convert(Node * root)
{
	if (root == NULL)
		return root;
		
	Node *left = convert(root->left);
	if (left)
	{
		while (left->right)
		{
			left = left->right;
		}
		left->right = root;
		root->left = left;
	}
	
	Node *right = convert(root->right);
	if (right)
	{
		while (right->left)
		{
			right = right->left;
		}
		right->left = root;
		root->right = right;
	}
	
	return root;
}

Node * treeToList(Node* root)
{
	Node *head = convert(root);
	Node *tail = head;
	if (!head)
		return NULL;
		
	while (head->left || tail->right)
	{
		if (head->left) head = head->left;
		if (tail->right) tail = tail->right;
	}
	
	head->left = tail;
	tail->right = head;
	
	return head;
}

- thinhdu February 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node
{
    Node* left;
    Node* right;
    int val;
}

Node* f(Node* root)
{
    if(!root) return nullptr;
    Node* head = nullptr;
    ff(root, &head);
    return head;
}

void ff(Node* root, Node** head)
{
    if(root->left)
    {
        ff(root->left, head);
    }
    Node* right = root->right;
    add(head, root);
    if(right)
    {
        ff(right, head);
    }
}

void add(Node** head, Node* newNode)
{
    if(*head == nullptr)
    {
        *head = newNode;
        *head->right = *head;
        *head->left = *head;
        return;
    }
    newNode->left = head->left;
    newNode->right = head;
    head->left = newNode;
}

- nane March 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I've seen this question on here before. Here's the solution I have typed up from the previous time I saw it (IIRC this isn't the original way I solved it, but rather someone else's answer that had a better solution than mine):

void convertToCircularDLL(Node *root)
{
	static Node *prev;
	static Node *head;

	if (root == NULL)
	{
		return;
	}
	convertToCircularDLL(root->left);
	if (prev == NULL)
	{  // first node in list
		head = root;
	}
	else
	{
		prev->right = root;
		root->left = prev;
	}
	prev = root;
	convertToCircularDLL(root->right); 
	if (prev->right == NULL)
	{ // last node in list
		head->left = prev;
		prev->right = head;
	}
}

EDIT: Thinking about it again, this is wrong. It works...once. If you made tried to convert more than one tree, it wouldn't work because the prev and head pointers are static, so they would still contain data from the previous run. This can be fixed by making them Node** parameters to the function. The initial call can be made with the addresses of two Node pointers initialized to NULL.

Node *prev = NULL, *head = NULL;
convertToCircularDLL(root, &prev, &head);

- Nick March 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

TreeNode[] registr = new TreeNode[2];
 convertBinaryTreeToCL(t1, registr);

public static void convertBinaryTreeToCL(TreeNode node, TreeNode[] register) {
        if(node == null)
            return ;

        convertBinaryTreeToCL(node.left, register);

        TreeNode head = register[0];
        TreeNode prev = register[1];

        if(head == null) {
            register[0] = head = node;
        }
        else {
            node.left = prev;
            prev.right = node;

        }
        register[1] = prev = node;

        convertBinaryTreeToCL(node.right, register);

        if(prev.right == null) {
            prev.right = head;
            head.left = prev;
        }

    }

- dxchen1 March 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <cstdlib>
#include <iostream>

using namespace std;

struct Node;
typedef pair<Node*, Node*> bounds;

struct Node {
	Node *l, *r;
	int data;
	
	Node(int d) : data(d) { }
	
	bounds flatten() {
		bounds t, b(this, this);
		if (l) {
			t = l->flatten();
			b.first = t.first;
			t.second->r = this;
			l = t.second;
		}
		if (r) {
			t = r->flatten();
			b.second = t.second;
			t.first->l = this;
			r = t.first; 
		}
		return b;
	}
};

int main() {

	Node *root = new Node(1);
	...
	bounds b = root->flatten();
	
	return 0;
}

- nikolay.dimitrov April 05, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is equivalent to convert a BST to a doubly linked list. To make the Doubly linked list circular we can simply traverse the list (once created) to find the end.

- xmlprgrm June 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To flatten the tree, in-order search is used and queue was used to store node in order.
Running time of this algorithm is O(n).

#include <list>
#include <iostream>
using namespace std;

struct node {
	int value;
	node * left;
	node * right;
	node(int v):value(v), left(0), right(0){}
};

void inorder_tree(node * r, list<node*>& queue)
{
	if (!r)
		return;
	inorder_tree(r->left, queue);
	queue.push_back(r);
	cout << r->value <<" ";
	inorder_tree(r->right, queue);
}

node * flatten_tree(node * root)
{
	list<node*> queue;
	inorder_tree(root, queue);
	node* prev=0, * cur = 0, *start = 0;
	list<node*>::iterator iter;
	for(iter= queue.begin(); iter != queue.end(); iter++)
	{
		cur = (*iter);
		if (prev == 0)
		{
			cur->left = cur;
			start = cur;
		}
		else {				
			cur->left = prev;
			prev->right = cur;
		}
		prev = cur;
	}
	prev->right = prev;
	return start;
}

- hankm2004 July 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If no additional memory is allowed, the following algorithm can achieve the same running time of O(N).

#include <list>
#include <iostream>
using namespace std;

struct node {
	int value;
	node * left;
	node * right;
	node(int v):value(v), left(0), right(0){}
};

node* head = 0;
node* tail = 0;

void inorder_tree2(node* r)
{
	if (!r)
		return;
	inorder_tree2(r->left);
	if (!head)
	{
		head = tail = r;
	} else {
		tail->right = r;
		tail = r;
	}
	inorder_tree2(r->right);
}

node * flat_tree(node *root)
{
	inorder_tree2(root);
	node * cur = head;
	node * prev = 0;
	while (cur != tail)
	{
		if (!prev)
		{
			cur->left = cur;
		} else {
			cur->left = prev;
		}
		prev = cur;
		cur = cur->right;
	}
	//do something with tail
	tail->left = prev;
	tail->right = tail;
	return head;
}

- hankm2004 July 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

///

void BinaryTreeToLL(const Node *root, Node **newHead)
{
	if (root == NULL || newHead == NULL) {
		return;
	}
	
	if (root->left != NULL) {
		BinaryTreeToLL(root->left);
	}
	
	Node *newNode = new Node();
	newNode->data = root->data;
	
	if (*newHead == NULL) {
		*newHead = newNode;
		newNode->left = newNode->right = newNode;
	} else {
		Node *end = newHead->left;
		end->right = newNode;
		newNode->left = end;
		newNode->right = newHead;
	}
	
	if (root->right != NULL) {
		BinaryTreeToLL(root->right);
	}
}

\\\

- Rohit January 03, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More