Coding - Toy Language Type System - OpenAI Interview Question | DarkInterview

Toy Language Type System

Problem Overview

You are tasked with implementing a type system for a toy programming language. This language supports:

Primitives: int, float, str
Generics: Uppercase letters with optional numbers, e.g., T, T1, T2, S
Tuples: Lists of types enclosed in brackets, which can contain primitives, generics, or nested tuples
- Examples: [int, T1, str], [int, str, [int, T1]]
Functions: Defined with parameters and a return type
- Syntax: [param1, param2, ...] -> returnType
- Example: [int, [int, T1], T2] -> [str, T2, [float, float]]

You need to implement two classes: Node and Function.

Class Specifications

Node Class

The Node class represents a type in the language, which can be either: [Source: darkinterview.com]

A primitive or generic type (single value)
A tuple (list of child nodes)

Constructor:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
def __init__(self, node_type: Union[str, List['Node']])

If node_type is a string: represents a primitive or generic type
If node_type is a list: represents a tuple containing child nodes

Key Methods:

__str__(): Returns the string representation of the node (see Part 1)

Function Class

The Function class represents a function signature with parameters and a return type. [Source: darkinterview.com]

Constructor:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
def __init__(self, parameters: List[Node], output_type: Node)

parameters: List of Node objects representing function parameter types
output_type: A Node object representing the return type

Key Methods:

__str__(): Returns the string representation of the function (see Part 1)

Part 1: String Representation

Implement the __str__() method for both Node and Function classes. [Source: darkinterview.com]

Node String Format

Primitive/Generic types: Return the type name as-is
- Example: int → "int", T1 → "T1"
Tuples: Return comma-separated types enclosed in brackets
- Example: [int, float] → "[int,float]"
- Nested example: [int, [str, T1]] → "[int,[str,T1]]"

Function String Format

Format: (param1,param2,...) -> returnType
Example: Function with parameters [int, T1] and return type [T1, str]
- Output: "(int,T1) -> [T1,str]"

Note: You should write your own test cases for Part 1 to verify correctness.

Part 2: Type Inference with Generic Substitution

Implement a function get_return_type(parameters: List[Node], function: Function) -> Node that:

Takes actual parameter types and a function definition
Resolves generic types (T1, T2, etc.) by matching actual parameters with function parameters
Returns the actual return type with all generics substituted
Raises errors for type mismatches or conflicts

Input Guarantees

All actual parameter types are concrete (no generics)
No need for deep DFS traversal in parameters

Error Conditions

Your implementation must detect and raise errors for: [Source: darkinterview.com]

Argument count mismatch: Number of parameters doesn't match function definition
Type mismatch: Concrete types don't match when they should
- Example: Expecting int but got str
Generic type conflict: Same generic type is bound to different concrete types
- Example: T1 is bound to both int and str

Examples

Example 1: Valid Type Inference

Function Definition:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
# [T1, T2, int, T1] -> [T1, T2]
func = Function(
    [Node('T1'), Node('T2'), Node('int'), Node('T1')],
    Node([Node('T1'), Node('T2')])
)

Actual Parameters:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
parameters = [Node('int'), Node('str'), Node('int'), Node('int')]

Expected Return: [Source: darkinterview.com]

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
Node([Node('int'), Node('str')])  # "[int,str]"

Explanation:

T1 is bound to int (from 1st and 4th parameters)
T2 is bound to str (from 2nd parameter)
Return type [T1, T2] becomes [int, str]

Example 2: Concrete Type Mismatch Error

Function Definition: Same as Example 1

Actual Parameters: [Source: darkinterview.com]

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
parameters = [Node('int'), Node('str'), Node('float'), Node('int')]

Expected: Raise exception

Explanation:

3rd parameter expects concrete type int but receives float
This is a type mismatch error

Example 3: Generic Type Conflict Error

Function Definition: Same as Example 1 [Source: darkinterview.com]

Actual Parameters:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
parameters = [Node('int'), Node('str'), Node('int'), Node('str')]

Expected: Raise exception

Explanation: [Source: darkinterview.com]

1st parameter binds T1 to int
4th parameter tries to bind T1 to str
This is a generic type conflict - same generic bound to different types

Example 4: Nested Tuples

Function Definition:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
# [[ T1, float ], T1] -> [T1, [T1, float]]
func = Function(
    [
        Node([Node('T1'), Node('float')]),
        Node('T1')
    ],
    Node([Node('T1'), Node([Node('T1'), Node('float')])])
)

Actual Parameters:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
parameters = [
    Node([Node('str'), Node('float')]),
    Node('str')
]

Expected Return: [Source: darkinterview.com]

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
Node([Node('str'), Node([Node('str'), Node('float')])])
# "[str,[str,float]]"

Explanation:

T1 is bound to str from both parameters
Return type substitutes T1 with str

Example 5: Complex Function with Multiple Generics

Function Definition:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
# [[T1, float], T2, S] -> [S, T1]
func = Function(
    [
        Node([Node('T1'), Node('float')]),
        Node('T2'),
        Node('S')
    ],
    Node([Node('S'), Node('T1')])
)

Actual Parameters: [Source: darkinterview.com]

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
parameters = [
    Node([Node('str'), Node('float')]),
    Node([Node('int'), Node('str')]),
    Node('int')
]

Expected Return:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
Node([Node('int'), Node('str')])
# "[int,str]"

Explanation:

