一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 881|回复: 5
收起左侧

[找工就业] 一个关于亚马逊cache miss的疑问

[复制链接] |试试Instant~ |关注本帖
royal_916 发表于 2016-1-20 16:59:26 | 显示全部楼层 |阅读模式

2015(10-12月)-[14]CE硕士+fresh grad 无实习/全职 - 内推| 码农类全职@Amazonfresh grad应届毕业生

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

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

x
lz收到了video,然后cache miss 用了一个linkedlist做完。看到地理貌似说有什么linkedhashmap版本,求问这个题有必要用这个么?如果用的话是什么思路,这个算是比一个linkedlist有提升么?
感谢地理小伙伴!
baiery 发表于 2016-1-20 23:17:48 | 显示全部楼层
那是LRU cache 吧,Leetcode 原题那道,这里只是算个miss,不需要那么复杂的结构,帅哥加油面!
回复 支持 反对

使用道具 举报

fezfeng 发表于 2016-2-18 07:26:41 | 显示全部楼层
我觉得这个题linkedlist就很好了,请问楼主video时候对于这个题面试官提了什么问题呢?十分感谢!
回复 支持 反对

使用道具 举报

lxr 发表于 2016-2-18 07:32:55 | 显示全部楼层
我也是这道题 刚面完~. From 1point 3acres bbs
用hashmap+linked list可以把time complexity优化到O(m) m is the length of input array.
这里的hashmap以requested integer 为 value, 对应的linked list node pointer为value。这样在我们扫input array时,可以O(1) time check每一个integer是否在cache里。如果只有linked list那我们只能去遍历list确认了。这样总体的time complexity就变成了 O(m*n) n is cache size.
回复 支持 反对

使用道具 举报

fezfeng 发表于 2016-2-18 07:43:18 | 显示全部楼层
lxr 发表于 2016-2-18 07:32
我也是这道题 刚面完~
用hashmap+linked list可以把time complexity优化到O(m) m is the length of input  ...

十分感谢回复!很详细。这样说的时候要不要提一下空间换时间什么的?然后请问层主面试官是怎么问的呢?直接问优化方法?
回复 支持 反对

使用道具 举报

lxr 发表于 2016-2-18 07:46:26 | 显示全部楼层
fezfeng 发表于 2016-2-18 07:43
十分感谢回复!很详细。这样说的时候要不要提一下空间换时间什么的?然后请问层主面试官是怎么问的呢?直 ...

不用谢哈~
面试官木有问我这一道题= = 这是我当时准备video时想的
我的面经贴:http://www.1point3acres.com/bbs/thread-171898-1-1.html
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-5 21:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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