Openai·Software Engineer·Onsite - Coding / Algorithms·Senior

Senior

Jul 2026

Summary

OpenAI SWE coding round focused on numerical computing, specifically computing entropy from logits in a way that doesn't blow up for large values. Two parts: a batch implementation and a streaming version with O(1) space. Pretty niche but actually a fair test of whether you understand floating point.

Questions Asked (2)

Implement a numerically stable function that computes entropy from a list of logits (unnormalized log-probabilities), without naively computing softmax probabilities first. Must handle logit values up to plus or minus 10,000.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The naive approach of exponentiating the logits directly just produces inf or 0 for large inputs and you get garbage.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Derive the entropy formula in terms of logits using the log-sum-exp trick to avoid overflow, then implement it with a numerically stable algorithm. Explain the derivation and discuss trade-offs like time complexity and precision.

Pro tip: Mention that you can compute entropy as logsumexp(logits) - sum(softmax(logits) * logits) and that using a max-shift ensures stability even for extreme values. Also note that for very large logits, the entropy approaches 0, so handle edge cases.

1. Derive the entropy formula

Start from the definition H = -sum(p_i * log p_i) and substitute p_i = exp(z_i)/Z, where Z = sum(exp(z_j)). Simplify to H = log Z - sum(exp(z_i) * z_i)/Z.

2. Apply the log-sum-exp trick

Compute log Z stably as m + log(sum(exp(z_i - m))), where m = max(z_i). This prevents overflow when logits are large.

3. Compute the weighted sum stably

Calculate sum(exp(z_i - m) * z_i) / sum(exp(z_i - m)) to get the expected logit, avoiding underflow/overflow.

4. Combine and handle edge cases

Compute H = log Z - expected_logit. For extreme logits, ensure that if one logit dominates, entropy is near zero; handle empty or single-element lists.

5. Analyze complexity and trade-offs

Discuss O(n) time and O(1) extra space, and compare with naive softmax which may overflow. Mention precision considerations for float32 vs float64.

Key Points to Mention

Log-sum-exp trick for numerical stability
Derivation of entropy in terms of logits: H = logsumexp(z) - sum(softmax(z) * z)
Avoiding explicit softmax computation to prevent overflow
Handling extreme values (e.g., ±10,000) by subtracting the maximum logit
Time and space complexity: O(n) time, O(1) extra space
Edge cases: empty list, single logit, all logits equal, one logit much larger

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

Design a StreamingEntropy class that processes logits one at a time with O(1) memory and computes the same numerically stable entropy at the end. The tricky part: the running maximum can change as new logits arrive.

Algorithms & Data StructuresSystem Design

Author's notes

This is where things got interesting.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by explaining the numerically stable entropy formula using the log-sum-exp trick, then design a streaming version that maintains a running maximum and a running sum of exponentials. When a new logit exceeds the current maximum, rescale the accumulated sum by multiplying it with exp(old_max - new_max) to keep the computation stable. Finally, compute entropy as log(sum_exp) + max - sum(logit * exp(logit - max)) / sum_exp, ensuring O(1) memory.

Pro tip: Emphasize that the rescaling step is crucial for numerical stability and that it only occurs when the maximum changes, so the amortized cost is O(1) per logit. Also, mention that you can avoid storing all logits by maintaining only the running max and the sum of exponentials.

1. Clarify the problem and constraints

Restate the goal: compute entropy of a stream of logits with O(1) memory and numerical stability. Confirm that logits arrive one at a time and we only need the final entropy.

2. Recall the stable entropy formula

Write the entropy formula using the log-sum-exp trick: H = log(sum(exp(logit - max))) + max - sum(logit * exp(logit - max)) / sum(exp(logit - max)). Explain why subtracting the max prevents overflow.

3. Design the streaming data structure

Maintain three variables: running maximum (max), sum of exponentials (sum_exp), and sum of logit * exp(logit - max) (sum_logit_exp). Update these incrementally as each logit arrives.

4. Handle maximum updates with rescaling

When a new logit exceeds the current max, update max and rescale sum_exp and sum_logit_exp by multiplying with exp(old_max - new_max). This keeps the accumulated sums consistent with the new max.

5. Compute final entropy and analyze complexity

After processing all logits, compute entropy using the maintained sums. State that time per logit is O(1) amortized (rescaling only on max change) and memory is O(1).

Key Points to Mention

Numerical stability via log-sum-exp trick and subtracting the running maximum.
O(1) memory by storing only running max, sum of exponentials, and sum of logit*exponential.
Rescaling of accumulated sums when the maximum changes to maintain consistency.
Amortized O(1) time per logit because rescaling happens only when a new maximum is encountered.
Correctness of the final entropy formula using the maintained sums.
Edge cases: empty stream, all logits equal, very large or very small logits.

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