## Facebook Interview Question for Software Engineer / Developers

• 3

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

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;
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){
}
};

int main(int argc, _TCHAR* argv[])
{
Tree tree;
Node left;
Node right;
Node left_left;
left.left_child = &left_left;
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;

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

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.

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.