Design Stock Price Display System

http://www.cnblogs.com/EdwardLiu/p/6369029.html

Implement a simple stock price display system which will show High, Low and Last price for a given stock throughout one day.The data comes from a real-time feed and have the following messages:
PriceUpdate(t, P) -> Price of Stock A at timet is P.
Correction(t, NewP) -> Price of Stock A attime t is rectified to NewP
Remove(t) -> Disregard the price feedreceived at time t.
PriceUpdate(10100,850.50) -> high = 850.50, Low = 850.50, Last = 850.50
PriceUpdate(10200,852.25) -> high = 852.25, Low = 850.50, Last = 852.25
PriceUpdate(10300,848.00) -> high = 852.25, Low = 848.00, Last = 848.00
Correction(10200, 849.00) -> high = 850.50, Low = 848.00, Last 848.00
PriceUpdate(10400,855.00)  -> high = 855.00, Low = 848.00, Last = 855.00
Correction(10300, 853.00) -> high = 855.00, Low = 850.50, Last = 855.00
PriceUpdate(10500,854.00) -> high = 855.00, Low = 848.00, Last = 854.00
Correction(10500,853.25) -> high = 855.00, Low = 848.00, Last = 853.25
Remove(10300) -> high = 855.00, Low = 849.00, Last = 853.25

简单说来PriceUpdate就是添加新的（timestamp, price）, Correction是改之前的(timestamp, price), 求实现当前high(), low(), last()

LZ是用的Heap + HashMap, 特别问了时间复杂度(我猜到他想考heap的remove(obj)复杂度)

follow Up是: 有没有办法把复杂度降到O(logN)

 

LZ是用的Heap + HashMap, 特别问了时间复杂度(我猜到他想考heap的remove(obj)复杂度)

LZ是用treeMap代替了Heap，这样代价是每次找high,low也要logN search整个tree了

 

感觉需要2个数据结构：
1. TreeMap<Long, Double> time2priceMap. 
2. TreeMap<Double, Integer> price2countMap

priceupdate: insert new record into time2priceMap, update price count in price2countmap
correction: update record in time2pricemap, update prev price count, update prev price count (if 0, remove record), update new price count or needs to insert a new price record into price2countmap
high and low: lastkey and firstkey from price2countmap
last: last entry's price from time2pricemap

补充内容 (2017-2-4 07:00):
这样好像都是O(log(n))

Get average stock price every 10 minutes | Hello World
Write a class that displays average of stock prices for a given stock symbol for the last 10 minutes. We have a service that sends stock updates about 5000 times per second. The structure of the message is :
Message {
long timestamp;
String symbol; // E.g. AAPL
double price;
}
Idea: Use a buffer that has the capacity of 5000 * 60 * 10 messages. Then insert all the messages in to this buffer if the buffer has extra capacity. if the buffer is full, remove from the head and insert new messages from the tail. When the get average price is called, we calculate all the messages in this buffer.

We can store pre-sum in fixed size linked list.
Read full article from Get average stock price every 10 minutes | Hello World