Google股票题目抛砖引玉

最近查面经好多人都碰到股票题目，如：
1）
2nd round: 紧接着进来一个白人大叔。他的macbook air的电池出了问题，先问了hashtable实现方法，于是直接开始出问题。给一个stock，这只股票在不同的timestamp下有不同的price，(800, 1), (700, 2), (900, 3), (400, 4)。 Looks like this. 需要实现几个方法：1.getMaxHistory, 2.getCurrentPrice, 3.Correction, 4. update。比如说刚才给出的例子是900最高，但是如果调用correction，将ts = 3的price改为600，那么最高的将变为800


2）
void update(double price, int timestamp) 更新/修正/删除股票价格，其中timestamp大部分时间是递增的，但是有时候发现过去的记录有错误，所以会对过去数据修正或invalidate。对过去数据修正是指input argument中的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

7832">new TreeSet<>();
        Map<Long, StockNode> map = new HashMap();
        //....
    }
}

帮顶zszszs

补充内容 (2018-11-25 10:36):
我想到的是HashTable+Heap

如果只用treeset的话， 我有两个时间点是最大的， 如果改掉一个，还剩一个。  treeset就不能handle了
treemap 可以， key: price， value: count，  改动的时候，就直接减一

如果用heap的话，需要delete操作，这个复杂度是O(n)。但如果自己实现heap的话，用个hashmap保存timestamp在heap中的位置，删除的时候根据hashmap找到那个node，删除是O（logn）

不过还是用TreeMap好写一点吧