Quick Overview

This question evaluates understanding of parsing, boolean expression semantics, and algorithmic enumeration, including tokenization, operator precedence, exhaustive evaluation over variable assignments, and handling of invalid inputs.

Generate boolean truth table

Company: Kickoff

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a function that, given a string boolean expression, outputs a complete truth table. The expression syntax is: variables are single uppercase letters A–Z; operators are '!' (unary NOT), adjacency (implicit AND), and '+' (binary OR); parentheses '()' are allowed; spaces are ignored. Use precedence: '!' > AND > '+', with left-associative AND and OR. Requirements: ( 1) Parse the expression (handle implicit AND) and validate tokens; ( 2) Extract all distinct variables, sort them alphabetically; ( 3) Enumerate all 2^n assignments and evaluate the expression for each; ( 4) Print rows as variable values followed by the expression’s result. Example: input "!AB + B!D + !(CD)" should produce a table over A,B,C,D with all 16 combinations. Describe your parsing approach (e.g., shunting-yard or recursive descent), data structures used, and analyze time/space complexity. Discuss edge cases such as unmatched parentheses, unknown symbols, or empty input.

Quick Answer: This question evaluates understanding of parsing, boolean expression semantics, and algorithmic enumeration, including tokenization, operator precedence, exhaustive evaluation over variable assignments, and handling of invalid inputs.

Parse a boolean expression with variables A-Z, !, implicit AND, + OR, and parentheses, then return variables and all truth-table rows.

Constraints

  • Inputs are provided as Python literals matching the function signature.
  • Return a deterministic exact-match result.

Examples

Input: ('A+B',)

Expected Output: {'variables': ['A', 'B'], 'rows': [[False, False, False], [False, True, True], [True, False, True], [True, True, True]]}

Explanation: Simple OR.

Input: ('!A',)

Expected Output: {'variables': ['A'], 'rows': [[False, True], [True, False]]}

Explanation: Unary NOT.

Hints

  1. Choose a representation that makes the core operation simple.
  2. Handle empty and boundary inputs before the main algorithm.

Loading coding console...