Toy Language Type System

MediumOpenAI Interview

RecursionTree TraversalType Inference

You're building a type system for a custom Toy Language. The system must handle primitive types, generics, nested tuples, and function signatures. You will implement the core data structures and a Type Inference engine that substitutes generics with concrete types.

Type Definitions

Primitives: Lowercase strings like int, float, str, bool

Generics: Uppercase letters followed by numbers, e.g. T1, T2

Tuples: Comma-separated types inside brackets, which can be nested. Example: [int, [T1, str]]

Functions: Defined by a list of parameter types and a single return type. Syntax: [param1, param2] -> returnType

Part 1 — Implement `to_str` in Node and Function

Node represents a type node. It can be a leaf (primitive/generic) or a tuple (list of child nodes).

If node_type is a string, it is a primitive or generic.

If node_type is a list, it is a tuple containing other Node objects.

to_str() for primitives/generics returns the string name (e.g. "int").

to_str() for tuples returns bracketed, comma-separated types (e.g. "[int,T1]").

Function represents a function signature with a list of parameter Nodes and a single return-type Node.

to_str() format: (param1,param2,...) -> returnType

Example: (int,T1) -> [T1,str]

Part 2 — Implement `get_return_type`

Implement a function get_return_type(parameters, function) that determines the concrete return type of a function based on provided arguments.

Requirements:

Generic Resolution: Build a substitution table by comparing the function's expected parameter types to the actual argument types provided.

Substitution: Recursively replace all generics in the function's output_type with the concrete types found during resolution.

Error Handling:

- Argument Count Mismatch: Raise an error if the number of arguments doesn't match the number of parameters.

- Type Mismatch: Raise an error if a concrete type is expected but a different concrete type is provided (e.g. expected int, got str).

- Generic Conflict: Raise an error if the same generic (e.g. T1) is bound to two different concrete types in the same call.

Class Skeleton

1class Node:
2    def __init__(self, node_type):
3        """
4        node_type: str for a primitive/generic,
5                   list[Node] for a tuple.
6        """
7        pass
8
9    def to_str(self) -> str:
10        """
11        Primitives/Generics: return the name, e.g. "int".
12        Tuples: return "[child1,child2,...]".
13        """
14        pass
15
16
17class Function:
18    def __init__(self, parameters: list[Node], output_type: Node):
19        """
20        parameters: list of Node objects (the param types).
21        output_type: a single Node (the return type).
22        """
23        pass
24
25    def to_str(self) -> str:
26        """
27        Format: (param1,param2,...) -> returnType
28        """
29        pass
30
31
32def get_return_type(parameters: list[Node], function: Function) -> Node:
33    """
34    Given concrete argument types and a Function,
35    resolve generics and return the concrete return type.
36    Raises on count mismatch, type mismatch, or generic conflict.
37    """
38    pass

Examples

Example 1 — Basic Substitution

1# Function: [T1, T2, int, T1] -> [T1, T2]
2params = [Node("T1"), Node("T2"), Node("int"), Node("T1")]
3ret    = Node([Node("T1"), Node("T2")])
4func   = Function(params, ret)
5
6func.to_str()  # "(T1,T2,int,T1) -> [T1,T2]"
7
8# Arguments: [int, str, int, int]
9args = [Node("int"), Node("str"), Node("int"), Node("int")]
10
11result = get_return_type(args, func)
12result.to_str()  # "[int,str]"
13# T1 -> int, T2 -> str

Example 2 — Nested Tuples & Complex Generics

1# Function: [[T1, float], T2, T3] -> [T3, T1]
2params = [
3    Node([Node("T1"), Node("float")]),
4    Node("T2"),
5    Node("T3"),
6]
7ret  = Node([Node("T3"), Node("T1")])
8func = Function(params, ret)
9
10# Arguments: [[str, float], [int, str], int]
11args = [
12    Node([Node("str"), Node("float")]),
13    Node([Node("int"), Node("str")]),
14    Node("int"),
15]
16
17result = get_return_type(args, func)
18result.to_str()  # "[int,str]"
19# T1 -> str, T2 -> [int,str], T3 -> int

Example 3 — Generic Conflict Error

1# Function: [T1, T1] -> T1
2params = [Node("T1"), Node("T1")]
3ret    = Node("T1")
4func   = Function(params, ret)
5
6# Arguments: [int, str]
7args = [Node("int"), Node("str")]
8
9get_return_type(args, func)
10# Error: T1 cannot be both int and str

Mock Interview Prompt

Copy this prompt into ChatGPT to practice with an AI interviewer.

Act as a senior SWE interviewing me for an entry-level to mid-level engineer position.

