Infer Generic Return Types
Company: OpenAI
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Build a small type-inference engine for a toy language. Do not parse raw strings; the input is already constructed as Python objects.
Type model:
- Primitive types: `int`, `float`, `char`, `str`
- Generic type variables: `T1`, `T2`, `T3`, ...
- Tuple types: a node containing a list of child nodes
- Function signatures: a list of parameter types and one output type
Implement the following behavior:
- A `Node` class that can represent either an atomic type or a tuple type
- A `Function` class for function signatures
- String formatting, cloning, and structural equality for types
- `check_and_bind(template, concrete, bindings)`: recursively match a template type against a concrete type
- If the template is a primitive, the concrete type must match exactly
- If the template is a tuple, the concrete type must also be a tuple with the same arity, and children must match recursively
- If the template is a generic such as `T1`, bind it to the concrete type if unbound; otherwise the concrete type must equal the previous binding
- `substitute(node, bindings, require_bound=True)`: replace generic variables with their bindings
- `get_return_type(actual_args, fn)`: check arity, infer bindings from all arguments using one shared binding map, then substitute those bindings into the function's output type
Raise appropriate errors for arity mismatches, primitive mismatches, and conflicting generic bindings.
Example:
- Function `(T1, T2, int, T1) -> (T1, T2)`
- Actual arguments `[int, char, int, int]`
- Returned type should be `(int, char)`
This question tests recursive data structures, unification-style binding, substitution, and precise error handling.
Quick Answer: This question evaluates understanding of type systems, generic unification, recursive data structures, substitution mechanics, and robust error handling in a toy type-inference engine.
You are given a toy type system for a small language. Your task is to infer the concrete return type of a function call.
This is not a parsing problem: all type expressions are already given as Python literals.
A type expression is represented as:
- a string for an atomic type, such as 'int', 'float', 'char', 'str', or a generic like 'T1', 'T2'
- a list of type expressions for a tuple type
Examples:
- 'int' means the primitive type int
- 'T2' means a generic type variable
- ['int', 'T1', ['float', 'char']] means the tuple type (int, T1, (float, char))
You are given:
- actual_args: a list of concrete argument types passed to a function call
- param_types: a list of parameter type templates; these may contain generics
- return_type: the function's return type template; this may contain generics
Inference rules:
1. If a template node is a primitive, the concrete node must be the same primitive.
2. If a template node is a tuple, the concrete node must also be a tuple with the same length, and each element must match recursively.
3. If a template node is a generic like 'T1':
- if it has not been seen before, bind it to the current concrete subtree
- if it is already bound, the new concrete subtree must be structurally identical to the old binding
4. After all parameters are matched, substitute the bindings into return_type.
5. If the return type still contains an unbound generic, that is an error.
Return the inferred return type as a canonical string:
- atomic types stay as-is, like 'int'
- tuple types use parentheses and ', ' separators, like '(int, char)' or '(str, (str, float))'
If inference fails, return one of these exact strings instead:
- 'ArityError' if the number of actual arguments does not match the number of parameters
- 'MismatchError' if a primitive or tuple shape does not match, or the return type has an unbound generic
- 'ConflictError' if the same generic would need to bind to two different types