Facebook Interview Question for Software Engineer / Developers


Country: China
Interview Type: Phone Interview




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

two different ways:
1) write with parentheis : root(left subtree string)(right subtree string)
2) write in-order sequence and (post-order or pre-order) sequence

- samuel February 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Get idea from your (1), and implement it.

class Solution {
	public static String treeToString(TreeNode root) {
		StringBuilder ret = new StringBuilder("{");
		if(root == null) ret.append("#");
		else {
			ret.append(root.val);
			if(root.left != null || root.right != null) {
				ret.append(treeToString(root.left));
				ret.append(treeToString(root.right));
			}
		}
		ret.append("}");
		return ret.toString();
	}

	public static TreeNode stringToTree(String str) {
		// get current tree
		str = str.substring(1, str.length() - 1);	// remove {}
		if(str.charAt(0) == '#') return null;
		int val = str.charAt(0) - '0';
		str = str.substring(1);	// remove root
		TreeNode left = null, right = null;
		int leftBraceCount = 0;
		if(str.length() > 0) {	// has childs
			for(int i = 0; i < str.length(); i++) {
				char ch = str.charAt(i);
				if(ch == '{') leftBraceCount++;
				if(ch == '}') leftBraceCount--;
				if(leftBraceCount == 0) {	// we find left and right child
					left = stringToTree(str.substring(0, i + 1));
					right = stringToTree(str.substring(i + 1));
					break;
				}
			}
		}
		TreeNode root = new TreeNode(val, left, right);
		return root;
	}

	public static void main(String[] args) {
		TreeNode root = constructTree();
		String str = treeToString(root);
		root = stringToTree(str);
	}
}

- usunyu March 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

/** my implementation */

#include <iostream>
#include <string>
#include <deque>

struct BinTreeNode {
    int val;
    BinTreeNode *left, *right;

    BinTreeNode() {}

    BinTreeNode(int v, BinTreeNode *l = NULL, BinTreeNode *r = NULL):
        val(v), left(l), right(r)
    {}
};

void bin_tree_to_str(BinTreeNode *root, std::string& str)
{
    if (root == NULL) return;

    std::deque<BinTreeNode *> que;
    BinTreeNode *p;

    que.push_back(root);

    str.append(std::to_string(root->val));

    while (!que.empty()) {
        //undef NDEBUG
        //std::cout << "curr size: " << que.size() << std::endl;

        p = que.front();
        que.pop_front();

        //undef NDEBUG
        //std::cout << "size after pop_font: " << que.size() << std::endl;

        //undef NDEBUG
        //std::cout << p->val << std::endl;

        //leaves
        if (p->left == NULL && p->right == NULL) continue;

        str.append("L");

        if (p->left) {
            que.push_back(p->left);
            str.append(std::to_string(p->left->val));
        } else {
            str.append("#");
        }

        str.append("R");

        if (p->right) {
            que.push_back(p->right);
            str.append(std::to_string(p->right->val));
        } else {
            str.append("#");
        }
    }

    std::cout << str << std::endl;
}

BinTreeNode *str_to_bin_tree(const std::string& str)
{
    std::deque<std::string> que;
    size_t i, j, l;

    for (i = 0, j = 0, l = str.size();
         i < l;
         /* void */) {
        while (str[i] != 'L' && i < l) i++;

        std::string ss = str.substr(j, i - j);

        que.push_back(ss);

        if (i == l) break;

        j = i + 1;
        i++;

        while (str[i] != 'R' && i < l) i++;

        ss = str.substr(j, i - j);

        que.push_back(ss);

        j = i + 1;
        i++;
    }

    std::deque<BinTreeNode *> que2;
    std::string str_val;
    BinTreeNode *root, *left, *right;
    BinTreeNode *temp;

    str_val = que.front();
    que.pop_front();

    root = temp = new BinTreeNode(std::stoi(str_val));

    que2.push_back(temp);

    //while (!que2.empty()) {
    while (!que.empty()) {
    //for (i = 0, l = (que.size() - 1) / 2; i < l; i++) {
        temp = que2.front();
        que2.pop_front();

        str_val = que.front();
        que.pop_front();

        if (str_val == "#") left = NULL;
        else left = new BinTreeNode(std::stoi(str_val));

        str_val = que.front();
        que.pop_front();

        if (str_val == "#") right = NULL;
        else right = new BinTreeNode(std::stoi(str_val));

        temp->left = left;
        temp->right = right;

        if (left) que2.push_back(left);
        if (right) que2.push_back(right);
    }

    return root;
}

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

When serializing a binary tree, treat it as a complete binary tree (not a full binary tree), like adding NULL pointer to a single-child node (not really added).

When deserializing a string to a binary tree, first extract real contents (BinTreeNode.val) into a assistant double-ended queue, by removing L or R in between. And then constructing the binary tree, using another double-ended queue to maintain parents/children relationship.

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

