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
Constraints
- 0 <= len(actual_args), len(param_types) <= 50
- Atomic type strings are one of: 'int', 'float', 'char', 'str', or a generic of the form 'T' followed by digits
- The total number of nodes across all input type trees is at most 10^4
Examples
Input: ([['char', 'int']], [['T1', 'int']], 'T1')
Expected Output: 'char'
Explanation: The single tuple argument matches (T1, int), so T1 binds to char and the return type becomes char.
Input: ([['int', 'float']], [['T1', 'T1']], 'T1')
Expected Output: 'ConflictError'
Explanation: T1 would need to be both int and float, which is a binding conflict.
Input: ([['char', ['int', 'float']]], [['T1', ['T2', 'float']]], ['T1', 'T2'])
Expected Output: '(char, int)'
Explanation: Nested matching binds T1 = char and T2 = int, so the return tuple is (char, int).
Input: (['float'], ['int'], 'int')
Expected Output: 'MismatchError'
Explanation: A parameter template of int cannot accept a concrete float.
Input: ([['int', 'char']], [['T1', 'T2', 'T3']], 'T1')
Expected Output: 'MismatchError'
Explanation: The template expects a 3-element tuple, but the actual argument is a 2-element tuple.
Input: (['int', 'char', 'int', 'int'], ['T1', 'T2', 'int', 'T1'], ['T1', 'T2'])
Expected Output: '(int, char)'
Explanation: Shared bindings across all parameters give T1 = int and T2 = char.
Input: ([['str', 'float'], 'str'], [['T1', 'float'], 'T1'], ['T1', ['T1', 'float']])
Expected Output: '(str, (str, float))'
Explanation: From the first parameter T1 binds to str, and the second parameter confirms the same binding.
Input: (['int'], ['T1', 'T2'], 'T1')
Expected Output: 'ArityError'
Explanation: The function expects 2 arguments but only 1 actual argument is provided.
Input: ([], [], 'int')
Expected Output: 'int'
Explanation: A zero-parameter function with a concrete return type is valid and needs no inference.
Input: (['int'], ['int'], 'T1')
Expected Output: 'MismatchError'
Explanation: T1 never appears in the parameters, so the return type cannot be fully resolved.
Hints
- Use a recursive helper that walks a template type and a concrete type together.
- Store each generic's first concrete binding in a hash map; if the same generic appears again, compare the new subtree with the old one structurally.