Equity Price History with O(1) Statistics
Bloomberg LP● MediumNEW GRADONSITE INTERVIEWProblem statement
Process a finite sequence of operations over one equity's daily price history. Prices are nonnegative integer cents.
["UPDATE", price]appends the next daily price.["REMOVE"]removes the most recently appended price.["LATEST"]emits the latest price as an integer string.["MAX"]emits the maximum current price as an integer string.["AVERAGE"]emits the exact current average as a reducednumerator/denominatorstring. Always include the denominator, even when it is1.
Every remove or query is valid: at least one price exists before that operation. Return query results in encounter order. Design the history so every operation runs in O(1) time.
Function
processEquityPrices(operations: String[][]) → String[]Examples
Example 1
operations = [["UPDATE","100"],["UPDATE","120"],["AVERAGE"],["MAX"],["LATEST"],["REMOVE"],["AVERAGE"],["LATEST"]]return = ["110/1","120","120","100/1","100"]After two updates the average is 220/2 = 110/1. Removing the latest price restores the one-price history.
Example 2
operations = [["UPDATE","0"],["UPDATE","1"],["UPDATE","2"],["AVERAGE"],["REMOVE"],["AVERAGE"],["MAX"],["LATEST"]]return = ["1/1","1/2","1","1"]The first average is 3/3, reduced to 1/1. After removing 2, the exact average is 1/2.
Example 3
operations = [["UPDATE","5"],["UPDATE","3"],["UPDATE","8"],["REMOVE"],["MAX"],["LATEST"],["AVERAGE"]]return = ["5","3","4/1"]Removing 8 exposes 3 as the latest price while the remaining maximum is 5.
Constraints
1 <= operations.length <= 100000.- Each operation is one of the five documented forms.
0 <= price <= 1000000000.REMOVE,LATEST,MAX, andAVERAGEoccur only when the history is nonempty.- The sum of current prices fits in a signed 64-bit integer.