FastPrep
Problem · Array

Streaming Entropy, Part 3: Block-wise Entropy

Learn this problem
● MediumOpenAIFULLTIMEONSITE INTERVIEW

Problem statement

Streaming Entropy Interview Sequence

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

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

For the full stream,

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

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

Streaming Requirements

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

Do not concatenate the blocks, retain the full logits stream, or materialize the probability vector. Keep only constant-size aggregate state. This part uses moderate logits so that block-wise processing, rather than numerical stability, is the main challenge.

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.

Continue to Part 4: Stable Streaming Entropy.

Function

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

Examples

Example 1

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

The blocks form the logits [0, 0], which produce a uniform two-outcome distribution.

Example 2

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

The blocks form logits whose softmax probabilities are [0.25, 0.75].

Example 3

blocks = [[1.0, -1.0, 0.0], [2.0], [-2.0, 0.5]]return = 1.2511246070440085

This stream uses uneven blocks and includes positive, negative, and fractional logits.

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 [-20, 20].
  • Use the natural logarithm.
  • Use O(n) time and O(1) auxiliary space.

More OpenAI problems

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