Implement toy-language types and generic substitution
Company: OpenAI
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem: Toy Language Type System (Printing + Generic Resolution)
You are implementing a small type system for a custom “Toy Language”. Types can be:
- **Primitive types:** lowercase strings like `int`, `float`, `str`, `bool`
- **Generic type variables:** uppercase letter(s) followed by digits, e.g., `T1`, `T2`
- **Tuples:** bracketed, comma-separated types, which may be nested, e.g. `[int,[T1,str]]`
- **Function signatures:** a list of parameter types and a single return type, written as `(param1,param2,...) -> returnType`
### Data structures
Implement the following classes.
#### `Node`
Represents a type node.
- Construction:
- If `node_type` is a **string**, the node is a **leaf** representing either a primitive type or a generic.
- If `node_type` is a **list of Node**, the node is a **tuple** whose children are those nodes.
```python
class Node:
def __init__(self, node_type):
...
def to_str(self) -> str:
...
```
**`Node.to_str()` formatting rules**
- Leaf: return the exact string name, e.g. `"int"`, `"T1"`.
- Tuple: return bracketed, comma-separated children with **no spaces**, e.g. `[int,T1]`, `[int,[T1,str]]`.
#### `Function`
Represents a function signature.
```python
class Function:
def __init__(self, parameters: list[Node], output_type: Node):
...
def to_str(self) -> str:
...
```
**`Function.to_str()` formatting rules**
- Format: `(param1,param2,...) -> returnType` using each node’s `to_str()`.
- Example: `(int,T1) -> [T1,str]`
---
## Part 2: Infer concrete return type
Implement:
```python
def get_return_type(parameters: list[Node], function: Function) -> Node:
...
```
Given:
- `function.parameters`: the expected parameter type patterns (may include generics and nested tuples)
- `parameters`: the actual argument types supplied at a call site
Return a **new `Node`** representing the **concrete** return type after substituting generics.
### Requirements
1. **Argument count check**
- Raise an error if `len(parameters) != len(function.parameters)`.
2. **Build a substitution table (generic resolution)**
- Compare each expected parameter pattern against the corresponding actual argument type.
- If the expected node is a **generic** (e.g., `T1`), bind it to the actual type node.
- If the expected node is a **primitive**, it must match the actual primitive exactly.
- If the expected node is a **tuple**, the actual must also be a tuple of the same arity, and you must recurse.
3. **Conflict detection**
- If a generic like `T1` is bound more than once in the same call, all bindings must be structurally identical.
- Otherwise raise an error (e.g., `T1` cannot be both `int` and `str`).
4. **Return type substitution**
- After building the mapping, recursively replace all generics appearing in `function.output_type` with their bound concrete types.
- If a generic appears in the output type but was never bound by the inputs, raise an error (or clearly document and implement a consistent behavior).
### Examples
1. **Basic substitution**
- Function: `[T1, T2, int, T1] -> [T1, T2]`
- Arguments: `[int, str, int, int]`
- Mapping: `T1 = int`, `T2 = str`
- Result: `[int, str]`
2. **Nested tuples & complex generics**
- Function: `[[T1, float], T2, T3] -> [T3, T1]`
- Arguments: `[[str, float], [int, str], int]`
- Mapping: `T1 = str`, `T2 = [int, str]`, `T3 = int`
- Result: `[int, str]`
3. **Conflict error**
- Function: `[T1, T1] -> T1`
- Arguments: `[int, str]`
- Error: `T1` cannot be both `int` and `str`
Implement the above behavior with clear recursive logic and appropriate error handling.
Quick Answer: This question evaluates understanding of type systems, AST-style type representations, and generic type variable resolution by requiring implementation of Node and Function models and substitution of generics to infer concrete return types.
Part 1: Format Toy-Language Types and Function Signatures
You are given serialized Toy-Language type data.
A type expression is represented as:
- a string leaf such as 'int', 'float', or 'T1'
- a Python list of type expressions, representing a tuple type
Examples:
- 'int' represents a leaf type
- ['int', 'T1'] represents [int,T1]
- ['int', ['T1', 'str']] represents [int,[T1,str]]
A function signature is represented by:
- a list of parameter type expressions
- one output type expression
Write a function solution(kind, data) that returns the canonical printed form.
Rules:
- If kind == 'node', data is one type expression and you must format it.
- If kind == 'function', data is a pair (parameters, output_type) and you must format the full signature as '(param1,param2,...) -> returnType'.
- Leaf nodes print exactly as their stored string.
- Tuple nodes print as bracketed, comma-separated children with no spaces.
- Function signatures have no spaces inside the parameter list; the only spaces are around '->'.
- A function may have zero parameters, which should print as '() -> returnType'.
Constraints
- kind is either 'node' or 'function'
- Each leaf is a non-empty string
- Tuple types are represented only by Python lists
- 0 <= number of function parameters <= 10^3
- Total number of nodes across the input structure is at most 10^4
- Maximum nesting depth is at most 200
Examples
Input: ('node', 'int')
Expected Output: 'int'
Explanation: A leaf node prints as its exact stored name.
Input: ('node', ['int', ['T1', 'str']])
Expected Output: '[int,[T1,str]]'
Explanation: Nested tuple types are formatted recursively with no spaces.
Input: ('function', (['int', 'T1'], ['T1', 'str']))
Expected Output: '(int,T1) -> [T1,str]'
Explanation: Each parameter and the return type are formatted using the same node rules.
Input: ('function', ([], 'bool'))
Expected Output: '() -> bool'
Explanation: Edge case: a function may have zero parameters.
Input: ('node', ['T9'])
Expected Output: '[T9]'
Explanation: Edge case: a single-element tuple still uses brackets.
Solution
def solution(kind, data):
class Node:
def __init__(self, node_type):
if isinstance(node_type, str):
self.name = node_type
self.children = None
elif isinstance(node_type, list):
self.name = None
self.children = [Node(child) for child in node_type]
else:
raise TypeError('node_type must be a string or a list')
def to_str(self):
if self.children is None:
return self.name
return '[' + ','.join(child.to_str() for child in self.children) + ']'
class Function:
def __init__(self, parameters, output_type):
self.parameters = [Node(param) for param in parameters]
self.output_type = Node(output_type)
def to_str(self):
param_text = ','.join(param.to_str() for param in self.parameters)
return '(' + param_text + ') -> ' + self.output_type.to_str()
if kind == 'node':
return Node(data).to_str()
if kind == 'function':
parameters, output_type = data
return Function(parameters, output_type).to_str()
raise ValueError('invalid kind')Time complexity: O(N), where N is the total number of nodes in the given type expression or function signature.. Space complexity: O(N), due to building the recursive Node structure..
Hints
- Use one recursive helper to format a type expression: strings return themselves, lists format each child and join with commas.
- For a function signature, reuse the same type-formatting helper for every parameter and for the return type.
Part 2: Resolve Generic Return Types in Toy-Language
You are given a Toy-Language function signature with generic type variables and a list of actual argument types.
A type expression is serialized as:
- a string leaf, such as 'int', 'float', 'str', 'bool', or 'T1'
- a Python list of type expressions, representing a tuple type
In this problem:
- lowercase strings are primitive types
- strings starting with an uppercase letter are generic type variables
Write solution(actual_parameters, expected_parameters, output_type) to infer the concrete return type.
Resolution rules:
1. If the number of actual parameters does not match the number of expected parameters, the call is invalid.
2. Compare each expected parameter pattern with the corresponding actual parameter:
- expected generic: bind it to the actual type
- expected primitive: it must match the actual primitive exactly
- expected tuple: the actual must also be a tuple with the same length, and matching continues recursively
3. If the same generic is seen more than once, every binding must be structurally identical.
4. After building the substitutions, recursively replace generics inside output_type.
5. If any error occurs, including an unbound generic in the output type, return 'ERROR'.
Return the inferred return type as a canonical string such as 'int' or '[int,str]'.
Constraints
- 0 <= len(actual_parameters), len(expected_parameters) <= 10^3
- Tuple types are represented only by Python lists
- Total number of nodes across all input type expressions is at most 10^4
- Maximum nesting depth is at most 200
- Primitive type names are lowercase strings
- Generic names start with an uppercase letter
Examples
Input: (['int', 'str', 'int', 'int'], ['T1', 'T2', 'int', 'T1'], ['T1', 'T2'])
Expected Output: '[int,str]'
Explanation: T1 resolves to int and T2 resolves to str.
Input: ([['str', 'float'], ['int', 'str'], 'int'], [['T1', 'float'], 'T2', 'T3'], ['T3', 'T1'])
Expected Output: '[int,str]'
Explanation: Nested tuples are matched recursively before substituting the output.
Input: (['int', 'str'], ['T1', 'T1'], 'T1')
Expected Output: 'ERROR'
Explanation: T1 cannot be bound to both int and str in the same call.
Input: ([], [], 'bool')
Expected Output: 'bool'
Explanation: Edge case: a zero-parameter function with a concrete return type is valid.
Input: (['int'], ['int'], 'T1')
Expected Output: 'ERROR'
Explanation: The output generic T1 was never bound by the inputs.
Solution
def solution(actual_parameters, expected_parameters, output_type):
def is_generic(expr):
return isinstance(expr, str) and expr != '' and expr[0].isupper()
def clone(expr):
if isinstance(expr, list):
return [clone(part) for part in expr]
return expr
def same(a, b):
if isinstance(a, str) and isinstance(b, str):
return a == b
if isinstance(a, list) and isinstance(b, list) and len(a) == len(b):
return all(same(x, y) for x, y in zip(a, b))
return False
def format_type(expr):
if isinstance(expr, str):
return expr
return '[' + ','.join(format_type(part) for part in expr) + ']'
substitutions = {}
def unify(expected, actual):
if isinstance(expected, str):
if is_generic(expected):
if expected in substitutions:
return same(substitutions[expected], actual)
substitutions[expected] = clone(actual)
return True
return isinstance(actual, str) and expected == actual
if isinstance(expected, list):
if not isinstance(actual, list) or len(expected) != len(actual):
return False
for expected_child, actual_child in zip(expected, actual):
if not unify(expected_child, actual_child):
return False
return True
return False
def substitute(expr):
if isinstance(expr, str):
if is_generic(expr):
if expr not in substitutions:
raise ValueError('unbound generic')
return clone(substitutions[expr])
return expr
if isinstance(expr, list):
return [substitute(part) for part in expr]
raise ValueError('invalid type expression')
if len(actual_parameters) != len(expected_parameters):
return 'ERROR'
for expected, actual in zip(expected_parameters, actual_parameters):
if not unify(expected, actual):
return 'ERROR'
try:
concrete_output = substitute(output_type)
except ValueError:
return 'ERROR'
return format_type(concrete_output)Time complexity: O(N), where N is the total number of nodes across all parameter types and the output type.. Space complexity: O(N), for the substitution table, recursion stack, and constructed substituted output..
Hints
- Walk expected and actual types together recursively, building a dictionary from generic name to concrete subtree.
- After matching the inputs, run a second recursive pass over the output type to substitute every generic.