一亩三分地论坛

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

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

Google Onsite 11.23

[复制链接] |试试Instant~ |关注本帖
pigmightfly 发表于 2015-12-9 08:50:24 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
上周五hr通知说过了hc了,发一下面经攒攒人品!
第一轮
白人大叔
input:
G . . G
X . . .
. G . .
G是终点,.是可走的点,X是不可走的点
output:
求出每个可走的点到终点的最短距离(每一步可上/下/左/右一步). 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


我的做法是经典的BFS。先构造一个距离矩阵,所有G的点对应的是距离为0,其他点为MAX_INT。然后将G的点放入Queue中进行BFS,修改距离矩阵。

follow up:. visit 1point3acres.com for more.
如果每一步可走两步/三步怎么办?
如一步可走:左左,左上,右下,。。。
我说应该画出解空间树,然后DFS遍历解空间树,DFS的返回值是从该点出发最少需要几步到达一个G点。大叔说make sense。
. 鍥磋鎴戜滑@1point 3 acres
第二轮. more info on 1point3acres.com
白人Geek小哥
input:
string stream
如 abckdeghs...

有一个search list[google, ok, doit]
.1point3acres缃
output:
每当stream里的有字符串是在search list里的,就alarm clock

我想的是先用search list构造一个Tre
然后alarm clock的方法我参考了actor model里的actor send message。所以这个函数是没有返回值的,发现有匹配之后send message 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
函数的输入是一个叫StringStream的class,用next()函数得到它下一个char。并且string stream是不能回头的,不能通过坐标得到某个char
我给出的做法是每碰到一个合理的开头,就把之后的char都记下来。
比如,对于输入流为abcd..., search list: [abcb, bcd]. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
那么到d的时候会发现以a开头的不对,于是从存好的a后面的一个char即b开始重新遍历Tre,看是否可以满足。

第三轮
国人哥哥
lc: serialization and deserialization of binary tree
lc: sort colors

第四轮
国人哥哥
第一题:
input:
source string: abcde
target string: ebcda. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

要求:
对于target string,只能进行交换两个char的操作。如例子中,交换a和e,那么source string和target string之间差异距离就由2减到了0.
要求输出将差异距离减小到最小的一次交换的坐标,如例子,是输出[0,4]
source string和target string长度相等
我先开始是想的是用一个hashmap记录source string里每个char的位置,然后遍历target string时,看是否有对应的。
比如上面的例子,a是0,e是4。那么遍历target string时看e在map的坐标是多少,发现是4,然后看target下标为4的char是否是a,如果是,就说明这个交换可以将差异值减小2,输出。如果不是,那说明这个交换可以将差异值减小1。
但面试官提示说如果输入字符串里有大量重复数字,那么时间复杂度就不是线性的了。
于是想到可以用两个map,第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可以找到将差异值减小2的解,由第一个map可以找到将差异值减小1的解。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. visit 1point3acres.com for more.
第二题:
给出四个点的坐标,判断这四个点能否构成一个正方形。

关键在于四条边的关系。

一点感想:
Google onsite是我最紧张的一次onsite了。感觉中途代码写的不是bug free,不过面试官一直安慰我说他们看重的是思维。
觉得自己很幸运,遇到两个国人哥哥,真是非常谢谢他们!面试过程中可以感觉出来Google很看重思维的过程。整个过程中我都在和面试官不断的交流,每道题(除了第一轮)都拿出了2到3种方案,感觉他们对于这点还蛮满意的。
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 鍥磋鎴戜滑@1point 3 acres



补充内容 (2015-12-10 00:50):
大米啊~~

评分

6

查看全部评分

本帖被以下淘专辑推荐:

JohnsonMS 发表于 2015-12-19 03:58:25 | 显示全部楼层
第二题:
给出四个点的坐标,判断这四个点能否构成一个正方形。
. 1point 3acres 璁哄潧
关键在于四条边的关系。
****************************************************************
我的想法是: 计算出任以 两点的距离,共6个, 然后对距离排序, 如果前4个距离相等,后2个距离相等,可以认为是正方形

欢迎拍砖
回复 支持 2 反对 0

使用道具 举报

ssross 发表于 2015-12-9 10:13:32 | 显示全部楼层
LZ能再具体说一下“于是想到可以用两个map,第二个map是记录(s[i], t[i])这一对tuple的位置的。于是由第二个map可以找到将差异值减小2的解,由第一个map可以找到将差异值减小1的解。”
非常感谢!
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-9 11:58:20 | 显示全部楼层
ssross 发表于 2015-12-9 10:13
LZ能再具体说一下“于是想到可以用两个map,第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可 ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. map2 是这样的
(a,e): 0
(b,b): 1
(c,c): 2
...鏈枃鍘熷垱鑷1point3acres璁哄潧
那么每遍历到一个新的tuple,比如(e,a),就查一下(a,e)是否已在map2中,如果是,那说明存在这个交换使得差异值减少2.
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-9 12:00:09 | 显示全部楼层
ssross 发表于 2015-12-9 10:13
LZ能再具体说一下“于是想到可以用两个map,第二个map是记录(s, t)这一对tuple的位置的。于是由第二个map可 ...

