Applied·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Applied gave me a coding problem that looked like a parser exercise but turned into a full dependency resolution challenge. Single question, but it had enough layers to keep me busy for the whole session.

Questions Asked (1)

Implement an evaluator for a simple DSL where each line assigns a variable to an arithmetic expression. Variables can reference each other in any order, and you need to handle cyclic dependencies, undefined variables, and arbitrary whitespace. Return a map of all successfully evaluated variable values.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

The parsing part I was fine with, strip whitespace, split on equals, tokenize the expression.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify the DSL grammar and evaluation semantics, then propose a two-phase approach: parse each line into a dependency graph, and evaluate via topological sort with cycle detection. Discuss error handling for undefined variables and cycles, and how to return partial results.

Pro tip: Mention that you would separate parsing from evaluation to make the system testable and extensible, and that you would use memoization to avoid re-evaluating expressions.

1. Clarify requirements and assumptions

Ask about the DSL syntax (e.g., variable names, operators, parentheses), whether expressions can be multi-line, and how to handle errors (skip vs. report). Confirm the expected output format.

2. Design the parser

Tokenize each line, ignoring whitespace, and parse into an AST or a simple structure capturing the variable name and its expression. Identify all variable references within the expression.

3. Build dependency graph and detect cycles

Create a directed graph where edges represent dependencies between variables. Use DFS or Kahn's algorithm to detect cycles; any variable in a cycle cannot be evaluated.

4. Evaluate in topological order

Process variables in an order where dependencies are resolved first. For each variable, evaluate its expression using already computed values; if a dependency is undefined or in a cycle, mark the variable as failed.

5. Handle errors and return results

Collect successfully evaluated variables into a map. For undefined variables or cycles, either omit them or include error information, depending on requirements. Discuss trade-offs.

Key Points to Mention

Parsing: tokenization and handling arbitrary whitespace
Dependency graph construction and topological sorting
Cycle detection using DFS or Kahn's algorithm
Error handling for undefined variables and cycles
Memoization to avoid redundant evaluations
Returning partial results and communicating failures

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