Evaluate Boolean Expression - Solution & Explanation

Problem Overview: Each row in the Expressions table stores a boolean comparison such as x > y or a = b. The operands reference variable names whose numeric values live in the Variables table. Your task is to evaluate every expression by resolving both operands and returning whether the comparison is true or false.

Approach 1: Equi-Join + CASE Expression (O(n), O(1))

The core idea is to replace variable names with their actual numeric values before evaluating the operator. You achieve this by joining the Expressions table with the Variables table twice: once for the left_operand and once for the right_operand. These are standard equi-joins where Expressions.left_operand = Variables.name and Expressions.right_operand = Variables.name. Each join resolves a variable reference into its numeric value.

After both operands are resolved, evaluate the comparison using a CASE expression. The CASE block checks the operator column (>, <, or =) and performs the corresponding comparison between the joined values. For example, when the operator is '>', compare left_value > right_value. SQL returns the final result as 'true' or 'false' depending on whether the condition holds.

This approach works because SQL joins effectively transform symbolic operands into actual numbers before evaluation. The database engine scans the Expressions rows once and resolves both operands through indexed lookups in the variables table. With proper indexing on Variables.name, the join remains efficient and scales well for larger datasets.

Time complexity is O(n) where n is the number of expressions, assuming indexed lookups for variable names. Each expression requires two joins and a constant-time comparison. Space complexity is O(1) beyond the query result since the database processes rows in a streaming fashion.

This problem primarily tests your understanding of database query composition, multi-table lookups with joins, and conditional evaluation using SQL expressions. The trick is recognizing that the operands are not values yet—they must first be resolved through joins.

Recommended for interviews: The equi-join plus CASE expression solution is the expected approach. It demonstrates that you understand relational lookups and conditional logic in SQL. A naive solution using repeated subqueries works but is less efficient and harder to read. Interviewers typically look for the clean join-based query because it mirrors how relational databases are designed to evaluate cross-table relationships.