Applied·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Applied gave me a compiler design question for a Software Engineer round, which I did not expect at all. It was a full pipeline: lexer, parser, AST, interpreter. More involved than your typical coding screen.

Questions Asked (1)

Design and implement a mini interpreter for a small expression language. It should tokenize input, parse it into an AST, and evaluate the AST to produce printed output. The language supports integer literals, variables, assignment, arithmetic with standard precedence, unary minus, and a print statement.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

I've done parser stuff before but never under interview pressure and never from scratch in one sitting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the language grammar and requirements, then outline a modular pipeline: tokenizer, parser (using recursive descent or Pratt parsing for precedence), and evaluator. Discuss design choices like AST node types, environment for variables, and error handling, and mention testing each component.

Pro tip: Mention that you would use a Pratt parser (or precedence climbing) to elegantly handle operator precedence and unary minus, and that you'd write unit tests for each stage to catch edge cases early.

1. Clarify Requirements and Grammar

Ask clarifying questions about the language features (e.g., variable scoping, integer overflow, error handling) and define a formal grammar (e.g., EBNF) to guide implementation.

2. Design the Tokenizer

Specify token types (integers, identifiers, operators, keywords) and implement a lexer that scans input and produces a token stream, handling whitespace and errors.

3. Design the Parser and AST

Choose a parsing strategy (e.g., recursive descent with precedence climbing) and define AST node classes for expressions, assignments, and print statements.

4. Implement the Evaluator

Create an evaluator that walks the AST, maintains an environment for variable bindings, and executes print statements, ensuring correct arithmetic and precedence.

5. Test and Iterate

Write unit tests for each component (tokenizer, parser, evaluator) and integration tests for full programs, covering edge cases like unary minus and operator precedence.

Key Points to Mention

Tokenization: using regular expressions or manual scanning to produce tokens with types and values.
Parsing: recursive descent or Pratt parsing to handle operator precedence and unary minus correctly.
AST design: node types for literals, variables, binary/unary operations, assignment, and print.
Evaluation: environment (symbol table) for variable storage and lookup, and handling of runtime errors.
Error handling: reporting syntax errors with line/column info and runtime errors like undefined variables.
Testing: unit tests for each stage and integration tests for end-to-end behavior.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.