Facebook Interview Question Software Developers
Country: United States
Interview Type: Phone Interview
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])
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");
nodes.add(assign1);
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");
nodes.add(assign2);
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");
nodes.add(assign3);
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");
nodes.add(result);
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);
}
}
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;
}
}
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>();
symbols.Add( buildX() );
symbols.Add( buildY() );
symbols.Add( buildZ() );
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
Add, // add left and right children
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" );
}
}
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
vs.
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)
and return expression as
of course things like types and other semantic rules need to be defined...
- Chris August 13, 2017