## Facebook Interview Question for Software Developers

Country: United States
Interview Type: Phone Interview

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

is the expression an AST? meaning for example

``````*
/    \
a       +
/    \
1      2

was originally a * (1+2)``````

is the order of the expressions given in such a way there exists a solution without the need to reorder

``````x = 2
y = 2
return x * y``````

vs.

``````return x * y
x = 2
y = 3``````

if so, then I would suggest to treat assign expressions in a way that the left node provides the variable name and the right node is the expression being evaluated recursively (of course can and should be done in a more OO way)

``````variables[assignment.left] = evaluate(assignment.right, variables)
def evaluate(root, variables):
if isinstance(root, BinaryOp):
if root.operator = '+':
return evaluate(root.left) + evaluate(root.right)
elif root.oeprator = '*':
return evaluate(root.left) * evaluate(root.right)
elif isinstance(root, VariableRef):
return variables[root.variableName]
elif isinstance(root, Number)
return root.value
raise "error"``````

and return expression as

``return evaluate(return.expression, variables)``

of course things like types and other semantic rules need to be defined...

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

This question ain't that clear.. A little bit of more explanation was definitely needed..

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

Humm for me the question as an input you have an array of trees with operators, they share the memory between them so you can have variables. As an output you have to return the result of the trees that have an operation of return. Here is the code in python that solves the problem. (As I think it is)

``````class node:
def __init__(self, value):
self.value = value
self.right = self.left = None

def AnalyzeClousure():
mem = dict()
def _(root):
# Integer
if type(root.value) == int: return root.value
# Variable
if type(root.value) == str and len(root.value) == 1\
and root.value not in "+-*/":
if root.value in mem:
return mem[root.value]
else:
return root.value

# Return
if root.value == 'Return': return AnalyzeTree(root.left)

op = root.value
left = AnalyzeTree(root.left)
right = AnalyzeTree(root.right)

if op == 'Assign': mem[left] = right
if op == '+': return left + right
if op == '-': return left - right
if op == '*': return left * right
if op == '/': return left / right
return _
AnalyzeTree = AnalyzeClousure()

a = node("Assign")
a.left = node("x")
a.right = node('+')
a.right.left = node(2)
a.right.right = node(3)

b = node("Return")
b.left = node("x")

print map(AnalyzeTree, [a, b])``````

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

This question is pretty straightforward. Result is -4720. You need to maintain a symbol lookup table (x = 5, y = 4970, etc.)

``````public class ExpressionTree {

public static void main(String... args) {
ArrayList<node> list = get();
for (node n : list) {
eval(n);
}
}

static HashMap<String, Integer> lookup = new HashMap<String, Integer>();

static int eval(node n) {
if (n == null) return 0;
if (n.L == null && n.R == null) {
try {
return n.getInt();
} catch (NumberFormatException e) {
//lookup symbol table
return lookup.get(n.value);
}
}

if (isOperator(n)) {
int l = eval(n.L);
int r = eval(n.R);
switch (n.value.charAt(0)) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
} else if (n.value.equals("Assign")) {
lookup.put(n.L.value, eval(n.R));
return 0;
} else if (n.value.equals("Return")) {
int result = eval(n.R);
System.out.println(result);
return 0;
}

throw new IllegalArgumentException("unknown node value " + n.value);
}

static boolean isOperator(node n) {
return n.value.equals("+") || n.value.equals("-") || n.value.equals("*") || n.value.equals("/");
}

static ArrayList<node> get() {
ArrayList<node> nodes = new ArrayList<node>();
node assign1 = new node("Assign");
assign1.L = new node("x");
assign1.R = new node("+");
assign1.R.L = new node("2");
assign1.R.R = new node("3");

node assign2 = new node("Assign");
assign2.L = new node("y");
assign2.R = new node("-");
assign2.R.L = new node("5000");
assign2.R.R = new node("30");

node assign3 = new node("Assign");
assign3.L = new node("z");
assign3.R = new node("*");
assign3.R.L = new node("50");
assign3.R.R = new node("x");

node result = new node("Return");
result.R = new node("-");
result.R.L = new node("z");
result.R.R = new node("*");
result.R.R.L = new node("1");
result.R.R.R = new node("y");

return nodes;
}

}

class node {
public String value;
public node L, R;
public node(String value) {
this.value = value;
}
public int getInt() {
return Integer.valueOf(value);
}``````

}

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

The key here is to maintain a hash table with previously computed variables:

``````#include "Common.h"

static std::unordered_map<std::string, int> Variables;

static bool is_number(const std::string& str)
{
if(str.empty())
return false;
else
return (str.find_first_not_of("0123456789") == std::string::npos);
}

struct ASTNode
{
enum eOperator { kNone, kPlus, kMin, kStar, kDiv, kAssign, kReturn };

eOperator _operator = kNone;

ASTNode* _left;
ASTNode* _right;
std::string _value;

ASTNode(eOperator oper, ASTNode* left, ASTNode* right)
: _operator(oper)
, _left(left)
, _right(right)
{
}

ASTNode(const std::string& value)
: _left(NULL)
, _right(NULL)
, _value(value)
{
}

bool isLeaf() const { return (_left == NULL) && (_right == NULL); }

int processValue()
{
switch(_operator) {
case kNone:
if(Variables.count(_value)) {
return Variables[_value];
}
if(!is_number(_value)) throw std::string("Leaf node is not a number. " + _value);
return atoi(_value.c_str());
case kPlus:
return _left->processValue() + _right->processValue();
case kStar:
return _left->processValue() * _right->processValue();
case kMin:
return _left->processValue() - _right->processValue();
case kDiv:
return _left->processValue() / _right->processValue();
case kAssign: {
int rv = _right->processValue();
Variables[_left->_value] = rv;
return rv;
}
default:
case kReturn: {
return _right->processValue();
}
}
}
};

