Katkat
Back

Design and implement a tiny language runtime

Jane StreetMachine Learning Engineer · Technical Screen
HardMachine Learning EngineerTechnical ScreenSystem Design

Last updated

Design and implement a tiny language runtime evaluates requirements, scale assumptions, API/data design, architecture, trade-offs, failure modes, and rollout in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given a specification for a minimal imperative programming language. Tokens include identifiers, integers, operators (+, -, *, /), comparisons (<, <=, >, >=, ==, !=), assignment (=), and punctuation (;, (, ), {, }). Statements include variable declaration (let x = ...;), assignment, if/else, while, and print(expr);. Expressions support integer arithmetic and parentheses. Using your preferred language, implement: (

  1. a tokenizer and a recursive-descent parser that builds an AST for a grammar you define; (
  2. static checks for undefined variables and integer-only type consistency; (
  3. either an AST interpreter or a bytecode compiler plus VM—choose one and justify it. Then answer: How would you extend the design to support user-defined functions with lexical scoping and a call stack? How would you organize classes and interfaces (OOD) to make adding new statements/operators low-friction while keeping the interpreter/compiler cohesive? How will you implement syntax/semantic error reporting with line/column tracking and recovery to continue parsing? What are the time and space complexities of tokenization, parsing, and execution with respect to program length?