传统Marketing行业的statistician/DS分享工作经验以及征求职业发展建议!

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
硅谷知名AI创业公司
图灵视频
招聘多个工程师职位
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
查看: 514|回复: 13
收起左侧

[找工就业] 面试题求解

[复制链接] |试试Instant~ |关注本帖
我的人缘0
bubblefish 发表于 2017-11-2 04:33:24 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (16)
 
 
15% (3)  踩

2017(7-9月)-[]CS本科+<3个月短暂实习/全职 - 校园招聘会| 码农类General实习@fresh grad应届毕业生

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

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

x
之前面试一家小公司,被问了这样一道题,interviewer给我的解释让我非常疑惑……来问问大家这个time complexity是怎么实现的
题目:
implement一个LRU cache,要求support set和get两个功能
比如说cache size是2
set("a", 1)-google 1point3acres
set("b", 2)
get("a") returns 1
get("b") returns 2
set("c", 3). 一亩-三分-地,独家发布
那么("a", 1)就会被从cache里evict掉
get(“a")就会return None

LRU的话就是least recently used,在cache存满的时候最先evict被使用过时间最久的那个key value pair

解题思路:
用一个dictionary来store cache的key value pair,用一个priority queue来储存key保证LRU
每次get的时候就把这个key从PQ里找到 pop出来 扔到PQ最顶上
但是如果用array implement PQ的话 array lookup是O(n)
interviewer说如果用doubly linked list来implement这个priority queue的话look up是O(1)
我就很迷茫了……
求解 来源一亩.三分地论坛.

上一篇:IXL OA拒
下一篇:Tableau SDE Intern 店面 1
我的人缘0
cutehuazai 发表于 2017-11-2 05:07:21 来自手机 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
你的hash表的value是doubly linkedlist的node
回复

使用道具 举报

我的人缘0
a92921 发表于 2017-11-2 04:36:10 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (90)
 
 
14% (15)  踩
为什么不是用哈希表+doubly linked list。。。
回复

使用道具 举报

我的人缘0
 楼主| bubblefish 发表于 2017-11-2 05:06:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (16)
 
 
15% (3)  踩
a92921 发表于 2017-11-2 04:36
为什么不是用哈希表+doubly linked list。。。

是啊 哈希表就是dictionary吧……
但是为什么doubly linked list有O(1) lookup啊 我们不知道每次要lookup的那个东西在linked list的哪个位置诶
回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-2 05:09:09 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
doubly linkedlist的目的在于你可以用o(1)的时间维持LRU。

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-2 05:09:34 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
而不需要用pq去保持
回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-2 05:11:53 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
而且把node作为value你就知道在哪个位置了。
回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-2 05:12:53 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
楼主没有刷过这道LC题吗?好好刷过应该知道这道题最优解是啥且为什么

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
a92921 发表于 2017-11-2 05:17:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (90)
 
 
14% (15)  踩
bubblefish 发表于 2017-11-2 05:06. 牛人云集,一亩三分地
是啊 哈希表就是dictionary吧……
但是为什么doubly linked list有O(1) lookup啊 我们不知道每次要looku ...

用了dict+doubly linkedlist就不需要pq了吧,比如这个链表(<->表示双向箭头)是这样的:. From 1point 3acres bbs
head <-> node <-> node ... node <-> tail.本文原创自1point3acres论坛
most recently used   ->   least recently used
head和tail是dummy node
dict里的K/V pair是key/node,直接通过key可以获取node,O(1)查找
如果某个node recently used了,就提前到head后面。删node就删tail前面那个。
回复

使用道具 举报

我的人缘0
ygnhzeus 发表于 2017-11-2 05:20:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (43)
 
 
0% (0)  踩
自己实现Node,双向指针,Hashmap存key->node
回复

使用道具 举报

我的人缘0
cutehuazai 发表于 2017-11-2 05:22:16 来自手机 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (107)
 
 
15% (19)  踩
楼上解释的更清楚。也可以双向链表维护least recent到most recent。思路是一样的。

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
alex.chan 发表于 2017-11-2 06:54:16 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  95% (124)
 
 
4% (6)  踩
嗯,楼上解释的很清楚。谢谢。
如果是java就要自己实现doubly linked list的Node

要不然就用LinkedHashMap
回复

使用道具 举报

我的人缘0
 楼主| bubblefish 发表于 2017-11-2 11:28:22 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (16)
 
 
15% (3)  踩
cutehuazai 发表于 2017-11-2 05:12.留学论坛-一亩-三分地
楼主没有刷过这道LC题吗?好好刷过应该知道这道题最优解是啥且为什么

诶搜了一下才发现这个居然leetcode上有!我还以为是公司很没创意的改编了CSAPP的lab题………大意了
回复

使用道具 举报

我的人缘0
 楼主| bubblefish 发表于 2017-11-2 11:32:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  84% (16)
 
 
15% (3)  踩
我明白了!感谢大家!dictionary里居然能直接存node……感觉是黑科技…………
回复

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

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

GMT+8, 2018-9-19 09:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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