Google Interview Question
Software Engineer / DevelopersCountry: United States
public class BinaryExpressionTree
{
enum Operator
{
add(true), subtract(false), multiply(true), divide(false);
private boolean symmetric;
private Operator(boolean symmetric)
{
this.symmetric = symmetric;
}
boolean compare(OperatorNode a, OperatorNode b)
{
if (a.left.isEqual(b.left) && a.right.isEqual(b.right))
return true;
if (symmetric)
{
return (a.left.isEqual(b.right) && a.right.isEqual(b.left));
}
return false;
}
}
abstract class Node
{
abstract boolean isEqual(Node other);
}
class OperatorNode extends Node
{
Operator operator;
Node left;
Node right;
@Override
boolean isEqual(Node other)
{
if (!(other instanceof OperatorNode))
{
return false;
}
OperatorNode n = (OperatorNode) other;
if (operator != n.operator)
{
return false;
}
return operator.compare(this, n);
}
}
class LeafNode extends Node
{
String value;
@Override
boolean isEqual(Node other)
{
if (!(other instanceof LeafNode))
{
return false;
}
LeafNode n = (LeafNode) other;
return value.equals(n.value);
}
}
boolean compare(Node a, Node b)
{
return a.isEqual(b);
}
}
package google;
import google.ExpressionTreeEvaluation.ExpressionTreeNode.Operator;
public class ExpressionTreeEvaluation {
public static class ExpressionTreeNode {
static enum Operator {
Add, Subtract, Multiply, Divide;
public int performOperation(int operand1, int operand2) {
switch (this) {
case Add:
return operand1 + operand2;
case Subtract:
return operand1 - operand2;
case Multiply:
return operand1 * operand2;
default:
return operand1 / operand2;
}
}
}
public Boolean isLeaf;
public Operator valIfOperator;
public Integer valIfInteger;
ExpressionTreeNode left;
ExpressionTreeNode right;
public ExpressionTreeNode(boolean isLeaf, Operator valIfOperator, Integer valIfInteger) {
this.isLeaf = isLeaf;
if (isLeaf == true && valIfOperator == null && valIfInteger != null) {
this.valIfInteger = valIfInteger;
} else if (isLeaf == false && valIfOperator != null && valIfInteger == null) {
this.valIfOperator = valIfOperator;
} else {
throw new IllegalArgumentException();
}
left = null;
right = null;
}
}
public static void main(String args[]) {
ExpressionTreeNode n1 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode n2 = new ExpressionTreeNode(false, Operator.Divide, null);
ExpressionTreeNode n3 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode n4 = new ExpressionTreeNode(true, null, 5);
ExpressionTreeNode n5 = new ExpressionTreeNode(true, null, 5);
ExpressionTreeNode n6 = new ExpressionTreeNode(true, null, 6);
ExpressionTreeNode n7 = new ExpressionTreeNode(true, null, -1);
n1.left = n2;
n1.right = n3;
n2.left = n4;
n2.right = n5;
n3.right = n7;
n3.left = n6;
ExpressionTreeNode en1 = new ExpressionTreeNode(false, Operator.Add, null);
ExpressionTreeNode en2 = new ExpressionTreeNode(true, null, 3);
ExpressionTreeNode en3 = new ExpressionTreeNode(true, null, 3);
en1.left = en2;
en1.right = en3;
System.out.println(evaluateExpression(n1) == evaluateExpression(en1));
}
private static int evaluateExpression(ExpressionTreeNode node) {
if (node.isLeaf) {
return node.valIfInteger;
} else {
int left = evaluateExpression(node.left);
int right = evaluateExpression(node.right);
return node.valIfOperator.performOperation(left, right);
}
}
}
// This solution assumes in-order, though this question could be changed to pre-order or post-order.
// This solution also assumes that a node is a value when it is a leaf, and is an expression otherwise
// Code in C++
struct Node
{
Node* left;
Node* right;
double val;
std::string exp; // --, ++, +, -, *, /
}
bool checkTrees(Node* left, Node* right)
{
if (left == NULL && right != NULL) return false;
if (left != NULL && right == NULL) return false;
return eval(left) == eval(right);
}
double eval(Node* node)
{
if (node->left == node-> right == NULL)
return node->val;
if (node->left == NULL && node-> right != NULL)
return compute(node->right, node->val);
if (node->left != NULL && node-> right == NULL)
return compute(node->left, node->val);
return compute(eval(node->left), node->exp, eval(node->right));
}
double compute(double valu, const std::string& exp)
{
if (exp == "--") return val - 1.0;
if (exp == "++") return val + 1.0;
// ERROR - Invalid tree
return 0.0;
}
double compute(double left, const std::string& exp, double right)
{
if (exp == "+") return left + right;
if (exp == "-") return left - right;
if (exp == "*") return left * right;
if (exp == "/") return left / right;
// ERROR - Invalid tree
return 0.0;
}
- Anonymous March 17, 2017