Interview Experience | Applied AI / Backend | π₯π₯ | OpenAI
2026 (Oct) Software Engineer, Implicit Signals @ OpenAI β San Francisco, CA β Phone β 1 round | π Neutral | Medium-Hard
Phone β Coding
Coding was one problem in four parts, each part shown only after the previous one was done. Python.
Part 1: given n pairs (score, label), label is 0/1. Pick a threshold t, score >= t predicts positive, return the t with the highest accuracy. Sorted by score and swept left to right, left side predicted negative, right side positive, keeping the count of negatives on the left and positives on the right. First version ignored equal scores, so two items with the same score got split across the threshold. He gave a tie example, changed it so equal scores move together.
Part 2: human review can flip one item's label, and after flip(i) I need the current best t right away. First said just rescan after every flip, O(n). He asked what if there are lots of flips and n is large. Took a while. Scores don't change, so sorted positions are fixed and only one value changes. Negatives on the left are correct, positives on the right are correct. Write a negative as +1 and a positive as -1, then accuracy is total positives plus the sum of the left part, so you want the max prefix sum. Segment tree where each node stores the range sum and max prefix, merge is max(L.pre, L.sum + R.pre), a flip updates one leaf and walks up. He asked to also return where the max is reached, so I stored an index in the node. The tie issue came back here, you can only cut at the boundary of a tie group.
Part 3: two thresholds low < high, the middle isn't predicted and goes to human review at cost c each. Maximize correct minus c times the number sent to review, still with flips. Got that the node also needs a max suffix: a left part predicted negative, a right part predicted positive, every middle item worth -c. When merging, the best cut can have both thresholds in the left child, both in the right child, or one in each. Got the one-in-each case, combining the left child's "prefix + middle" with the right child's "middle + suffix". For the case where both land on one side and the other child is entirely middle, you need extra fields like "prefix + whole range as middle". Didn't list out every field the node needs, only half written.
Part 4: new items keep arriving and scores aren't known up front, so you can't sort and build the tree first. Said offline you could collect all scores and compress coordinates, online you'd need a balanced tree or a dynamic segment tree. Time was up, didn't write it.