Openai·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

OpenAI ML engineer round, one deep question that sounds like a fun puzzle until you're actually in it. The 1-NN as a neural net thing is the kind of problem where you think you see the answer immediately and then realize you're missing half the pieces.

Questions Asked (1)

Express the 1-Nearest-Neighbor algorithm as a pure neural network forward pass (no training, inference only), where every operation is a linear layer followed by an activation. The network should take a query vector and output the nearest training example's label.

Algorithms & Data StructuresTechnical Trade-offsSystem Design

Author's notes

I knew the 1-NN problem from a prior round so I wasn't starting from zero, but rephrasing it as a literal forward pass with Wx+b layers and at least one activation was a different beast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, clarify that the network is a fixed computational graph with no learned parameters, where the training set is embedded as constant weights. Then, express each step—computing distances, finding the minimum, and retrieving the label—using linear layers and activations, leveraging operations like squared distance expansion, softmax with low temperature for argmin, and one-hot label lookup.

Pro tip: Emphasize that this is a theoretical construction to demonstrate neural network expressiveness, not a practical implementation, and highlight the use of temperature scaling in softmax to approximate a hard minimum.

1. Clarify assumptions and setup

State that the network has no trainable parameters; training examples and labels are fixed constants. The input is a query vector x, and the output is the label of the nearest training example.

2. Compute squared distances to all training points

Use a linear layer to compute dot products between x and each training point, and another linear layer to compute the squared norm of x. Combine with precomputed squared norms of training points to get squared Euclidean distances via the identity ||x - t_i||^2 = ||x||^2 - 2 x·t_i + ||t_i||^2.

3. Find the index of the minimum distance

Apply a softmax with a very low temperature (or negative distances with high temperature) to approximate a one-hot vector indicating the nearest neighbor. Alternatively, use a hard-min activation if allowed, but softmax is more standard.

4. Map the one-hot index to the label

Use a linear layer with weights being the one-hot encoded labels (or label vectors) to output the label of the nearest neighbor. If labels are categorical, output a probability distribution over classes.

5. Discuss trade-offs and limitations

Mention that this construction is exact only with infinite precision; in practice, softmax temperature introduces approximation. Also note that the network size scales with the number of training examples, making it impractical for large datasets.

Key Points to Mention

The network is a fixed computational graph with no training; weights are set to training data and labels.
Squared Euclidean distance can be computed using linear operations and precomputed constants.
Softmax with low temperature approximates argmin, enabling differentiable selection.
The final linear layer acts as a lookup table from the one-hot index to the label.
The construction is theoretical and not scalable due to memory and computation costs.
Precision and temperature affect the exactness of the nearest neighbor retrieval.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.