FastPrep
Problem · Array

Streaming Entropy, Part 4: Stable Streaming Entropy

Learn this problem
● HardOpenAIFULLTIMEONSITE INTERVIEW

Problem statement

Streaming Entropy Interview Sequence

This is Part 4 of one four-part ML coding exercise.

The logits of one softmax distribution arrive in consecutive, non-empty blocks. Concatenating the blocks in order would produce the complete stream x.

For the full stream,

p[i] = exp(x[i]) / sum(exp(x[j]))

H = -sum(p[i] * ln(p[i]))

The logits may be extremely large or small. Direct exponentiation can overflow, and a later block may contain a new maximum that changes the scale of every previously accumulated exponential.

Streaming Requirements

Process the blocks in order and return the non-negative entropy over every logit in the stream.

Do not concatenate the blocks, retain all logits, materialize the probability vector, or make a preliminary pass to find the global maximum. Keep a running maximum and constant-size aggregate state. Whenever the running maximum increases, rescale the previously accumulated state before merging the new block.

Your implementation must run in O(n) time and use O(1) auxiliary space, where n is the total number of logits.

An answer is accepted when its absolute or relative error is at most 1e-6.

This completes the four-part Streaming Entropy interview sequence.

Function

streamingEntropy(blocks: double[][]) → double

Examples

Example 1

blocks = [[0.0], [0.0]]return = 0.6931471805599453

The two logits produce probabilities [0.5, 0.5]. Their entropy is ln(2).

Example 2

blocks = [[0.0], [1.0986122886681098]]return = 0.5623351446188083

The second logit is ln(3), so the probabilities are [0.25, 0.75]. The running maximum also increases after the first block.

Example 3

blocks = [[1000.0, 1000.0], [-1000.0]]return = 0.6931471805599453

Directly evaluating exp(1000) overflows. A stable running scale keeps the first two outcomes at probability 0.5 each while the third is negligible.

Constraints

  • 1 <= blocks.length <= 10^4
  • 1 <= blocks[i].length
  • The total number of logits across all blocks is at most 2 * 10^5.
  • Every logit is finite and lies in [-10^9, 10^9].
  • Use the natural logarithm.
  • Process the stream in one pass over the blocks.
  • Use O(n) time and O(1) auxiliary space.

More OpenAI problems

drafts saved locally
public double streamingEntropy(double[][] blocks) {
  // write your code here
}
blocks[[0.0], [0.0]]
expected0.6931471805599453
checking account