一亩三分地论坛

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

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

google Pittsburgh奇葩跪经

[复制链接] |试试Instant~ |关注本帖
goulgold 发表于 2016-4-8 09:29:23 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Failfresh grad应届毕业生

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

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

x
非常不走运今天刚刚接到HR电话,告诉我svp review挂了,我看地里好像没有类似的case,我就分享一下经验,希望能帮助后面的同学

去年12月末找人内推,2月份HR联系我,先做了最新的code sample,一周之后安排电面

电面很简单,就略过了,大概一周后通知电面pass,安排三月末onsite,因为lz在Pittsburgh,就安排的Pittsburgh的office onsite。

可能是lz运气好,onsite的题都不难,lz用的C++:

第一轮:高频题 window average,不能用STL,所以要自己实现queue,follow up是多线程怎么办,加锁就可以

第二轮:一个tree是否包含另外一个tree,用recursive解的,然后就问问题了…… lz当时以为跪在这一轮了

第三轮:类似https://leetcode.com/problems/minimum-window-substring/ 只不过是两个vector<string>, 用sliding window. visit 1point3acres.com for more.

第四轮:第一题是https://leetcode.com/problems/lo ... g-path-in-a-matrix/ 的变形
  lz也是没经验,一看这题做过啊,刷刷刷就背完了……然后面试官看还是有时间,就又出来一道题:
有两个set的points, set A和set B,又给了一个double类型的参数delta,求set A里面每一个point最近的且距离小于delta的set B的point,有点绕,就是给一个point A,就返回一个最近的point B,并且这个距离要小于delta。
lz开始用的暴力解法,复杂度是O(n^2),后来想出来一个先排序再搜索,复杂度降为O(nlogn),三姐一直说interesting,我也不知道是好是坏……
. more info on 1point3acres.com
onsite之后三天,通知hc过了,送executive review,当时觉得很有希望拿下offer了,万万没想到啊,今天通知svp review挂了,问是什么原因也不说,lz心里有一万只草泥马跑过……

虽然没有拿到offer,但是整体看下来,google面试难度没有传说的那么变态,但是流程确实长,最后这个挂的有点无语,只能发个面经攒攒人品了

希望对小伙伴能有帮助,也祝地里的同学早日拿到心仪offer


. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
补充内容 (2016-4-30 04:19):
最后的一题解法见回复~

评分

2

查看全部评分

newbiee 发表于 2016-4-8 09:44:45 | 显示全部楼层
同学,请教下第四轮,怎么排序啊? 要对A里面每一个点最近,对B按照什么排序呢?
回复 支持 反对

使用道具 举报

kittycerry 发表于 2016-4-14 14:02:54 | 显示全部楼层
第四题,是不是可以这么做,seta, setb分别排序,然后,用两个pointer分别指向seta,setb的开头然后这样走一遍?
回复 支持 反对

使用道具 举报

x1957 发表于 2016-4-14 16:22:05 | 显示全部楼层
我去,还真有hc之后跪了的啊
回复 支持 反对

使用道具 举报

theocrasy 发表于 2016-4-14 21:09:55 | 显示全部楼层
你得问问啊 这就是死的不明不白啊 你连将来哪里要注意都不知道 难道是因为gpa太低?
回复 支持 反对

使用道具 举报

此用户无名 发表于 2016-4-27 13:22:30 | 显示全部楼层
一轮45min 正常应该做几道题?1还是2?
回复 支持 反对

使用道具 举报

zhengyino1 发表于 2016-4-27 13:59:45 | 显示全部楼层
我擦,我听说过挂svp的,svp都看啥?code?学历?GPA?
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-4-28 02:08:20 | 显示全部楼层
LZ请节哀但是我觉得LZ已经很厉害了
顺便想问一下 第四题 第二问 point怎么进行排序呀 排序和距离也没有关系呀
回复 支持 反对

使用道具 举报

 楼主| goulgold 发表于 2016-4-30 04:24:05 | 显示全部楼层
看到问最后一道题的比较多,我详细说一下我的解法,抛砖引玉~
两个集合A, B。A里面的点用a1, a2,...,ai表示,B里面的点用b1, b2,...,bj表示
第一步是把B里面的所有点,按照和a1的距离排序(复杂度是O(nlogn))
第二步是对于A里面的点,比如a2,先求a2到a1的距离,记为d, 然后在排好序的B集合里面,找[d-delta,d+delta]范围内的点,这一步可以用二分查找,所以复杂度是O(logn).
. from: 1point3acres.com/bbs
这个算法主要是利用三角不等式https://en.wikipedia.org/wiki/Triangle_inequality,画个图就很清楚了~
回复 支持 反对

使用道具 举报

陈润鹏 发表于 2016-4-30 06:13:49 | 显示全部楼层
goulgold 发表于 2016-4-30 04:24
看到问最后一道题的比较多,我详细说一下我的解法,抛砖引玉~. from: 1point3acres.com/bbs
两个集合A, B。A里面的点用a1, a2,...,ai表 ...

楼主 想法非常好
但是复杂度还是n^2 但是能优化
回复 支持 反对

使用道具 举报

杰西Jesse 发表于 2016-5-3 08:28:30 | 显示全部楼层
不知道可以用treemap来做么? 就是先A和B的point都按横坐标排序,然后把B的点都放到treemap里。。然后对于每个A就只要考虑|xb-xa| < delta的点,treemap选这些点的复杂度应该lgn....然后随着x越来越大,还可以将之前的一些点移除。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 23:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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