Optiver OA Interview Experience (2026) - Max-Heap Halving & K-Partition First-Last DP, Offer

Problem 1: Minimum Array Sum After D Halving Operations

Problem: Given an integer array weights , on each of d consecutive days you must pick one element, subtract floor(element / 2) from it, and replace it in the array. Return the minimum possible sum of the array after all d operations.

This is greedy on the largest-loss element per day. Each day you want to pick the element whose halving reduces the sum the most, which is always the current largest element (because floor(x / 2) is monotonic in x ). That means the optimal policy is: on each day, extract the max, halve it, and put the halved value back.

A max-heap does the bookkeeping in O(log n) per operation for d operations total. A naive re-sort after each day is O(d n log n) which passes small inputs but times out at the upper bound. The heap brings the total to O(d log n) .

The edge cases: elements of value 0 or 1 halve to themselves, so the greedy will stall on them if the array is entirely small. That is fine, the sum simply cannot decrease further. Also, the problem does not require you to halve a new element each day, you can keep halving the same largest value repeatedly, which is actually what a max-heap will do naturally.

Practice it: no exact match in the current Optiver set, so I did not link this one.

This question is coming soon to HackTheRounds.

Problem 2: Minimum K-Partition Cost by First-and-Last

Problem: Given an integer array videoChunks and a positive integer k , partition the array into exactly k non-empty contiguous subarrays. The cost of a subarray is the sum of its first and last elements. Return the minimum total cost across all valid partitions.

Two-dimensional DP on prefix length and number of partitions used. Let dp[i][j] be the minimum cost to partition the first i elements into exactly j subarrays. The transition enumerates the starting index of the last subarray: if the last subarray is arr[m + 1 .. i] for some m between j - 1 and i - 1 , then dp[i][j] = min over m of (dp[m][j - 1] + arr[m + 1] + arr[i]) .

The outer iteration is over (i, j) and the inner over m , giving O(n^2 k) in the naive form. For n and k both up to a few hundred, that passes comfortably. For the larger n = 10^4 variant some candidates saw, you need to isolate the arr[i] contribution out of the min and reduce the inner loop to arr[i] + min over m of (dp[m][j - 1] + arr[m + 1]) , which with a running-min gives O(n k) .

The subtle implementation point is the initialization. dp[0][0] = 0 , every dp[i][0] = infinity for i 0 , and every dp[i][j] where i < j is infinity because you cannot partition fewer elements into more subarrays. Off-by-one errors on the valid ranges of m are the usual failure mode.

Practice it: no exact match in the current Optiver set, so I did not link this one.

This question is coming soon to HackTheRounds.

Result

Both problems passed the full hidden-test grader. Invited to the trader tech round one week later, which is a live coding round plus a set of mental math drills. The rest of the loop went cleanly and I got the verbal offer three business days after the final VO. OA-to-offer took about seven weeks end to end, which is fast for a trading shop.

Tips

1. Heap-based greedy is the default for "repeat operation N times" prompts. If the problem says "each step pick an element, modify it, put it back" and the metric you care about is a running sum, the answer is almost always a max-heap or min-heap. Do not waste time trying to prove a closed-form.
2. For partition DP, separate out the term that depends only on the current index. The Optiver k-partition problem has an obvious `O(n^2 * k)` formulation, but the pruning to `O(n * k)` requires isolating `arr[i]` out of the min. Know this trick cold for any partition-cost problem, the linear-factor reduction is a common Optiver test case.
3. Sketch the recurrence before coding. Optiver's problems are short to implement but brutal on off-by-one errors. A 60-second diagram of your DP table on scratch paper saves you from re-reading your own code for the last twenty minutes of the session.
4. Watch for integer overflow on the sum. In C++ with `n = 10^4` and values up to `10^9`, the prefix sum of the array overflows `int`. Use `long long` everywhere. In Python this is free.
5. The Optiver grader is strict on performance. Hidden tests include large inputs specifically sized to fail the naive approach. If your submission passes the sample but times out on one hidden test, that is a sign your asymptotic is wrong, not that you had bad luck.
6. Prep both the algorithmic pool and the probability pool. Optiver rotates between the two this cycle and you cannot predict which set your session will pull from. The algorithmic pool rewards heap greedy and partition DP. The probability pool rewards optimal stopping and PSD constraints. Drill both.

This question is coming soon to HackTheRounds.