map1 还是记录source string的char的位置
a: 0
b: 1
...
那么遍历target string的时候,比如第一个元素e,只要发现map1中存在e并且index不同,那么说明至少有一种交换是可以将差异值减少1的。
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-15 08:08:54 | 显示全部楼层
谢谢楼主分享~请问怎么怎么判断四个点能否构成正方形哈?首先要四条边长度相等,然后再判断四个夹角是不是90度嚒?
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-15 08:21:50 | 显示全部楼层
楼主可以说说等待的流程嘛..
onsite到送hc等了多久呢. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
然后hc等了多久呢
我上周2面完 现在feedback都还没拿齐 呜呜呜
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-15 08:34:06 | 显示全部楼层
xiaoniuona 发表于 2015-12-15 08:08 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
谢谢楼主分享~请问怎么怎么判断四个点能否构成正方形哈?首先要四条边长度相等,然后再判断四个夹角是不是 ...

单纯判断边的关系即可
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-15 08:35:04 | 显示全部楼层
randomusername 发表于 2015-12-15 08:21. Waral 鍗氬鏈夋洿澶氭枃绔,
楼主可以说说等待的流程嘛..
onsite到送hc等了多久呢
然后hc等了多久呢

我正好面试那周是感恩节,所以拖了一点时间。我从onsite到hc是等了两周,hc当天出的结果。
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-15 08:36:20 | 显示全部楼层
pigmightfly 发表于 2015-12-15 08:35
我正好面试那周是感恩节,所以拖了一点时间。我从onsite到hc是等了两周,hc当天出的结果。

两周这么久...敢问楼主是怎么熬过的...(会不会像我一样每半小时看一次邮件呢)
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-15 08:38:31 | 显示全部楼层
randomusername 发表于 2015-12-15 08:36
两周这么久...敢问楼主是怎么熬过的...(会不会像我一样每半小时看一次邮件呢)

. Waral 鍗氬鏈夋洿澶氭枃绔,我当时面完就知道结果不会出那么快(因为感恩节嘛),所以还好哈哈。。最后是要赶上我另一个offer的ddl,才和hr催了一下。你要是实在不安心,就问联系你的hr大概啥时候有结果吧
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-15 12:21:17 | 显示全部楼层
pigmightfly 发表于 2015-12-15 08:35
我正好面试那周是感恩节,所以拖了一点时间。我从onsite到hc是等了两周,hc当天出的结果。
. visit 1point3acres.com for more.
美女楼主 还有一个问题... onsite 到送进去hc等了多久呀!!
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-16 10:47:35 | 显示全部楼层
randomusername 发表于 2015-12-15 12:21
美女楼主 还有一个问题... onsite 到送进去hc等了多久呀!!

onsite完就是hr收集工程师feedback,这个过程有可能一周,有可能两周,还有可能更久。。收集完feedback之后,如果是positive,hr会把feedback送到hc。hc好像都是周五开的。过了hc之后,hr会把所有材料送到leadership team review。
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-16 12:15:50 | 显示全部楼层
pigmightfly 发表于 2015-12-16 10:47
onsite完就是hr收集工程师feedback,这个过程有可能一周,有可能两周,还有可能更久。。收集完feedback之 ...

我上年2天就收集完送hc了...现在已经一周没消息...等到下周又圣诞...当时又有2个engineers没take note只照了个相的... 到时忘了我了都。
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-17 03:28:52 | 显示全部楼层
randomusername 发表于 2015-12-16 12:15
我上年2天就收集完送hc了...现在已经一周没消息...等到下周又圣诞...当时又有2个engineers没take note只 ...
. 1point3acres.com/bbs
应该不会的吧。。。估计就是赶上圣诞大家无心工作了=。=
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-17 08:25:25 | 显示全部楼层
pigmightfly 发表于 2015-12-17 03:28
应该不会的吧。。。估计就是赶上圣诞大家无心工作了=。=

惨了呜呜呜呜啊啊啊
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-18 01:50:51 | 显示全部楼层
randomusername 发表于 2015-12-17 08:25
惨了呜呜呜呜啊啊啊

时间长不一定是坏消息啊。。Good luck!
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-18 07:52:24 | 显示全部楼层
pigmightfly 发表于 2015-12-18 01:50
时间长不一定是坏消息啊。。Good luck!
. 1point3acres.com/bbs
嗯嗯 我等等啦... 你什么时候入职呀
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-18 08:18:37 | 显示全部楼层
randomusername 发表于 2015-12-18 07:52
嗯嗯 我等等啦... 你什么时候入职呀

3月4号。。感觉好晚
回复 支持 反对

使用道具 举报

randomusername 发表于 2015-12-18 09:50:47 | 显示全部楼层
pigmightfly 发表于 2015-12-18 08:18
3月4号。。感觉好晚

哇。。。。是蛮久的.. 到时一起玩耍!
回复 支持 反对

使用道具 举报

 楼主| pigmightfly 发表于 2015-12-18 10:58:20 | 显示全部楼层
randomusername 发表于 2015-12-18 09:50
哇。。。。是蛮久的.. 到时一起玩耍!

好哇~
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 15:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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