How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at OpenAI.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at OpenAI during technical interviews.

Implement type AST and infer generics | OpenAI Coding Question

Implement type AST and infer generics

Company: OpenAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Toy language type system: AST + generic inference You are implementing a tiny type system for a toy language with: - **Primitive types**: `char`, `int`, `float` - **Generic type variables**: identifiers like `T1`, `T2`, … (stand for an unknown type) - **Tuple types**: an ordered tuple of 2 or more types, where each element can itself be a primitive, a generic, or another tuple. Assume the textual syntax for a type is: - Primitive: `char` | `int` | `float` - Generic: `T` followed by one or more digits (e.g., `T1`, `T20`) - Tuple: `(<type>,<type>,...,<type>)` with no restriction on nesting (e.g., `(int,(T1,char),float)`) ### Part A — `Node` type representation Implement a `Node` class/struct that can represent any type in this grammar. ### Part B — `toString()` Implement `toString()` for `Node` that serializes the type back into the exact canonical format described above. ### Part C — `infer_return(pattern, concrete)` Implement a function that infers what each generic (`T1`, `T2`, …) must be, given: - `pattern`: a type expression that may contain generics - `concrete`: a fully concrete type expression containing **no generics** (only primitives and tuples) The function must return a mapping like `{T1 -> int, T2 -> (char,float)}` such that substituting generics in `pattern` produces exactly `concrete`. #### Rules - If `pattern` is a primitive, it must equal `concrete`. - If `pattern` is a generic `Tk`, bind it to `concrete` **unless** it was already bound to a different type (conflict). - If `pattern` is a tuple, `concrete` must also be a tuple of the same length, and inference recurses element-wise. #### Error cases (must throw/return error) - Tuple vs non-tuple mismatch - Tuple length mismatch - Primitive mismatch - Conflicting generic bindings (e.g., `pattern=(T1,T1)` with `concrete=(int,float)`) ### Examples - `pattern=(T1,int)`, `concrete=(char,int)` → `{T1 -> char}` - `pattern=(T1,(T2,char))`, `concrete=(float,(int,char))` → `{T1 -> float, T2 -> int}` - `pattern=(T1,T1)`, `concrete=(int,float)` → error (conflict) State any assumptions about parsing/whitespace and how you represent/compare types.

Quick Answer: This question evaluates a candidate's ability to design an abstract syntax tree representation and implement generic type inference for a small language, exercising skills in type systems, structural recursion, and detecting conflicting bindings.

Part 1: Build a Type AST

Given a toy-language type expression, build its AST using a serializable Node representation. Use these node formats: primitive -> ("primitive", name), generic -> ("generic", name), tuple -> ("tuple", [child1, child2, ...]). Ignore optional whitespace in the input. Assume the input string is syntactically valid and every tuple has at least 2 elements.

Constraints

1 <= len(type_expr) <= 10^4
Valid primitive names are char, int, and float
Generic names are T followed by one or more digits
Maximum nesting depth <= 10^3

Examples

Input: "int"

Expected Output: ("primitive", "int")

Explanation: A primitive becomes a primitive node.

Input: "T20"

Expected Output: ("generic", "T20")

Explanation: A generic type variable becomes a generic node.

Input: "(int,T1,float)"

Expected Output: ("tuple", [("primitive", "int"), ("generic", "T1"), ("primitive", "float")])

Explanation: A flat tuple stores its children in order.

Input: "(int,(T1,char),float)"

Expected Output: ("tuple", [("primitive", "int"), ("tuple", [("generic", "T1"), ("primitive", "char")]), ("primitive", "float")])

Explanation: Nested tuples become nested tuple nodes.

Input: " ( int , ( T2 , char ) ) "

Expected Output: ("tuple", [("primitive", "int"), ("tuple", [("generic", "T2"), ("primitive", "char")])])

Explanation: Whitespace is ignored.

Hints

A recursive-descent parser fits this grammar well: parse one type, and if you see '(', recursively parse comma-separated child types until ')'.
Tokenize lazily: for non-tuple types, read one contiguous alphanumeric token and then decide whether it is a primitive or a generic.

Part 2: Serialize a Type AST to Canonical String

You are given a type AST in the same representation as Part 1: primitive -> ("primitive", name), generic -> ("generic", name), tuple -> ("tuple", [child1, child2, ...]). Serialize it back to the exact canonical type syntax with no whitespace. Tuples must be written as (type1,type2,...) and may be nested.

Constraints

The total number of AST nodes is at most 10^4
Tuple nodes contain at least 2 children
The AST is valid and uses only the node kinds primitive, generic, and tuple

Examples

Input: ("primitive", "char")

Expected Output: "char"

Explanation: A primitive leaf serializes to its name.

Input: ("generic", "T3")

Expected Output: "T3"

Explanation: A generic leaf also serializes to its name.

Input: ("tuple", [("primitive", "int"), ("generic", "T1")])

Expected Output: "(int,T1)"

Explanation: Children are joined with commas and wrapped in parentheses.

Input: ("tuple", [("primitive", "int"), ("tuple", [("generic", "T1"), ("primitive", "char")]), ("primitive", "float")])

Expected Output: "(int,(T1,char),float)"

Explanation: Nested tuples serialize recursively.

Hints

This is a tree traversal problem: serialize each child first, then combine them for tuple nodes.
Primitive and generic nodes are both leaves, so their string form is just their stored name.

Part 3: Infer Generic Bindings from a Pattern Type

Given two type expressions, infer how each generic in the pattern must be bound so that substituting those bindings into the pattern produces the concrete type exactly. The pattern may contain primitives, generics, and tuples. The concrete type must contain only primitives and tuples. Return a dictionary mapping each generic name to its concrete type in canonical string form, or return "ERROR" if inference fails. Ignore optional whitespace while parsing, and compare types structurally.

Constraints

1 <= len(pattern), len(concrete) <= 10^4
Valid primitive names are char, int, and float
Generics appear only in pattern; if concrete contains a generic, return "ERROR"
Maximum nesting depth <= 10^3

Examples

Input: ("(T1,int)", "(char,int)")

Expected Output: {"T1": "char"}

Explanation: T1 must be char for the tuple to match.

Input: ("(T1,(T2,char))", "(float,(int,char))")

Expected Output: {"T1": "float", "T2": "int"}

Explanation: Bindings are inferred recursively inside nested tuples.

Input: ("(int,float)", "(int,float)")

Expected Output: {}

Explanation: No generics appear, so the mapping is empty.

Input: ("(T1,T1)", "(int,float)")

Expected Output: "ERROR"

Explanation: T1 cannot be both int and float.

Input: ("(int,float)", "int")

Expected Output: "ERROR"

Explanation: A tuple cannot match a non-tuple.

Hints

Parse both strings into trees first. Working with structure is much easier than comparing raw text.
When you see a generic in the pattern, either bind it for the first time or check that the new candidate matches its previous binding exactly.

Quick Overview

This question evaluates a candidate's ability to design an abstract syntax tree representation and implement generic type inference for a small language, exercising skills in type systems, structural recursion, and detecting conflicting bindings.