一亩三分地论坛

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

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

谷歌6/21电面面经

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

2016(7-9月) 码农类 硕士 全职@Google - 猎头 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
今天下午刚面完了,感觉要跪了,其实是很简单的题……面试官是国人大哥,听口气完全是老司机,说话还挺快,但是还算清楚。
这是我开始找工作以来第一次面试……就献给了Google………………

他迟到了五分钟,然后开始后直接扔题(只做了一道题

有两个人A和B 已知两个人的schedule比如

scheduleA [0,10] [7,20], [26,28],[30,33]
scheduleB [0,5] [8,13],[27,30]

让你给A和B安排一个持续时间为time的meeting,求meeting可以开始的最早的时间。A和B的schedule已经是有序的(按开始时间排序)

schedule的区间是他们busy的时间,所以要找gap

我的想法是 A 和B 分别 merge,然后再找gap 怎么找gap没怎么想清楚,然后我说先分别merge,然后再汇合到一个数组里再merge。他说可以啊。然后我就开始写。写完了之后他说你反复merge,我说那我可以把两步并做一步,一边汇合一边merge,就像merge two sorted list一样,这样总时间是O(m+n),m和n分别是A和B的区间数。但是我当时脑子有点发热,merge的时候条件写的不对……

后来经面试官提醒 才知道原来他想直接把两个接一块然后再sort 然后再merge.然后再找gap

这样就是O(NlogN) N=m+n了 写起来也简单

写完了就剩10分钟了 其实可以说 我把以前那个再写完吧……但是他就问我有什么问题了 我就问了几个问题。。然后就结束了

只不过我一上来根本没想要sort 因为已经是sorted的了……就想直接写个O(N)的…………感觉NlogN这个是他想考我的第一个 然后再优化到O(N)
-google 1point3acres
还是有点着急,有点好高骛远。大家吸取教训。和面试官交流也不错,面试官人很好,这么折腾也没显示出任何不耐心。就是我太紧张了,毕竟第一次……


Move On了 估计没什么好结果。. 1point 3acres 璁哄潧


补充内容 (2016-6-22 11:18):.1point3acres缃
给的例子如果 要安排 一个5分钟的meeting 那输出就是20

补充内容 (2016-6-24 02:09):
刚接到recruiter电话,拿到onsite了!

评分

2

查看全部评分

mdyuki1016 发表于 2016-6-22 12:48:16 | 显示全部楼层
我感觉 merge 可以做到 On, 就和merge 2 sortedlist 一样
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-6-22 12:49:32 | 显示全部楼层
mdyuki1016 发表于 2016-6-22 12:48
我感觉 merge 可以做到 On, 就和merge 2 sortedlist 一样

是的 可以做到 只不过我写到中间的时候 出现了一点问题 然后正在思考的时候 面试官说 我们换个思路…………
回复 支持 反对

使用道具 举报

mdyuki1016 发表于 2016-6-22 12:49:52 | 显示全部楼层
感觉 楼主的 o(m+n) 比面试官的sort solutiuon 还要好啊
回复 支持 反对

使用道具 举报

 楼主| jjustc 发表于 2016-6-22 12:51:16 | 显示全部楼层
mdyuki1016 发表于 2016-6-22 12:49
感觉 楼主的 o(m+n) 比面试官的sort solutiuon 还要好啊

是啊 只不过写之前没有完全想清楚后面条件怎么写 然后写的时候就卡了一会儿 想了一分钟大概 然后面试官就要把我的思路往他那上面引了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 23:30

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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