当前在线人数13769
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
狗面经题2
[版面:待字闺中][首篇作者:uwwu] , 2018年07月11日12:33:18 ,412次阅读,3次回复
来APP回复,赚取更多伪币 关注本站公众号:
[分页:1 ]
uwwu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: uwwu (Vera), 信区: JobHunting
标  题: 狗面经题2
发信站: BBS 未名空间站 (Wed Jul 11 12:33:18 2018, 美东)

这题怎么搞。。?

设计股票价格的记录系统
只观察一支股票的价格,实现几个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.)



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

 
garphy
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: garphy (喜欢猫), 信区: JobHunting
标  题: Re: 狗面经题2
发信站: BBS 未名空间站 (Wed Jul 11 12:52:06 2018, 美东)

感觉前几天有人问过了?这莫不是狗家最新题库

【 在 uwwu (Vera) 的大作中提到: 】
: 这题怎么搞。。?
: 设计股票价格的记录系统
: 只观察一支股票的价格,实现几个function:
: - vold update(double price, int timestamp) 更新/修正/删除股票价格,其中
: timestamp大部分
: 时间是递增的,但是有时候发现过去的记录有错误,所以会对过去数据修正或
: invalidate。
: 对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp
,让
: price为function新提供的price;invalidat时候function argument中的price为-1,
: 删除
: ...................




--
☆ 发自 iPhone 买买提 1.24.07
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1010:b048:]

 
garphy
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: garphy (喜欢猫), 信区: JobHunting
标  题: Re: 狗面经题2
发信站: BBS 未名空间站 (Wed Jul 11 12:54:36 2018, 美东)


这题不就是一个array就完事的嘛?有了新的时间直接append到最后。如果修改老的数
据的话,就告诉面试官你见过多少历史数据出错的?这个case交给on call解决。真出
现了rebuild index就行了。

这个面试官的意思肯定是弄两个自平衡的二分排序树,一个大根一个小根,这样所有修
改都是O(logn)。看到这样的题就应该直接告诉他,你这一个类做了两件事,一个是存
储历史数据,一个是对最大最小值的索引和查找。让他回去重新上大一学一下solid里
面的s是个什么意思。这样的面试题本身就是违背原则的,不面也罢!

如果真是狗家面试,那更不能怂,10分钟赶快写好bug free的logn解答,然后当面告诉
丫,你们的园区真漂亮,题目真有价值,能够加入谷歌是我一辈子的愿望,我特别喜欢
你们的文化。

【 在 uwwu (Vera) 的大作中提到: 】
: 这题怎么搞。。?
: 设计股票价格的记录系统
: 只观察一支股票的价格,实现几个function:
: - vold update(double price, int timestamp) 更新/修正/删除股票价格,其中
: timestamp大部分
: 时间是递增的,但是有时候发现过去的记录有错误,所以会对过去数据修正或
: invalidate。
: 对过去数据修正是指input argument中的timestamp是一个已经记录在案的timestamp
,让
: price为function新提供的price;invalidat时候function argument中的price为-1,
: 删除
: ...................





--
☆ 发自 iPhone 买买提 1.24.07
--
※ 修改:·garphy 於 Jul 11 13:04:18 2018 修改本文·[FROM: 2600:1010:b02c:8]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 2600:1010:b048:]

 
uwwu
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: uwwu (Vera), 信区: JobHunting
标  题: Re: 狗面经题2
发信站: BBS 未名空间站 (Wed Jul 11 13:05:24 2018, 美东)

谢谢,我是看面经总结里的,应该是个典型问题
有人给了他的答案,我觉得不怎么看得懂(第一种实现里什么叫update:大多数O(1),
少数O(n);如果max price的股票Invalidated,怎么update max还是O(1)  ??? 第二种
实现 min/max Heap 怎么update??)
第一种实现:假设update频率比较低
Map<Integer, Double> time2Price;
Double min;
Double max;
Double current;
那么
- update:大多数O(1),少数O(n)
- Max, min, current:O(1)
- S(n)
第二种实现:update频率较高
Map<Integer, Double> time2Price;
MinHeap<int[]> minHeap;
MaxHeap<int[]> maxHeap;
LinkedList<int[]> list;
那么:
- update:O(log n)
- max(), min(): 最好O(1),最坏O(k log k)
- list:最好O(1),最坏O(k)
- S(n)
【 在 garphy (喜欢猫) 的大作中提到: 】
: 这题不就是一个array就完事的嘛?有了新的时间直接append到最后。如果修改老的数
: 据的话,就告诉面试官你见过多少历史数据出错的?这个case交给on call解决。真出
: 现了rebuild index就行了。
: ,让




--
※ 修改:·uwwu 於 Jul 11 13:06:01 2018 修改本文·[FROM: 68.]
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 68.]

[分页:1 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996