Design and implement a tiny language runtime

Quick Overview

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.

Design and implement a tiny language runtime

Company: Jane Street

Role: Machine Learning Engineer

Category: System Design

Difficulty: hard

Interview Round: Technical Screen

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?

Overview: 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.

Community answers

Answer by Skywalker

Can't seem to find the inbuilt code editor.
|Home/Jane Street/System Design
Jane Street logo
Jane Street
Aug 1, 2025
hardMachine Learning EngineerTechnical ScreenSystem Design
67
0

Design and implement a tiny language runtime

Minimal Imperative Language — Design and Implementation Task

Context

You are asked to design and implement a minimal imperative language and its tooling. The language supports integers, variables, arithmetic, comparisons, conditionals, loops, and printing. You must decide and document a concrete grammar, implement a tokenizer and recursive-descent parser that produce an AST, perform basic static checks, and execute programs.

Language Specification (to implement)

  • Tokens: identifiers, integers, operators (+, -, *, /), comparisons (<, <=, >, >=, ==, !=), assignment (=), punctuation (;, (, ), {, }).
  • Statements:
    1. Variable declaration: let x = expr;
    2. Assignment: x = expr;
    3. Conditional: if (expr) { ... } else { ... }
    4. Loop: while (expr) { ... }
    5. Print: print(expr);
  • Expressions: integer arithmetic and parentheses.

Deliverables

  1. Implement a tokenizer and a recursive-descent parser that builds an AST for a grammar you define.
  2. Implement static checks for undefined variables and integer-only type consistency.
  3. Implement either:
    • an AST interpreter, or
    • a bytecode compiler plus VM. Choose one, implement it, and justify the choice.

Design Extensions and Discussion

  • 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?

Clarifying Questions to Ask Guidance

  • Clarify users, core use cases, read/write patterns, scale, latency, availability, and data retention.
  • State explicit assumptions before making sizing or architecture decisions.
  • Prioritize the functional path first, then address reliability, security, observability, and rollout.

What a Strong Answer Covers Guidance

  • A scoped requirements summary with concrete non-goals and success metrics.
  • API, data model, architecture, consistency, capacity, and operations.
  • Reasoned trade-offs among simple and scalable designs, including bottlenecks and failure modes.
  • A validation, monitoring, migration, and launch plan appropriate for the risk level.

Follow-up Questions Guidance

  • What breaks first at 10x traffic or data volume?
  • How would you degrade gracefully during dependency failures?
  • What metrics and alerts would prove the design is healthy after launch?

Browse More Questions

More System Design•More Jane Street•More Machine Learning Engineer•Jane Street Machine Learning Engineer•Jane Street System Design•Machine Learning Engineer System Design