3 U5 l v/ Y1 I; VI was asked to design a stock ticker system. Stock ticker is simply the shortened name of company and its current stock size. e.g. for Apple - "AAPL" -> "115"2 q$ ~/ k/ y$ c' R4 p8 l
He asked me to design a data structure to store incoming stream of stock tickers. Stream can contain same company more than once but all the values of it had to be stored. I used HashMap<String, List<Integer>>. Then he was adding more functionalities to system I don't exactly remember the questions now but one of them was related to calculating some ratio in constant time. Some of the questions were challenging.
Wouldn't a trie with a queue for each node be a nice structure. Wherever queue is present, it indicates a ticker from root to that node exist. And queue can hold the prices read so far in the incoming stream. Thoughts/suggestions?
发表于 2-5-2017 02:45 PM
