Dynamic Future Pricing
Reported by candidates from Optiver's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Optiver reported this one in October 2022, and the input sizes are the whole story. Up to 10^5 dividends and 10^5 operations means rescanning the dividend list on every PRICE query will time out. Dynamic Future Pricing looks like a finance word problem, but it's a point-update, prefix-query problem in disguise. Days go up to 10^6, so you can index straight on the day. If you blank on the structure during the OA, StealthCoder runs invisibly on your screen and gives you a working solution as a safety net. Know the shape first and you probably won't need it.
The problem
A stock has today's price stockPrice and a list of dividends. Each dividend is represented by [amount, day]. Beginning on its payment day, that amount is subtracted from every future price. Process the operations in order: UPDATE i amount day replaces the i-th dividend, using one-based indexing. PRICE day asks for the future stock price on that day. Subtract every current dividend whose payment day is at most the queried day. Return the answers to all PRICE operations in their original order. Function futurePrices(stockPrice: long, dividends: long[][], operations: String[]) → long[] Examples Example 1 stockPrice = 1000 dividends = [[100,10],[50,100]] operations = ["PRICE 1","PRICE 10","PRICE 99","PRICE 100"] return = [1000,900,900,850] The first dividend starts affecting the price on day 10, and both dividends affect it beginning on day 100. Example 2 stockPrice = 500 dividends = [[20,5],[30,10]] operations = ["PRICE 10","UPDATE 1 40 12","PRICE 10","PRICE 12","UPDATE 2 5 3","PRICE 2","PRICE 3"] return = [450,470,430,500,495] Moving the first dividend to day 12 removes it from the day-10 query. The second update moves a dividend to day 3. Constraints 1 <= dividends.length, operations.length <= 10^5 1 <= stockPrice, amount <= 10^9 1 <= day <= 10^6 At most 500 operations are UPDATE operations. Every update index is valid. Future prices and cumulative dividend amounts fit in a signed long.
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: PRICE day is a prefix sum over dividend amounts keyed by payment day. Use a Fenwick tree (BIT) of size 10^6 indexed by day. Load every dividend with add(day, amount). For PRICE, answer stockPrice minus query(day). For UPDATE i, remove the old dividend with add(oldDay, -oldAmount), add the new one, and store it in your array. Every operation is O(log 10^6). The pitfall is the one-based update index, so store the current dividends in an array and mutate it. Another is using int, since sums can reach 10^14, so use long. The note that at most 500 updates are allowed is a tempting hint to rebuild a prefix array per update, which works but costs about 500 times 10^6. The BIT is cleaner. If the BIT slips your mind mid-assessment, StealthCoder is the hedge that hands you the structure while you keep typing.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Dynamic Future Pricing cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Optiver's OA.
Optiver reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Dynamic Future Pricing FAQ
What's the trick in Dynamic Future Pricing?+
Treat each dividend as a value at its payment day and answer PRICE as stockPrice minus the prefix sum up to the queried day. A Fenwick tree over days 1 to 10^6 gives log-time updates and queries. Brute force rescans every dividend per query and fails at 10^5.
Why does the 500 UPDATE limit matter?+
It opens a second route. You could keep a prefix array over days and rebuild it on each update, about 500 times 10^6 work. It's heavy but plausible. The Fenwick tree is safer and simpler, so you don't need to lean on that limit.
What data types should I use?+
Use 64-bit integers everywhere for the price, amounts, and tree sums. The constraints say cumulative amounts fit in a signed long, but they won't fit in a 32-bit int. Day values fit in int, and the tree size is 10^6 plus one.
How do I handle UPDATE correctly?+
Parse the index and subtract one for zero-based storage. Remove the old amount at the old day from the tree. Add the new amount at the new day. Then overwrite the stored pair so a later update to the same dividend removes the right values.
How do I prepare for this Optiver OA in 48 hours?+
Write a Fenwick tree from memory twice, with point update and prefix query. Then solve this problem end to end, including parsing the operation strings. Test against both examples. Parsing and off-by-one errors cost more points than the algorithm does.