《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 439|回复: 7
收起左侧

11.3 狗店面

[复制链接] |试试Instant~ |关注本帖
harris577 发表于 2017-11-11 05:22:39 | 显示全部楼层 |阅读模式

2018(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
歐洲大叔面的 上來就扯天氣 加州乾旱扯了10分鐘 接著就出很長的一道題 說什麼股市交易...25分鐘都過了 . 1point3acres.com/bbs
反正就是設計一個數據結構
實現五個function
update(long timestamp, long price)
delete(long timestamp)
change(long timestamp, long price)
getMaxPrice()
getMostRecent()

例如. more info on 1point3acres.com
update(1, 300)
update(2, 330). Waral 鍗氬鏈夋洿澶氭枃绔,
update(3, 315). 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
change(1, 500)
delete(2)
getMaxPrice--> 500
getMostRecent-->330

我是用stack + hashmap + linkedlist node做的
get都是O(1)  update, delete, change都是O(n) 結果跪了-google 1point3acres
不知道有沒有人有更好的想法

qpalzm0827 发表于 2017-11-11 06:08:54 | 显示全部楼层
HashMap + linkedList 就像LRU Cache 一样, 就可以使得除getMaxPrice之外都是O(1)了, 会不会好一些呢?. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果想getMaxPrice快一些, 可以加个heap? 但是要支持快速删除的话可能需要hash heap, 这样除getMostRecent之外都是log(n)
回复 支持 1 反对 0

使用道具 举报

18844549105 发表于 2017-11-11 05:56:03 | 显示全部楼层
一个hashmap存就够了?然后保留一个timestamp最大的值和一个price最大的值。
回复 支持 反对

使用道具 举报

qpalzm0827 发表于 2017-11-11 06:10:08 | 显示全部楼层
18844549105 发表于 2017-11-11 05:56
一个hashmap存就够了?然后保留一个timestamp最大的值和一个price最大的值。

如果没有更新和删除操作, 是可以存着最大值的
回复 支持 反对

使用道具 举报

Lizard squad 发表于 2017-11-11 13:38:24 | 显示全部楼层
楼主能仔细说下getMostRecent()的接口定义吗,是指在时间上最近的一个还是最后一个操作过的节点?看楼主的列子意思是最后一个操作过的节点?update change delete都算?
回复 支持 反对

使用道具 举报

tangalai 发表于 2017-11-11 13:45:48 | 显示全部楼层
MaxStack 的变种吧。。
回复 支持 反对

使用道具 举报

 楼主| harris577 发表于 2017-11-11 13:55:05 来自手机 | 显示全部楼层
Lizard squad 发表于 2017-11-11 13:38-google 1point3acres
楼主能仔细说下getMostRecent()的接口定义吗,是指在时间上最近的一个还是最后一个操作过的节点?看楼主 ...

抱歉打錯了 getMostRecent應該為return 315 不是330
回复 支持 反对

使用道具 举报

say543 发表于 2017-11-12 15:16:19 | 显示全部楼层
有讨论tradeoff 哪个比较 frequency 吗 感觉都可以做到logn (if tree 有balance的话) ?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-25 17:51

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表