void compute_tree()
{
{
ASTNode* l = new ASTNode("2");
ASTNode* r = new ASTNode("3");
ASTNode* op = new ASTNode(ASTNode::kPlus, l, r);

ASTNode* xNode = new ASTNode("x");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "x=2+3=" << assign->processValue() << std::endl;
}

{
ASTNode* l = new ASTNode("5000");
ASTNode* r = new ASTNode("30");
ASTNode* op = new ASTNode(ASTNode::kMin, l, r);

ASTNode* xNode = new ASTNode("y");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "y=5000-30=" << assign->processValue() << std::endl;
}

{
ASTNode* l = new ASTNode("50");
ASTNode* r = new ASTNode("x");
ASTNode* op = new ASTNode(ASTNode::kStar, l, r);

ASTNode* xNode = new ASTNode("z");
ASTNode* assign = new ASTNode(ASTNode::kAssign, xNode, op);
std::cout << "z=50*x=" << assign->processValue() << std::endl;
}

{
ASTNode* l = new ASTNode("1");
ASTNode* r = new ASTNode("y");
ASTNode* op1 = new ASTNode(ASTNode::kStar, l, r);

ASTNode* z = new ASTNode("z");
ASTNode* op2 = new ASTNode(ASTNode::kMin, z, op1);

// for the "return" node , we only compute the right node
ASTNode* assign = new ASTNode(ASTNode::kReturn, NULL, op2);
std::cout << "z-(1*y)=" << assign->processValue() << std::endl;
}

}``````

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

This is pretty vague and could definitely use some more explanation on what they're trying to get at ... but here's my stab at it.

``````using System;
using System.Collections.Generic;

// -------------------------------------------------------------
class Solution
{

// -------------------------------------------------------------
static void Main(string[] args)
{
List<Node> symbols = new List<Node>();

int result = evaluate( buildTest(), symbols );
Console.WriteLine( "Result: {0}", result );

}

// -------------------------------------------------------------
enum Type
{

// values
Int,          // node defines an int value
Symbol,       // node defines a symbol

// operations
Subtract,     // sub left and right children
Multiply,      // mul left and right children

// evaluations
Return,       // eval right tree and return

// symbol definitions
Assign,       // defines a symbol and its value, left symbol is the eval of right

}

// -------------------------------------------------------------
class Node
{

// all nodes have a type decribing what do with with
public Type Type;              // the node type

// for nodes that hold values
public string SymbolValue;     // symbol value
public int IntValue;           // int value

// children nodes as required for anything except int and symbol nodes
public Node Left;
public Node Right;

// constructors
public Node( Type type ) { Type = type; }
public Node( string symbolValue ) { Type = Type.Symbol; SymbolValue = symbolValue; }
public Node( int intValue ) { Type = Type.Int; IntValue = intValue; }

}

// -------------------------------------------------------------
static Node buildX()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "x" );
root.Right = new Node( Type.Add );
root.Right.Left = new Node( 2 );
root.Right.Right = new Node( 3 );
return root;
}

// -------------------------------------------------------------
static Node buildY()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "y" );
root.Right = new Node( Type.Subtract );
root.Right.Left = new Node( 5000 );
root.Right.Right = new Node( 30 );
return root;
}

// -------------------------------------------------------------
static Node buildZ()
{
Node root = new Node( Type.Assign );
root.Left = new Node( "z" );
root.Right = new Node( Type.Multiply );
root.Right.Left = new Node( 50 );
root.Right.Right = new Node( "x" );
return root;
}

// -------------------------------------------------------------
static Node buildTest()
{
Node root = new Node( Type.Return );
root.Right = new Node( Type.Subtract );
root.Right.Left = new Node( "z" );
root.Right.Right = new Node( Type.Multiply );
root.Right.Right.Left = new Node( 1 );
root.Right.Right.Right = new Node( "y" );
return root;
}

// -------------------------------------------------------------
static Node findSymbol( string symbol, List<Node> symbols )
{

// sanity
if (string.IsNullOrEmpty( symbol ) || symbols == null)
{
return null;
}

foreach (Node symbolNode in symbols)
{
if (symbolNode.Left.SymbolValue == symbol)
{
return symbolNode;
}
}

return null;

}

// -------------------------------------------------------------
static int evaluate( Node node, List<Node> symbols )
{

// sanity
if (node == null)
{
throw new System.InvalidOperationException( "Invalid node" );
}

switch (node.Type)
{

// values
case Type.Int: return node.IntValue;
case Type.Symbol:
{
Node symbolNode = findSymbol( node.SymbolValue, symbols );
if (symbolNode == null)
{
throw new System.InvalidOperationException( "Invalid symbol" );
}
return evaluate( symbolNode.Right, symbols );
}

// operations
case Type.Add: return evaluate( node.Left, symbols ) + evaluate( node.Right, symbols );
case Type.Subtract: return evaluate( node.Left, symbols ) - evaluate( node.Right, symbols );
case Type.Multiply: return evaluate( node.Left, symbols ) * evaluate( node.Right, symbols );

// actions
case Type.Return: return evaluate( node.Right, symbols );

// assignments are not evaluated, they define symbols
case Type.Assign: break;

}

throw new System.InvalidOperationException( "Node cannot be evaluated" );

}

}``````

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.