Square Interview Question (Dev Bootcamp)

problem1.markdown

Question 1:

Let's assume you are building a programming language for only boolean values, that is, true and false: true, false

(Variables: a, b, c... (booleans))

1. You support the 3 boolean operations, AND (&&), OR (||), and NOT (!):

a && b
a || b
!a
!(a || (b && !c))

2. You can represent an expression as a tree:

   &&
  /  \
 a    b

        !
       /
      ||
      /\
     a  &&
        /\
        b !
         /
        c

Or using reverse Polish notation:

["a", "b", "&&"]
["a", "!"]
[a, b, c, !, &&, ||, !]

PROBLEM: Now write a function evaluate that takes an object representing the expressions, along with a dictionary of variables and their corresponding values, so that the function returns the final evaluated value of the expression:

evaluate(expression, dict : string -> boolean) --> true/false
evaluate(a || b, { a : true, b : false }) --> true
evaluate(!!a, { a : false }) --> false

problem2.markdown

Question 2:

Expand on the above evaluate function and write a new function that takes 2 expressions and determines if they will always return the same value for all values of the variables. is_equiv should return True if the expressions return the same evaluated value for all values of the variables, and False otherwise.

# is_equiv(expr1, expr2, list of vars) --> true/false

So for:

# is_equiv(a || b, b || a, ["a", "b"]) --> true
# { a : false, b : false } = 00 = 0
# { a : false, b : true } = 01 = 1
# { a : true, b : false } = 10 = 2
# { a : true, b : true } = 11 = 3

And for:

# is_equiv(a, !a, ["a"]) --> false
# { a : false }