FastPrepDynamic Future Pricing

Dynamic Future Pricing

Optiver logoOptiver● MediumINTERNOA
Learn

Problem statement

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 = 1000dividends = [[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 = 500dividends = [[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.

More Optiver problems

See Optiver hiring insights
public long[] futurePrices(long stockPrice, long[][] dividends, String[] operations) {
  // write your code here
}
stockPrice1000
dividends[[100,10],[50,100]]
operations["PRICE 1","PRICE 10","PRICE 99","PRICE 100"]
expected[1000,900,900,850]
Checking account…