Openai·Machine Learning Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Jun 2026Remote

Summary

Got a technical screen for an MLE role at OpenAI that went pretty deep into type systems and compiler theory, which I wasn't fully expecting. The problem was meaty and the follow-up discussion pushed into territory I hadn't prepped for.

Questions Asked (1)

Given the AST of a small toy language where nodes can represent literals, variables, function calls, or composite expressions, implement a recursive function that infers the type of each expression. Your solution should handle nested expressions, type propagation through function return values, and raise clear errors on type mismatches. Also discuss how you'd extend the system to support generics or union types, and analyze time complexity relative to AST size.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

This one took me a minute to even parse.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the AST structure and type system, then outline a recursive type inference algorithm that traverses the AST bottom-up, propagating types and checking for mismatches. Discuss extensions for generics and union types, and analyze the time complexity as O(n) where n is the number of AST nodes.

Pro tip: Emphasize that type inference is a constraint-solving problem; mentioning unification or Hindley-Milner can show depth, but keep the core solution simple and correct first.

1. Clarify assumptions and define types

Ask about the type system (e.g., int, float, bool, function types) and AST node structure. Define a Type representation and an environment mapping variables to types.

2. Design recursive inference function

Write a function infer(node, env) that pattern-matches on node type: literals return their type, variables look up in env, function calls infer argument types and check against function signature, and composite expressions combine operand types.

3. Handle errors and propagation

On type mismatch, raise a clear error with node location. For function calls, ensure return type propagates correctly. Use exceptions or result types for error handling.

4. Extend to generics and union types

For generics, introduce type variables and unification; for union types, allow a type to be a set of possible types and define inference rules for operations on unions.

5. Analyze complexity and discuss trade-offs

Time complexity is O(n) for a single pass, but with generics/unions it may increase due to unification. Space complexity is O(d) for recursion depth. Discuss caching or memoization for repeated subexpressions.

Key Points to Mention

Recursive traversal of AST with environment for variable types
Type propagation through function return values and argument checking
Clear error messages with source location for type mismatches
Generics via type variables and unification (e.g., Hindley-Milner)
Union types as sets of possible types and inference rules for operations
Time complexity O(n) for basic inference, potential overhead with advanced features

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