u**u
发帖数: 668 | 1 这题怎么搞。。？
设计股票价格的记录系统
只观察一支股票的价格，实现几个function：
- vold update(double price, int timestamp) 更新/修正/删除股票价格，其中
timestamp大部分
时间是递增的，但是有时候发现过去的记录有错误，所以会对过去数据修正或
invalidate。
对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp，让
price为function新提供的price；invalidat时候function argument中的price为-1，
删除
timestamp对应的记录
- double max() 返回历史最大值
- double min() 返回历史最低值
- double current() 返回最近一次的记录
针对各种情况进行实现和算法复杂度讨论。（大量更新？大量查询？invalidate很多很
少？etc.） |
g****y
发帖数: 2810 | 2 感觉前几天有人问过了？这莫不是狗家最新题库
，让
【在 u**u 的大作中提到】
: 这题怎么搞。。？
: 设计股票价格的记录系统
: 只观察一支股票的价格，实现几个function：
: - vold update(double price, int timestamp) 更新/修正/删除股票价格，其中
: timestamp大部分
: 时间是递增的，但是有时候发现过去的记录有错误，所以会对过去数据修正或
: invalidate。
: 对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp，让
: price为function新提供的price；invalidat时候function argument中的price为-1，
: 删除
|
g****y
发帖数: 2810 | 3 这题不就是一个array就完事的嘛？有了新的时间直接append到最后。如果修改老的数
据的话，就告诉面试官你见过多少历史数据出错的？这个case交给on call解决。真出
现了rebuild index就行了。
这个面试官的意思肯定是弄两个自平衡的二分排序树，一个大根一个小根，这样所有修
改都是O(logn)。看到这样的题就应该直接告诉他，你这一个类做了两件事，一个是存
储历史数据，一个是对最大最小值的索引和查找。让他回去重新上大一学一下solid里
面的s是个什么意思。这样的面试题本身就是违背原则的，不面也罢！
如果真是狗家面试，那更不能怂，10分钟赶快写好bug free的logn解答，然后当面告诉
丫，你们的园区真漂亮，题目真有价值，能够加入谷歌是我一辈子的愿望，我特别喜欢
你们的文化。
，让
【在 u**u 的大作中提到】
: 这题怎么搞。。？
: 设计股票价格的记录系统
: 只观察一支股票的价格，实现几个function：
: - vold update(double price, int timestamp) 更新/修正/删除股票价格，其中
: timestamp大部分
: 时间是递增的，但是有时候发现过去的记录有错误，所以会对过去数据修正或
: invalidate。
: 对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp，让
: price为function新提供的price；invalidat时候function argument中的price为-1，
: 删除
|
u**u
发帖数: 668 | 4 谢谢，我是看面经总结里的，应该是个典型问题
有人给了他的答案，我觉得不怎么看得懂（第一种实现里什么叫update：大多数O(1)，
少数O(n)；如果max price的股票Invalidated,怎么update max还是O(1) ??? 第二种
实现 min/max Heap 怎么update？？）
第一种实现：假设update频率比较低
Map time2Price;
Double min;
Double max;
Double current;
那么
- update：大多数O(1)，少数O(n)
- Max, min, current：O(1)
- S(n)
第二种实现：update频率较高
Map time2Price;
MinHeap minHeap;
MaxHeap maxHeap;
LinkedList list;
那么：
- update：O(log n)
- max(), min(): 最好O(1)，最坏O(k log k)
- list：最好O(1)，最坏O(k)
- S(n)
【在 g****y 的大作中提到】
: 这题不就是一个array就完事的嘛？有了新的时间直接append到最后。如果修改老的数
: 据的话，就告诉面试官你见过多少历史数据出错的？这个case交给on call解决。真出
: 现了rebuild index就行了。
: 这个面试官的意思肯定是弄两个自平衡的二分排序树，一个大根一个小根，这样所有修
: 改都是O(logn)。看到这样的题就应该直接告诉他，你这一个类做了两件事，一个是存
: 储历史数据，一个是对最大最小值的索引和查找。让他回去重新上大一学一下solid里
: 面的s是个什么意思。这样的面试题本身就是违背原则的，不面也罢！
: 如果真是狗家面试，那更不能怂，10分钟赶快写好bug free的logn解答，然后当面告诉
: 丫，你们的园区真漂亮，题目真有价值，能够加入谷歌是我一辈子的愿望，我特别喜欢
: 你们的文化。
|
