他家网站上自己投的简历
店面:面经里的巫师题10个巫师编号0-9,给定每个巫师认识的其它巫师,需要介绍0号和9号认识,每次介绍的费用是编号之差的平方,求最小费用
本来我说可以用Dijkstra对方说这个比较复杂,不需要最优,于是广度优先搜索解决
上门
1 & 2. Cross Functional
多数问题比较常规:给别人的批评,别人对你的批评,最得意的成就,身边的人中你认为谁会是一个好host为什么,其它的想不太起来了
问到why us的时候扯到了他家的experience和谷歌地图的区别,追问了几次为什么认为这两个产品不一样,略懵逼
-
设计:订阅系统
需要考虑如果停止订阅要从当前Feed中删除对应条目
先设计存储schema,不考虑具体数据库类型假设单机,然后问如何加速查询如何对每个table进行index,需不需要建多个,是否需要复合。
然后就是典型的NewsFeed套路了。特别问到了如果某个发布者有海量订阅者怎么办。 -
代码:倒水,利口其呜呜
和原题区别:一是上来先让写一个print的函数,写完主干再来改这个print函数,需要把水和地形分别表示;二是水流到边界会流出去(即边界上没有无限高的板)。其它一些细节比如先往那个方向自己决定。
代码都是自己电脑IDE写然后邮件发到指定邮箱。
因为有点区别写的稍微慢了点,最后写完了test case没过,面官表示『已经比绝大多数人好了』。回家后看了一眼发现只是有两行代码顺序反了,于是又发了个邮件说明了下。 -
设计:KV存储
问了好多好多最后都超时了……写一下还记得的吧,也不知道自己答的是不是靠谱
也是先说不要想多机器的情况先设计单机版本,内存快速存取且排序(说的跳表或treeset好像不太靠谱),内存满了dump到硬盘,dump的时候创建新表不block新进来的请求,内存存储对文件的index快速[定位]需要搜索的文件(忘了说boom filter了……),硬盘二分搜索,定期合并避免文件太多,更改删除元素直接append新元素,查询时先内存文件再倒时序查,多次更改删除后浪费空间-同一个key出现的文件数达到某一阈值后在下一次的非高峰时段进行文件合并每个key保留最近值。拓展到多机器,数据迁移一致性哈希,一致性哈希的查询表可以缓存在client端减轻master压力,上传文件时需要返回client完成信息-选择captain上传一由captain复制备份有一个备份传输完成则返回成功信息避免client等太久,保存不同replica的访问顺序避免复制完全结束前收到请求。 -
Experience
聊以前项目。后来听说这一轮主要是通过经验来判断一下给什么级别很少会刷人。 -
Coding:利口而流久
原题,先假设没有环,写完后,再加上有环的情况(返回个特殊值或者报错都行)。拓扑排序。要自己想几个测试数据。
说一般24小时最多72小时给结果,最后真的是刚刚好等了72小时给我打电话拒了……只说了是因为design signal not strong enough,也不肯说是哪一轮。
比较伤心,毕竟下了不少功夫刷他家那些个难题,面完也觉得都是见过的问题应该有戏。可能设计这种没有标准答案的还是变数大吧,下次找朋友mock几次可能会比较好。
感觉他们家比较好的策略就是在面经题目比较稳定的时候集中突击出现过的题目高度熟练然后靠押题取胜。这种难度的题目第一次见40分钟内(这么难他们还一定要留出5分钟问问题我也是服了)写出来还要过测试数据真心难。设计题目感觉要求也不低(也可能是我自我感觉良好了)。