Compared to the implementation by Preorder & Inorder traversal, the level-order implementation use more assistant storage. When the tree is sparse, possibilities are more memory are wasted.

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

Here's the tested code:

#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <stdlib.h>

using namespace std;

struct Node {
    long data;
    Node* left;
    Node* right;

    Node(long d) : data(d), left(0), right(0) {}
};

void serialize (Node* root, stringstream& os)
{
    if (!root) {
      os << "$ ";
      return;
    }

    os << root->data << " ";
    serialize(root->left, os);
    serialize(root->right, os);
}

Node* deserialize (stringstream& os)
{
    string tok;

    os >> tok;

    if (tok == "$")
        return 0;
   
    Node* root = new Node(stoi(tok));

    root->left = deserialize(os);
    root->right = deserialize(os);

    return root;
}

int main()
{
    Node* root = new Node(4);
    root->left = new Node(2);
    root->left->right = new Node(3);
    root->left->right->left = new Node(1);
    root->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    stringstream os;
    serialize(root, os);

    cout << os.str() << endl;

    Node* dup = deserialize(os);

    stringstream os2;
    serialize(dup, os2);
    cout << os2.str() << endl;
    return 0;
}

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

void serialize(node *head, string &serial)
{
	if(head == 0)
	{
		serial += "#,";
		return;
	}
	serial += to_string(head->value)+",";
	serialize(head->left,serial);
	serialize(head->right,serial);
}
void deserialize(node * &head, string &serial, int &index)
{
	
	int fou = serial.find(",",index);
	string curr_val = serial.substr(index,fou - index);
	index = index + curr_val.length() + 1;

	if(curr_val == "#")
	{
		head = 0;
		return;
	}
	else
	{
		
		head = new node;
		//assuming values here are integers
		head->value = atoi(curr_val.c_str());
		deserialize(head->left,serial,index);
		deserialize(head->right,serial,index);
	}
}

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

You can use BFS to serialize the tree. Then, you simply need to insert the values in order to get the same exact tree. The order is:
"Root R L RR RL LR LL RRR RRL RLR RLL LRR LRL..."

I implemented a simple BST with "insert" only.

from Queue import *

class bst_node(object):
    def __init__(self, p, l, r, v):
        self.parent = p
        self.right = r
        self.left = l
        self.value = v
    

class bst(object):
    def __init__(self):
        self.root = 0
        
        
    def insert(self, value):
        if self.root == 0:
            self.root = bst_node(0, 0, 0, value)
        else:
            x = self.root
            while True:
                if x.value < value:
                    if x.right == 0:
                        x.right = bst_node(x, 0, 0, value)
                        break
                    else:
                        x = x.right
                else:
                    if x.left == 0:
                        x.left = bst_node(x, 0, 0, value)
                        break
                    else:
                        x = x.left


def serialize(b):
        q = Queue(maxsize = 0)
        q.put(b.root)
        s = ""            
        while not q.empty():
            node = q.get()
            if node.right != 0:
                q.put(node.right)
            if node.left != 0:
                q.put(node.left)
            # print this
            if q.empty():
                s = s + str(node.value)
            else:
                s = s + str(node.value) + " "
        return s
            

def deserialize(string_bst):
    values = string_bst.split(" ")
    b = bst()
    for k in range(0, len(values)):
        value = int(values[k])        
        b.insert(value)
    return b
    
    

numbers =[-5, 3, -2, 5, 10, 12, 11] 

first_bst = bst()
for n in range(0, len(numbers)):
    first_bst.insert(numbers[n])
    
str_first = serialize(first_bst)
print "First BST Serialized to:", str_first

second_bst = deserialize(str_first)
str_second = serialize(second_bst)

print "Second BST serialized to:", str_second

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

public static void serialize(Node root, OutputStreamWriter out){
	if(root==null){
		out.write(‘|’);
		return;
	}

	out.write(root.data+””);
	serialize(root.left);
	serialize(root.right);
}

public static Node deserialize(InputStreamReader reader) throw IOException{
	char c = (char)reader.read();
	if(c==’|’){
		return null;
	}
	Node n = new Node(c);
	n.left=deserialize(reader);
	n.right=deserialize(reader);
}

- guest March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The Country is China? WTF????

- TerrorGeek June 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Should clarify with the interviewer what is the type of data the node holds.

Assuming the serialized data can fit into a char (it simplify, but don't impact the general principle): the most space efficient way I can think of is to use a string where the children of node at index n are placed at 2n+1 (left) and 2n+2 (right).

- CreativeChips June 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

4 possible ways:
- write pre/post order along with inorder
- write with parenthesis
- write like complete binary tree
- write like <node val>, <node id>, <L/R child>, <parent id>

- sw August 05, 2014 | 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