I have not done interviews in a long time. Do this step by step:
1. Present the problem below, then ask if I have any clarifying questions before I start. If I say no or try to skip ahead, gently nudge me — say something like "Are you sure? It might be worth thinking about how types are represented and what edge cases generics could introduce before diving in." Do NOT give specific example questions — just hint at the area.
2. Answer my clarifying questions if I have any, then ask me to walk you through my approach before coding.
3. Once I start coding, give hints only if I appear stuck. Never directly give me the answer — always end with a question that guides me.
4. When I make a suboptimal choice or get something wrong, briefly explain why the alternative is better so I learn the reasoning, then ask me how I'd adjust.
5. Give positive reinforcement when I get something right or show good instincts.

Here is the problem:

You're building a type system for a custom Toy Language. The system must handle primitive types, generics, nested tuples, and function signatures.

Type Definitions:
- Primitives: Lowercase strings like int, float, str, bool
- Generics: Uppercase letters followed by numbers, e.g. T1, T2
- Tuples: Comma-separated types inside brackets, which can be nested. Example: [int, [T1, str]]
- Functions: Defined by a list of parameter types and a single return type. Syntax: [param1, param2] -> returnType

Part 1 — Implement to_str in Node and Function.

Node represents a type node. It can be a leaf (primitive/generic) or a tuple (list of child nodes).
- If node_type is a string, it is a primitive or generic.
- If node_type is a list, it is a tuple containing other Node objects.
- to_str() for primitives/generics returns the string name (e.g. "int").
- to_str() for tuples returns bracketed, comma-separated types (e.g. "[int,T1]").

Function represents a function signature with parameters (list of Nodes) and output_type (a single Node).
- to_str() format: (param1,param2,...) -> returnType
- Example: (int,T1) -> [T1,str]

Once the candidate finishes Part 1, move on to Part 2:

Part 2 — Implement get_return_type(parameters, function) that determines the concrete return type of a function based on provided arguments.

Requirements:
- Generic Resolution: Build a substitution table by comparing the function's expected parameters to the actual arguments provided.
- Substitution: Recursively replace all generics in the function's output_type with the concrete types found during resolution.
- Error Handling:
  - Argument Count Mismatch: Raise an error if the number of arguments doesn't match.
  - Type Mismatch: Raise an error if a concrete type is expected but a different type is provided.
  - Generic Conflict: Raise an error if the same generic is bound to two different concrete types.

Test Examples:

Example 1: Function [T1, T2, int, T1] -> [T1, T2], Arguments [int, str, int, int]. T1 maps to int, T2 maps to str. Result: [int, str].

Example 2: Function [[T1, float], T2, T3] -> [T3, T1], Arguments [[str, float], [int, str], int]. T1 extracted from the nested tuple as str, T2 maps to [int, str], T3 maps to int. Result: [int, str].

Example 3: Function [T1, T1] -> T1, Arguments [int, str]. Error: T1 cannot be both int and str.

solution.py

class Node:
    def __init__(self, node_type):
        """
        node_type: str for a primitive/generic,
                   list[Node] for a tuple.
        """
        pass

    def to_str(self) -> str:
        """
        Primitives/Generics: return the name, e.g. "int".
        Tuples: return "[child1,child2,...]".
        """
        pass


class Function:
    def __init__(self, parameters: list[Node], output_type: Node):
        """
        parameters: list of Node objects (the param types).
        output_type: a single Node (the return type).
        """
        pass

    def to_str(self) -> str:
        """
        Format: (param1,param2,...) -> returnType
        """
        pass


def get_return_type(parameters: list[Node], function: Function) -> Node:
    """
    Given concrete argument types and a Function,
    resolve generics and return the concrete return type.
    Raises on count mismatch, type mismatch, or generic conflict.
    """
    pass

class Node:
    def __init__(self, node_type):
        """
        node_type: str for a primitive/generic,
                   list[Node] for a tuple.
        """
        pass

    def to_str(self) -> str:
        """
        Primitives/Generics: return the name, e.g. "int".
        Tuples: return "[child1,child2,...]".
        """
        pass


class Function:
    def __init__(self, parameters: list[Node], output_type: Node):
        """
        parameters: list of Node objects (the param types).
        output_type: a single Node (the return type).
        """
        pass

    def to_str(self) -> str:
        """
        Format: (param1,param2,...) -> returnType
        """
        pass


def get_return_type(parameters: list[Node], function: Function) -> Node:
    """
    Given concrete argument types and a Function,
    resolve generics and return the concrete return type.
    Raises on count mismatch, type mismatch, or generic conflict.
    """
    pass