📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 18
跳转到指定楼层
上一主题 下一主题
收起左侧

新鲜古果柯克兰大概率挂经

全局:

2019(4-6月) 码农类General 硕士 全职@google - 内推 - Onsite  | | Other | 在职跳槽

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
运气不好,面试前一天病倒了,卧床不起,直到面试当天凌晨4点还在头痛。
早晨起来虽然好多了,但还是有点点头痛,只能小声说话,感觉很虚。
然而还是决定去面试,因为本来也对古果没有情结,挂了就算了,尽力就好。

三轮coding,一轮bq,一轮design
[hide=80]
第一轮:一道 hard
悲剧啊,一上来就碰到难题,而且身体还有点sick,声音小,有一两个瞬间还恶心想吐,以至于讲话的时候interviewer说听不清。。
题目是一个社交网络里,每个人可以like多个其他人,like是单向关系。给两个人的node,求两个人直接或间接like同一个人的最短距离是多少。
例如:X -> A -> C -> D, Y -> B -> E -> F -> D, X和Y之间的最短距离是3+4 == 7。注意每个人都可以like多个人,这里为了简化只画了一条path。
最brute force的方法就是从X开始BFS整个网络,查一下每个访问到的人是否能被Y reach到。但是没有给出网络整体,只给了X和Y两个人的node,所以网络是非常大的,这个方法不可行。
然后各种瞎扯没思路,interviewer给了hint,说对X BFS,每层都看看访问到的人是否在对Y BFS访问过的人里。于是想出对X和Y一起一层一层的BFS,记录X和Y各自访问过的人和相应的距离(BFS层数),如果X当前访问的人在Y曾经访问过的人里,就返回当前访问的层数+此人和Y之前的距离。
Interviewer给了个反例:X -> A -> C -> D, Y -> B -> E -> F -> D -> A,如果用上述算法返回的是7,但最短距离应该是6(Y和A距离5,X和A距离1)。想了一会答,在D那里得到距离7以后,如果有更短的路径,那么BFS的层数肯定< 7,所以只要一直update 当前最短距离,BFS的loop直到当前层数 == 当前最短距离时终止。
Interviewer点头,又说我的code里好多不同的distance变量,实际不需要那么多,因为对X和Y BFS的层数是一样的。删了冗余变量,没时间改完全部代码,就结束了。
感觉答得不好,因为开始时问面试官有一题还是两题,面试官说it depends,说不定还有
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
答先统计图片访问量,把popular的放在一个cache,其他放在default cache,popular的每天根据历史记录算一下,如果图片访问率在所有图片访问里超过某个阈值就放在popular里。问如何设这个阈值,答看下cumulative ratio取80%,因为80/20定律。面试官说那个是social media的分布,我们这个可能不是那样分布。面试官的意思是根据cache的capacity,将访问率从高到低排序,然后尽可能塞进cache里,不需要计算阈值。
再问bottle neck在哪,答latency。需要globally部署web server和cache。问假设全球只有一台server,SLA的latency是1秒,问处理10k QPS需要多少台web server。我答不上来,他提示说一台server每秒钟不会只处理一个request,我想到用多线程,每个线程可以处理不同的任务,例如解析request,访问cache,访问blob storage等。
然后时间到了就结束了。感觉这轮面得一般。
[/hide=80]

总体感觉要挂就挂在第一轮了,摊手。之前没怎么看面经,因为感觉看了也没用,一半以上题是面试官自己想的……

希望大家都好好准备(主要还是理解),尤其要调整好状态,保证精神充沛地去面试啊~

评分

参与人数 14大米 +52 收起 理由
snznedta + 2 很有用的信息!
水鬼田 + 2 给你点个赞!
江城渔翁 + 1 给你点个赞!
阿满 + 1 很有用的信息!
geyu625 + 2 很有用的信息!

查看全部评分


上一篇:亚麻校招OA2
下一篇:Houzz 昂赛 跪经 (求大米,求利口题号)

本帖被以下淘专辑推荐:

推荐
tinlittle 2019-4-27 11:52:36 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
 楼主| bluesilence 2019-4-27 11:07:57 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

推荐
nlackx 2019-4-29 07:34:44 | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
sinopeter84 2019-4-27 11:29:14 | 只看该作者
全局:
谢谢,我下周同一地点。

补充内容 (2019-4-27 11:29):
祝楼主好运
回复

使用道具 举报

🔗
 楼主| bluesilence 2019-4-27 11:34:15 来自APP | 只看该作者
全局:
sinopeter84 发表于 2019/04/27 11:29:14
谢谢,我下周同一地点。

补充内容 (2019-4-27 11:29):
祝楼主好运

谢谢,也祝你好运!
回复

使用道具 举报

🔗
 楼主| bluesilence 2019-4-27 11:55:24 来自APP | 只看该作者
全局:
您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
回复

使用道具 举报

🔗
tinlittle 2019-4-27 12:08:17 | 只看该作者
全局:
bluesilence 发表于 2019-4-26 20:55
Set不是为了去重,是为了O(1)时间check边长k是否已经见过

set去重有歧义。我是口误,本来应该说用set避免重复是没有必要的。用set对原始输入数组去重倒是可以的,但要先给个数学证明去重不影响结果。
回复

使用道具 举报

🔗
 楼主| bluesilence 2019-4-27 12:09:36 来自APP | 只看该作者
全局:
tinlittle 发表于 2019/04/27 12:08:17


set去重有歧义。我是口误,本来应该说用set避免重复是没有必要的。用set对原始输入数组去重倒是可以的,但要先给个数学证明去重不影响结果。

面试官说假设input数组没有dup
回复

使用道具 举报

🔗
tinlittle 2019-4-27 12:12:04 | 只看该作者
全局:
bluesilence 发表于 2019-4-26 21:09
面试官说假设input数组没有dup

了解,那你就更不该用set检测边有没有用过了。面试官没有follow-up吗?
回复

使用道具 举报

🔗
 楼主| bluesilence 2019-4-27 12:18:20 来自APP | 只看该作者
全局:
tinlittle 发表于 2019/04/27 12:12:04


了解,那你就更不该用set检测边有没有用过了。面试官没有follow-up吗?

我的意思是只scan两条边,看能组成直角的第三条边是否存在,因为假定第三条边是最短的那条,所以只要在已经见过的set里查就行了
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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