一亩三分地论坛

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

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

Google onsite 一道算法和最后一道系统题

[复制链接] |试试Instant~ |关注本帖
yoo 发表于 2016-6-22 03:21:37 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 本科 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
之前贴了面经,比较简略,这次详细贴一下:

这次面试跪在了一道算法题和一道系统设计题上,算法题我在这里详细讲了:http://www.1point3acres.com/bbs/ ... p;page=1#pid2473014
不过没有看到有谁回复解法。

系统设计题是关于Google保存图片供世界各地的用户访问,我们先只讨论read, 不理write,主要讨论cache。我首先提出用LRU cache, 在request某个图片的用户附近的服务器上cache这个图片,每次用户request图片都是先检查最近的服务器有没有,没有的话才回远方的主服务器访问。LRU的具体细节就像lc拿到题那样写了,不过面试官不是很关心LRU的写法,马上指出如果有些图片非常热门,访问量过亿,但是仅仅因为短时间内没有被这附近的人访问,就要被移出cache, 这并不合理。 我临时想了个办法,在LRU的基础上增加了一个popularity cache(纯蒙的)- 记下每个被访问图片的访问量,如果超过一个threshold, 把它移到popular cache里面,这里面的图片不再按照LRU的规则移除,而是按照访问量排序。最后为了避免某些一度非常大访问量的图片一直留在这个cache里,每过一段时间清理,即检查popular cache里面的图片上一次被访问是什么时候。。。   

虽然跪了,还是好奇这两个题应该怎么答。

评分

1

查看全部评分

readman 发表于 2016-6-22 03:35:01 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

blackrose 发表于 2016-6-22 03:28:39 | 显示全部楼层
你是说第二次面试 数组转圈的算法题? 那个就是一个两个指针swap 吧。swap(nums[i], nums[nums[i]]) 如果nums[i] == i 的话,不swap。这个题和leetcode find the first missing positive number 雷同。另外这个题其实可能有附加要求,比如不能改变原数组。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-22 03:31:22 | 显示全部楼层
Cache 这个题挺有意思,感觉面试官想让implement LFU least frequent used cache,抛弃最不常访问的。
-google 1point3acres
补充内容 (2016-6-22 03:32):
短时间内implement这个,感觉有点难为人。。。。。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-22 03:35:33 | 显示全部楼层
class cacheNode {. from: 1point3acres.com/bbs
  int key,
  int value;. 1point 3acres 璁哄潧
  int freq;
  cacheNode* prev;
  cacheNode* next;
}

class LFU{.1point3acres缃
  unordered_map<int, cacheNode> map;
  cacheNode* head;
  cacheNode* end;
}.鏈枃鍘熷垱鑷1point3acres璁哄潧
// 剩下的几乎和LRU相同,只是移除的时候,找到freq最小的拿走。 get 时候freq++。  不知道对不对,大家讨论哈/。
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-6-22 03:40:00 | 显示全部楼层
readman 发表于 2016-6-22 03:35
http://www.cs.cornell.edu/~qhuang/ http://dl.acm.org/citation.cfm?id=2522722

。。。。。我咋感觉太难为人
回复 支持 反对

使用道具 举报

 楼主| yoo 发表于 2016-6-22 08:12:59 | 显示全部楼层
blackrose 发表于 2016-6-22 03:28. 鍥磋鎴戜滑@1point 3 acres
你是说第二次面试 数组转圈的算法题? 那个就是一个两个指针swap 吧。swap(nums, nums[nums]) 如果nums ==  ...

我觉得原贴里Heliuhun给的方案是对的,你的解法我不明白原理,好像不对哦。。

跳转序列可以拆成几个独立的环,同时也知道每个环的长度,然后求所有环长度的最小公倍数?比如[1,0,4,2,3]就是0-1-0 和 2-3-4-2两个环,所以6次shuffle后变回原来的数组
回复 支持 反对

使用道具 举报

dg7743 发表于 2016-6-22 12:38:31 | 显示全部楼层
楼主我在我这个帖子里面经/LintCode/LeetCode题目想法和代码分享的13楼写了LFU的分析,21楼写了我自己对于Battleship的设计,以及Heliuhun方案的分析。
回复 支持 反对

使用道具 举报

frederickyl 发表于 2016-6-22 12:49:42 | 显示全部楼层
I am confused with your answer. The popularity cache mentioned by you is actually a LRU cache. Its replacing strategy is the hit times of a photo. I think this problem is somehow related to the CDN architecture. You can read some papers that introduces Akamai or Facebook TAO.
回复 支持 反对

使用道具 举报

 楼主| yoo 发表于 2016-6-22 13:06:23 | 显示全部楼层
frederickyl 发表于 2016-6-22 12:49
I am confused with your answer. The popularity cache mentioned by you is actually a LRU cache. Its r ...

本科毕业工作了一年,确实没有接触过这方面的知识。。
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-6-28 18:19:09 | 显示全部楼层
缓存那题,google跟你说的业务需求是什么?.鏈枃鍘熷垱鑷1point3acres璁哄潧
如果即要访问次数多的,又要最近访问的,那搞两个缓存行么?
回复 支持 反对

使用道具 举报

 楼主| yoo 发表于 2016-6-30 14:03:19 | 显示全部楼层
adrian_yang84 发表于 2016-6-28 18:19
缓存那题,google跟你说的业务需求是什么?
如果即要访问次数多的,又要最近访问的,那搞两个缓存行么?

就是快速访问图片,不需要考虑修改图片。
我用了两个缓存,但是最后feed back不好,跪了。
回复 支持 反对

使用道具 举报

Thunder_up 发表于 2016-7-1 05:06:34 | 显示全部楼层
缓存算法里有LRU-K(LRU其实是 LRU-1)。LRU-K需要多维护一个队列,record所有缓存数据被访问的历史。更复杂的貌似还有multi queue(MQ)算法。这题感觉还是偏向于问算法啊。。
回复 支持 反对

使用道具 举报

phantom 发表于 2016-7-1 05:16:16 | 显示全部楼层
话说。。设计题他是不是想和你聊CDN的东西啊?
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-7-1 05:17:15 | 显示全部楼层
系统设计题 要写代码吗?.鐣欏璁哄潧-涓浜-涓夊垎鍦
回复 支持 反对

使用道具 举报

adrian_yang84 发表于 2016-7-1 18:13:20 | 显示全部楼层
嗯。业务需求的话,比如访问里,各种类型的分布如何?多少访问是访问最新的,多少是访问经常访问的,多少是访问很少访问的。另外,cache还有命不中的问题。命不中的话,接受多少的延迟呢。等等。
可能先多问问业务需求好一点。然后根据他的需求,做具体的取舍。他要求严的地方,就重点关注,要求松的地方,就牺牲一点。

这是我的理解。
回复 支持 反对

使用道具 举报

 楼主| yoo 发表于 2016-7-4 09:19:41 | 显示全部楼层
phantom 发表于 2016-7-1 05:16
话说。。设计题他是不是想和你聊CDN的东西啊?
. visit 1point3acres.com for more.
不是,先问了我想聊CDN方面的还是Cache方面的,我选了Cache
回复 支持 反对

使用道具 举报

 楼主| yoo 发表于 2016-7-4 09:20:27 | 显示全部楼层
陈润鹏 发表于 2016-7-1 05:17
系统设计题 要写代码吗?

写了,我写的是LRU加上自己蒙的popular cache那部分
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 08:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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