Streaming Entropy, Part 1: Batch Entropy

Streaming Entropy interview sequence
This is Part 1 of one four-part ML coding exercise.
Part 1: Batch Entropy
Part 2: Numerically Stable Entropy
Part 3: Block-wise Entropy
Part 4: Stable Streaming Entropy
A model produces a one-dimensional array of logits x[0], x[1],..., x[n - 1]. The logits define a probability distribution through softmax:
p[i] = exp(x[i]) / sum(exp(x[j]))
The entropy of that distribution is:
H = -sum(p[i] * ln(p[i]))
Here, ln is the natural logarithm. Given all logits at once, return the non-negative entropy of their softmax distribution. An answer is accepted when its absolute or relative error is at most 1e-6.
This opening part uses moderate logits, so numerical overflow and underflow are not the focus yet. Your implementation should run in O(n) time.
After solving this part, continue to Part 2: Numerically Stable Entropy.

Function
entropy(logits: double[]) → double

Examples
Example 1
logits = [0.0, 0.0]
return = 0.6931471805599453
The two logits are equal, so softmax produces [0.5, 0.5]. The entropy is -2 * 0.5 * ln(0.5) = ln(2).
Example 2
logits = [0.0, 1.0986122886681098]
return = 0.5623351446188083
The second logit is ln(3), so the probabilities are [0.25, 0.75].
Example 3
logits = [2.0, 1.0, 0.0]
return = 0.8323955818399389
Softmax is unchanged if the same constant is added to every logit. This distribution is equivalent to the logits [0, -1, -2].

Constraints
1 <= logits.length <= 2 * 10^5
Every logit is finite and lies in [-20, 20].
Use the natural logarithm.
Use O(n) time.

The trick is algebra. Entropy is H = -sum(p * ln p), and ln p[i] = x[i] - ln(Z), where Z is the sum of exp(x[j]). So H = ln(Z) - sum(p[i] * x[i]). That's two passes: one to compute Z, one to compute the weighted sum of logits. No need to call ln on every probability, which also dodges ln(0) worries. The pitfall is a nested loop that recomputes the softmax sum per element, which is O(n^2) and dies at 2 * 10^5. Logits sit in [-20, 20], so plain exp is safe here. Still, subtract the max anyway, because Part 2 is about exactly that and it costs you nothing. Return a double and trust the 1e-6 tolerance. If you freeze mid-OA, StealthCoder is the hedge that keeps you moving.

Memorize the pattern. If you can't, run StealthCoder. The proctor sees the IDE. They don't see what's behind it.