Optiver Online Assessment 2022
Anonymous User
16165
Heap (Priority Queue)OptiverOnline AssessmentData StructureInterview

This is the question from Optiver Online Assessment for the position Software Engineer Intern Summer 2023 in London.
It's the second of 2 question in OA. The overall time for assessment was 2 hours.

__________________________________________________________________________________________________

Intro

Stock prices in the future are affected by dividends which is a fixed amount that gets paid out on a particular date.

Mathematically speaking, if today the stock price is S, and a dividend of amount A is to be paid out D days from now:

  • Future price from today till day D-1 is S
  • Future price from D onwards (including D) is S - A

Naturally, if there are multiple dividends this has an additive effect. Consider the following example:

Say the stock price today is S = 1000, and there are dividends:
(1) A[1] = 100, D[1] = 10 days from now:
(2) A[2] = 50, D[2] = 100 days from now.

Then the future prices varies as follows:

  • 1000 from Day 0 (today) to Day 9;
  • 900 (=1000-100) from Day 10 to Day 99;
  • 850 (=1000-100-50) from Day 100 onwards.

Problem statement

In this problem, you will be given today's stock price S, and N dividends - each with an amount A[i] and day D[i] from today (1 <= i <= N) as input.

You will also be asked to perform Q operations. Each operation is one of 2 types:

  • DIVIDEND_UPDATE(i, A, D) - Update the i-th dividend from (A[i], D[i]) to (A, D)
  • PRICE(F) - Output the future price on day F based on all N dividends

Constraints

  • 1 <= N, Q <= 10^5
  • 1 <= S, A <= 10^9
  • 1 <= D, F <= 10^6
  • 1 <= Number of DIVIDEND_UPDATE operations <= 500

__________________________________________________________________________________________________

My thoughts and ideas:
Sort dividends as pairs (Day, Price from that day onwards) by day (using Treeset). For example from problem statement it would be:

(0, 1000),
(10, 900)
(100, 850)

It allows us to answer the PRICE-query for logN time, by finding the floorKey element for given day F (the pair where the day value is less than F and is maximum among all such pairs).

But I couldn't come up with a way how to answer the DIVIDEND_UPDATE query for logN time.
Well, because of the last contraint it could also potentailly work for O(n) time which is pretty easy. But I'm still wondering if there is any solution or a data structure that could allow to answer both of the query types for logN.

Feel free to leave your thought in comments :)

Comments (8)