931. Price Corrections

Medium3.5 points estimatedDesignHash TableHeapOrdered Set4 hints
RPby Rohit Parihar

A trading screen receives price readings that carry a timestamp, possibly out of order, and sometimes re-sends a timestamp to correct an earlier mistake. Build PriceCorrections with an empty constructor.

update(timestamp, price) records the price for that timestamp; if the timestamp already has a price, the new value replaces it and the old value is forgotten. current() returns the price of the largest timestamp seen so far. maximum() and minimum() return the highest and lowest price among the corrected readings that are currently recorded, one per timestamp. These three queries are only called after at least one update. Aim for O(log n) per call.

Example 1

Input:
operations = ["PriceCorrections","update","update","current","maximum","minimum","update","maximum","minimum","update","current"]arguments = [[],[14,230],[9,415],[],[],[],[9,120],[],[],[20,300],[]]
Output:
[null,null,null,230,415,230,null,230,120,null,300]
Explanation:

Readings arrive out of order. The latest timestamp is 14 so current is 230, the highest is 415 and the lowest is 230. Correcting timestamp 9 to 120 makes 300 on timestamp 20 the new latest after its update, while the maximum becomes 230 and the minimum 120.

Example 2

Input:
operations = ["PriceCorrections","update","maximum","update","minimum","current"]arguments = [[],[5,77],[],[5,88],[],[]]
Output:
[null,null,77,null,88,88]
Explanation:

The reading for timestamp 5 is overwritten, so the old value 77 no longer counts: maximum was 77, then the minimum and the current price both become 88.

Constraints

1 ≤ timestamp, price ≤ 109

At most 2000 calls in total; current, maximum and minimum are called only after an update

How this problem is judged

Answers
Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Input
Each case is an operation log. operations names the class first and then each method call; arguments holds the arguments for each, in the same order. Your answer is one list with a result per operation - null for the constructor and for methods that return nothing.

Expected complexity

Time
O(log n) amortised per call
Space
O(n)

What the author was aiming for. Your own solution is not measured against it.

Asked in an interview

Were you asked this in an interview? Say where, anonymously.

Code
Loading the editor…

operations names the class, then each method to call; arguments holds one list of arguments per operation, in the same order.