传说中的谷歌招聘委员会成员之一,从幕后走出来,教你学系统设计!


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 543|回复: 2
收起左侧

zenefits 昂赛特

[复制链接] |试试Instant~ |关注本帖
洋葱头 发表于 2017-7-17 14:21:12 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 硕士 全职@ - 网上海投 - Onsite |Fail在职跳槽

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

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

x


第一轮,
被要求设计一个哈希-google 1point3acres
给了4G的内存,所需要储存的是int类型,而且数字的范围是(1~500M)。不要考虑什么LRU LFU之类的。
insert/erase/erase_all 都是常数的时间复杂度。

考虑到给出的size 和 给出的可用内存。我决定使用vector<int>来做。
这里关键是erase_all的时间复杂度没办法满足。我就用了两个vector<int> v1 v2。每个是500M*4 = 2G。 两个刚好4G。
这样做的好目的是,当需要执行erase_all的时候,就可以通过一个异步的thread去对当前使用的vector进行erase all。(不过这里需要多出一个flag来表示当前使用的是哪一个vector。)
而且这里存在一个问题,就是下面的情况:
erase_all(v1)
erase_all(v2)
insert(v1)
如果这时候v1的erase_all还没有结束,就会出现race condition。所以这里还需要mutex。而这种情况下erase_all的时间复杂度也不再能看成是常熟。
这里我还考虑使用bitset,不过C++的bitset reset我不确定是否是O(1)的复杂度。
请大神指教

第二轮.鏈枃鍘熷垱鑷1point3acres璁哄潧
问题很简单,就是一个在matrix中做搜索的问题。DFS BFS都可以。不过被要求使用BFS。

第三轮
系统设计 优步
最后要求对整个系统的时间复杂度进行分析。

第四轮
系统设计 multiplayer 贪吃蛇. 1point 3acres 璁哄潧
关键点是整个 game board要分成多个区域,每个区域通过一个thread handle。不过boundary的部分怎么处理我还是没想到。。。
请大神指教!


总体来说面试难度还好。不过因为还没开始准备系统设计,所以挂掉也是自己的问题。

总体感觉,公司内部工作环境还好。提醒一点,貌似他们都是使用python,所以上面之所以被要求写BFS,是因为对方熟悉这道题python BFS的写法。
而且最后对方也对我C++的coding style 提出了异议,然后给出了我python的写法。。。

总之,网上对这家公司pay的介绍还蛮好的。建议还是好好面,然后去compete其他家。. Waral 鍗氬鏈夋洿澶氭枃绔,

各位加油,如果有没有阐述清的请包涵。有问题请留言。




. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


ykwwind 发表于 2017-7-17 14:59:30 | 显示全部楼层
第一轮是不是个烙印啊.....鐣欏璁哄潧-涓浜-涓夊垎鍦
我当年被问过这个.
回复 支持 反对

使用道具 举报

 楼主| 洋葱头 发表于 2017-7-23 07:15:36 | 显示全部楼层
ykwwind 发表于 2017-7-17 14:59
第一轮是不是个烙印啊....
我当年被问过这个.

是的 看来他们的题库就这么大, 以后要面的要注意啦 哈哈 加油
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-9-25 19:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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