FastPrepIncremental Hard Attention with a KV Cache
Problems/Incremental Hard Attention with a KV Cache

Incremental Hard Attention with a KV Cache

OpenAI logoOpenAI● MediumFULLTIMEPHONE SCREENONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an OpenAI phone screen for a full-time role. The interview report describes debugging position initialization, causal masking, and the right contents of the value cache. Then you implement a KV cache. Here we chose integer hard attention, matrix shapes, ties going to the earliest score, limits, and a finite batch signature. They keep those state changes and give a fixed output. An unclear issue with the loss function is outside this exercise.

Implement a deterministic incremental attention adapter. The input contains n token embeddings and n position embeddings, each of dimension d, plus square key and value weight matrices.

At step t:

  1. Initialize the hidden vector as h = tokenEmbeddings[t] + positionEmbeddings[t].
  2. Use h as the query. Compute key = h * keyWeights and value = h * valueWeights with row-vector matrix multiplication, then append them to separate key and value caches.
  3. Apply the causal rule by considering only cached keys from steps 0 through t. Select the index with maximum dot product between the query and a cached key. Break ties by choosing the earliest index.
  4. Output the cached value at the selected index.

Return all output vectors in step order.

Function

cachedCausalHardAttention(tokenEmbeddings: int[][], positionEmbeddings: int[][], keyWeights: int[][], valueWeights: int[][]) → int[][]

Examples

Example 1

tokenEmbeddings = [[1,0],[1,1]]positionEmbeddings = [[0,0],[0,0]]keyWeights = [[1,0],[0,1]]valueWeights = [[0,1],[1,0]]return = [[0,1],[1,1]]

At each step, the newest key has the unique highest score. Values come from the separate value projection, not from the attention output.

Example 2

tokenEmbeddings = [[0,0],[0,0]]positionEmbeddings = [[1,0],[1,0]]keyWeights = [[1,0],[0,1]]valueWeights = [[2,0],[0,2]]return = [[2,0],[2,0]]

Position embeddings initialize both hidden vectors. Equal scores at the second step select the earlier cached value.

Constraints

  • 1 <= n <= 200.
  • 1 <= d <= 40.
  • Both embedding matrices have shape n x d.
  • Both weight matrices have shape d x d.
  • Every input value is between -100 and 100.
  • Every matrix product, attention score, and output fits in a signed 32-bit integer; use 64-bit intermediates when comparing scores.

More OpenAI Phone Screen questions

  • Secret Number Search with One-Call-Delayed FeedbackPHONE SCREEN · Seen Nov 2026
  • Determine the Winner of Three-Card HandsPHONE SCREEN · Seen Nov 2026
  • Grid Infection with Recovery After D DaysPHONE SCREEN · Seen Nov 2026
  • Sparse Plant Infection SimulationPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Light Source Hits: Sample, Compare, and FitPHONE SCREEN · Seen Nov 2026
  • Rectangle Point Coverage CountsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Adaptive Calibration ErrorPHONE SCREEN · Seen Nov 2026
  • Elevator Scheduling SimulationPHONE SCREEN · Seen Nov 2026
  • Evaluate Noisy AnnotatorsPHONE SCREEN · Seen Oct 2026
  • Network Endpoint or Cycle BoundaryOA · PHONE SCREEN · Seen Oct 2026

Similar questions at other companies

  • Spiral MatrixNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions
  • Apply a 2048 Board MoveGlean · PHONE SCREENGlean interview questions
  • Spiral Order with ObstaclesTemu · PHONE SCREENTemu interview questions
  • Spiral Matrix TraversalByteDance · PHONE SCREENByteDance interview questions
  • Stochastic Gradient Descent with MomentumMeta · ONSITE INTERVIEWMeta interview questions
  • S-Shaped Matrix TraversalFox Corporation · PHONE SCREEN
  • Longest Consecutive Same-Color LineGoogle · PHONE SCREENGoogle interview questions
  • Process Minesweeper Game OperationsAmperity · PHONE SCREENAmperity interview questions
  • Minesweeper Board UpdateUber · ONSITE INTERVIEWUber interview questions
  • Diagonal TraverseHive · PHONE SCREENHive interview questions
All OpenAI interview questionsSee OpenAI hiring insights
Saved
class Solution {
    public int[][] cachedCausalHardAttention(int[][] tokenEmbeddings, int[][] positionEmbeddings, int[][] keyWeights, int[][] valueWeights) {
        // Write your code here.
    }
}
Checking account…