T1 is bound to str
T2 is bound to [int, str] (tuple)
S is bound to int
Return type [S, T1] becomes [int, str]

Implementation Hints

Suggested Helper Methods

You may find it useful to implement: [Source: darkinterview.com]

is_generic_type(node: Node) -> bool: Check if a node contains any generic types
clone(node: Node) -> Node: Deep copy a node
bind_generics(func_param: Node, actual_param: Node, binding_map: dict):
- Recursively match function parameters with actual parameters
- Populate the binding map with generic type mappings
- Raise errors on conflicts
substitute_generics(node: Node, binding_map: dict) -> Node:
- Replace all generic types in a node with their concrete bindings
- Recursively handle nested tuples

Algorithm Outline

// Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
1. Validate parameter count matches
2. Initialize empty binding_map = {}
3. For each (func_param, actual_param) pair:
   a. If func_param is a generic type:
      - Check if already bound in binding_map
      - If bound, verify it matches actual_param
      - If not bound, add to binding_map
   b. If func_param is concrete:
      - Verify it exactly matches actual_param
   c. If func_param is a tuple:
      - Recursively process each child
4. Substitute all generics in return type using binding_map
5. Return the substituted return type

Test Cases for Part 2

The interviewer will provide comprehensive test cases for Part 2. Your implementation should pass all provided tests, which will cover:

Basic generic substitution
Nested tuple handling
Type mismatch detection
Generic conflict detection
Edge cases with multiple generics

Notes

The parameter types in get_return_type are always concrete (no generic types like T1, T2)
Focus on clear error messages when raising exceptions
Consider edge cases like empty tuples, single-element tuples, and deeply nested structures

Sample Solution

Below is a reference implementation demonstrating one approach to solving this problem:

# Source: https://darkinterview.com/collections/x7k9m2p4/questions/f6791008-88f4-49af-93c1-4fce89292822
from typing import Union, List


class Node:
    def __init__(self, node_type: Union[str, List['Node']]):
        self.type_list = ['str', 'float', 'int']

        if isinstance(node_type, str):
            self.base = node_type
            self.children = []
        else:
            self.base = None
            self.children = node_type

    def get_content(self) -> Union[str, List['Node']]:
        if self.base:
            return self.base
        return self.children

    def is_base_generic_type(self):
        return self.base and self.base not in self.type_list

    def is_generic_type(self):
        if self.is_base_generic_type():
             
         ([child.is_generic_type()  child  .children])

     ():
         .base:
             Node(.base)
         Node([child.clone()  child  .children])

     () -> :
         .base:
             .base

        node_types = []
         child  .children:
            node_types.append((child))

         

     () -> :
          (other, Node):
             
         (other) == ()


 :
     ():
        .parameters = param
        .output_type = output

     () -> :
        param_str = .join([(param)  param  .parameters])
        output_str = (.output_type)
         


 ():
    
     func_param.is_generic_type()  func_param.base:
         func_param.base  binding_map  binding_map[func_param.base] != param:
             Exception()
         func_param.base   binding_map:
            binding_map[func_param.base] = param
    
     func_param == param:
        
    
      func_param.base   param.base:
        
         (func_param.children) != (param.children):
             Exception()
         sub_func_node, sub_param_node  (func_param.children, param.children):
            binding(sub_func_node, sub_param_node, binding_map)
    :
         Exception()


 () -> Node:
      node.is_generic_type():
         node.clone()

      node.children:
        cloned = binding_map[node.base].clone()
         Node(cloned.get_content())

     Node([replace_invocation_arguments(child, binding_map)  child  node.children])


 () -> Node:
     (parameters) != (function.parameters):
         Exception()

    binding_map = {}

     func_node, param_node  (function.parameters, parameters):
        binding(func_node, param_node, binding_map)

      function.output_type.is_generic_type():
         function.output_type

     replace_invocation_arguments(function.output_type, binding_map)



 __name__ == :
    
    node1 = Node()
    node2 = Node()
    node3 = Node()
    node4 = Node([node1, node2])
    node5 = Node([node4, node3])

    (node5)  

    func = Function([node5, Node()], Node([Node(), Node()]))

    (func)  

    
    node11 = Node()
    node22 = Node()
    node33 = Node()
    node44 = Node([node11, node22])
    node55 = Node([node44, node33])

    node = get_return_type([node55, Node([Node(), Node()])], func)
    (node)

Key Implementation Details:

is_base_generic_type(): Checks if a base type is generic by verifying it's not in the primitive type list
is_generic_type(): Recursively checks if a node or any of its children contain generics
binding(): Recursively matches function parameters with actual parameters, populating the binding map and validating types
replace_invocation_arguments(): Substitutes all generic types in the return type with their concrete bindings
Tuple length validation: The solution includes a check to ensure tuple lengths match during binding (this is an important edge case)

Legal Disclaimer & Copyright Notice

Toy Language Type System

Problem Overview

Class Specifications

Node Class

Function Class

Part 1: String Representation

Node String Format

Function String Format

Part 2: Type Inference with Generic Substitution

Input Guarantees

Error Conditions

Examples

Example 1: Valid Type Inference

Example 2: Concrete Type Mismatch Error

Example 3: Generic Type Conflict Error

Example 4: Nested Tuples

Example 5: Complex Function with Multiple Generics

Implementation Hints

Suggested Helper Methods

Algorithm Outline

Test Cases for Part 2

Notes

Sample Solution

Key Implementation Details: