Katkat
Back

Implement Three Research Coding Tasks

OpenAISoftware Engineer · HR Screen
MediumSoftware EngineerHR ScreenCoding & Algorithms

Last updated

This problem tests fundamental understanding of numerical stability in probability, memory-efficient buffering, and greedy combinatorial optimization.

Part 1: Log-Sum-Exp Trick

Given an array of raw logits x (floats), implement a function softmax(x) that returns the probabilities. You must handle numerical overflow/underflow issues.

def softmax(x: list[float]) -> list[float]:
    # Returns list of probabilities

Part 2: Circular Buffer Streaming

Implement a class RollingVariance that maintains the variance of a stream of numbers using a window size k. The implementation must be O(1) per update and numerically stable (Welford's algorithm or similar).

class RollingVariance:
    def __init__(self, k: int):
        pass
    def update(self, val: float) -> float:
        # Returns current variance

Part 3: Token Balancing

Given a list of token weights, partition them into two sets such that the absolute difference between their sums is minimized. The weights are strictly positive integers. Provide a solution with a time complexity better than O(2^n).

def minimize_weight_diff(weights: list[int]) -> int:
    # Returns minimum absolute difference

Examples

  • softmax([1000, 1001]): Should return [1/(1+e), e/(1+e)] instead of [NaN, NaN].
  • minimize_weight_diff([1, 2, 3, 9]): Should return 3 (Sets are {1, 2, 3} and {9}).

Constraints

  • n (array length) up to 1000 for Part 1 & 3.
  • k up to 10^5 for Part 2.
  • Memory usage should be O(k) for the buffer.

Hints

Hint 1

For softmax, subtract the maximum value in the array from every element before exponentiating.

Hint 2

For the rolling variance, maintain the sum of elements and the sum of squares of elements within the window to calculate variance as (sum_sq - (sum^2)/k) / k.

Hint 3

For the partition problem, recognize this as a variation of the subset sum problem and use dynamic programming to track reachable sums.

Follow-up questions

  • How would you modify the softmax implementation to handle a 2D tensor of logits?
  • What are the precision trade-offs between using a naive sum-of-squares formula versus Welford's algorithm in the rolling variance?
  • How does the time complexity of your partition solution change if the weights are very large but the number of elements is small?