## Facebook Interview Question for Software Engineer / Developers

• 3
of 3 votes

Country: United States
Interview Type: Phone Interview

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

For binary tree:

``````preorder traversal:
{
if( i'm null ) return;

add "me.data" to end of a vector/arrayList;

if( my chilren are both null ) print out the vector/arrayList;

recurse into left child;
recurse into right child;

delete last element of the vector/arrayList (e.g. removing me.data);
}``````

For graph do DFS with a check for visited flags (do the check before extending path there) using same idea above.

NOTE: preorder(tree) == DFS(graph) - (need for visited flags)

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

Who interviewed you? Why does it say "Later..." ?

I've seen this on a programming challenge website.

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

This was an actual interview I got and I wrote myself the problem statement, the fact that it's similar to another question you've seen is merely a coincidence.

And yet, at the end of the day you'll have to take my word for it... that's career cup's way.

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

Same as Sound Wave's solution.
Here's the pseudo code.

``````void printGraph(Node *root) {
static DeQueue<int> q;   // this is store a path. DeQueue to access from front and back.
static set<Node*> visited;
if (NULL == root) {
// this will print the contents of q from head to tail. this is a full path.
printDeQueue(q);
return;
}
visisted.insert(root); // mark node as visited.
q.push(root->data);
Node *c;
for_each(c in root->children){
if(visited.find(c) != visited.end()) { //already visited. cycle.
printDeQueue(q); // print the path
continue;
}
q.push_back(c);
printGraph(c);
q.pop_back();
}
}``````

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

``````#include "stdafx.h"
#include "iostream"
#include "string"
#include "stack"
using namespace std;
class Node {
public:
Node * left_child;
Node * right_child;
Node(){
left_child = NULL;
right_child = NULL;
}
bool is_leaf(){
return !left_child && ! right_child;
}

};
struct Tree {

stack <string> path;
Node * head;
void print_node (Node * node, string ss) {
if(node == NULL) {
return;
} else if(node->is_leaf()){
path.push(ss.append("/"));
cout<<ss<<endl;
} else {
string buffer1 = ss;

buffer1.append("/leftchild");

string buffer2 = ss;
buffer2.append("/rightchild");
print_node(node->left_child, buffer1);

print_node(node->right_child, buffer2);

}
}
void print_path(void){
print_node(head, "");
}
};

int main(int argc, _TCHAR* argv[])
{
Tree tree;
Node head;
Node left;
Node right;
Node left_left;
left.left_child = &left_left;
head.left_child = &left;
head.right_child = &right;
tree.head = &head;
tree.print_path();
int i;
string ss = "this";
string s2 (ss);
s2.append("//");
cout<< ss<<endl;
cout<<s2<<endl;
cin >> i;
return i;
}``````

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

PHP version

Part 1: print all paths of a binary tree

``````// class for Binary Tree Node
class BinaryNode {
public \$value;
public \$left;
public \$right;

public function __construct(\$value) {
\$this->value = \$value;
\$this->left = null;
\$this->right = null;
}

public function isLeaf() {
return (\$this->left === null && \$this->right === null);
}
}

// Class for Binary Tree
class BinaryTree {
private \$_root;

public function __construct() {
\$this->_root = null;
}

public function isEmpty() {
return \$this->_root === null;
}

public function insert(\$value) {
\$node = new BinaryNode(\$value);

if (\$this->isEmpty()) {
\$this->_root = \$node;
} else {
\$this->_insertNode(\$node, \$this->_root);
}
}

private function _insertNode(BinaryNode \$node, &\$subTree) {
if (\$subTree === null) {
\$subTree = \$node;
}
// right insert
elseif (\$node->value > \$subTree->value) {
\$this->_insertNode(\$node, \$subTree->right);
}
// left insert
elseif (\$node->value < \$subTree->value) {
\$this->_insertNode(\$node, \$subTree->left);
}
}

public function getRoot() {
return \$this->_root;
}
}

function printAllTreePaths(BinaryTree \$tree) {
\$root = \$tree->getRoot();
\$treePath = '';

recurseNode(\$root, \$treePath);
}

function recurseNode(BinaryNode \$node, \$treePath) {

\$treePath .= \$node->value;

// if we've hit a leaf, print the current path
if (\$node->isLeaf()) {
echo \$treePath . "\n";
return;
}

// check and recurse left node
if (\$node->left !== null) {
recurseNode(\$node->left, \$treePath . '<L>');
}

// check and recurse right node
if (\$node->right !== null) {
recurseNode(\$node->right, \$treePath . '<R>');
}
}

// create and fill the tree

\$myTree = new BinaryTree();

for (\$i = 0; \$i < 100; \$i++) {
\$myTree->insert(mt_rand(1,10000));
}

// print the tree
printAllTreePaths(\$myTree);``````

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

``````public static void printPathsBT(Node root){
if(root == null) return;
System.out.print(root.data);
root.marked = true;

if(root.left != null && root.left.marked == false)
printPaths(root.left);
if(root.right != null && root.right.marked == false)
printPaths(root.right);
}

public static void printPathsGraph(Node root){
if(root == null) return;

System.out.print(root.data);
root.marked = true;

for(Node neighbor : root.getNeighbors()){
if(neighbor.marked == false){
printPaths(neighbor);
}
}
}``````

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

``````public IEnumerable<string> PrintAllPaths(TreeNode root)
{
var list = new List<string>();
if (root == null)
return list;

var path = new List<int>();

return list;
}

private void PrintAllPaths(TreeNode node, List<int> path, List<string> list)
{
if (node == null)
return;

path.Add(node.Value);
if (node.Left == null && node.Right == null)
{
var sb = new StringBuilder();
foreach (var item in path)
sb.Append(item).Append(", ");
list.Add(sb.ToString());
}

PrintAllPaths(node.Left, path, list);
PrintAllPaths(node.Right, path, list);

path.RemoveAt(path.Count - 1);
}``````

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

For both the problem its gonna be DFS with the slight change of printing the path before calling recursion. I will write the algo for the graph one.

``````for node in all_nodes:
DFS(path, node) {
print path
if node in path:
return
for child in node.children:
DFS(path+node, child)}``````

The visited flag logic is insufficient here as we might have to visit a node more than once if its a part of more than 1 path.

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