一亩三分地论坛

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

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

Google onsite

[复制链接] |试试Instant~ |关注本帖
chs5003 发表于 2016-11-21 12:05:28 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
9月30号在西雅图面的,本来应该早点发的,但是由于种种原因耽误了,现在发上来也算是攒攒人品吧,今年运气一直不算太好。. from: 1point3acres.com/bbs
一共五轮,可以用白板,准确地说是一面白墙,也可以用chromebook.我基本上都是在chromebook上写的,因为我感觉打字要快多了。于是每一轮面试官都把我给的答案发送到他们的邮箱里了,估计是事后比较方便验证吧。
第一轮,英国人,LC418, 当时给了个O(mn)的解法,后来follow up他说要是m, n 都比较大怎么办,然后我给了个O(m)的解法。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

第二轮,美国小哥,第一题问了一个数据结构的题,把一个某种格式的inputstream,利用你设计的数据结构转换成另外一种形式并输出,算法上很简单。我implement完后他看了一下也没有提什么问题就直接复制发送到了他邮箱。第二题问了H-index,秒掉之后他验证了几个edge case, 找不出问题后 follow up 问算法复杂度多少,我说O(n), 然后他follow up说如果citation 如果本来已经排好序的话怎么做,我说可以用binary search。

第三轮,应该挂在这一轮了,美国小哥,pull char to head, 给两个String anagrams, str1 和 str2,每次只能把str2里的某一个char移到最前面,问最少需要几次这样的操作。比如给的String是 “anagram"和“naagram”,可以把第二个String的第二个‘a’移到最前面,最少操作是1. 我当时给了个BFS的解法,然后感觉他不满意,说是不需要每一种情况都要go through一遍。后来想问他给点提示,但是他和我打太极,说他也不确定。

第四轮,不太确定是哪个国家的,应该是混血,第一题要设计一个list iterator,记得比较清楚的是比如给一个list, 是{1,2,3,4}的话,iterator 给的输出应该是 2,4,4,4意即奇数位表示偶数位的value要重复的次数,input list不一定valid,要handle各种Exception。第二题也是一个设计题,要判断一个人(node)是否能access一个file, 这个node有两个member,一个是userId, 另外一个是他能access的file的list,但每一个file可能也包含多个其他file。给出思路后没有让实现,然后问了他几个问题就结束了。

第五轮,美国小哥,LC317 变种题,敲代码的过程中大脑一抽把visit过后的点的visit[i][j]写成了false, 被他指出来了,敲完答案和和他一起过了一遍,没有发现问题然后他问了下复杂度,然后复制发到他邮箱了。

面完后的第二周周四HR打来电话,说是有一些Strong data但是feedback的discrepanycy比较大,决定不送HC。HR之前邮件说他会在我onsite的时候和我见面,但是直到面完也没有看见过他,这也是让我有一点小意外吧。

其实整个面试的体验还是不错的,报销的速度也相当迅速。

. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

1

查看全部评分

本帖被以下淘专辑推荐:

catinclay 发表于 2016-11-21 14:05:23 | 显示全部楼层

想了一下 应该是Longest Consecutive Sequence的变形
找str1里面最长的suffix使得在str2中有最长的Sequence
例如str1 = "abcdefg"
str2 = "eafbgcd"
str1最长的suffx且是str2的sequence的是"efg", 次数就是str.length - 3 = 4
实际上的做法就双指针从str1根str2的尾端往回扫就好了 时间复杂度是O(n)

如果直接找Longest Consecutive Sequence的话会因为你只能移动str2导致结果错误-google 1point3acres
用上面当例子, Longest Consecutive Sequence是"abcd", 得到结果为length - 4 = 3, 但3次移动是没办法让两string相等的. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

. 1point 3acres 璁哄潧
回复 支持 2 反对 0

使用道具 举报

dummyprogrammer 发表于 2016-11-21 13:12:05 | 显示全部楼层
第三題我也先想到可以bfs,後來仔細想一下,好像可以先判斷str2中,擁有最長的str1尾端的字串。例如anagram, gramana,那就是str2裡的gram。然後再一個一個把剩下的字都往前推。在推的時候,如果會額外產生match的字串,就要扣掉次數。例如aabaaaa, aaaabaa,str2的b往前移動之後,就會產生額外的matching字串,那就要扣掉那兩個aa的移動次數。每移動一個字的時候,都會增加1個或0個matching字串,但可以都視為增加一個matching字串,因為遲早會增加回來。例如像agagram, ngramaa,matching字串要到移動最後一個a的時候才會一次加三,但遲早都會加回來的。

补充内容 (2016-11-21 13:19):
bfs的話會有O(n!)的time complexity,如果是一個一個移動的話,就是O(n^2)
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 13:20:39 | 显示全部楼层
第三轮的问题
首先, 可以把str1跟str2的common suffix给删除掉
然后每次把最后一个char放到头 等到有common suffix之后再删除掉 直到两个str都变成空字串

不确定是不是最佳解....鐣欏璁哄潧-涓浜-涓夊垎鍦

补充内容 (2016-11-21 13:25):
是錯的..請忽略

补充内容 (2016-11-22 00:05):
發了另一個解法在其他樓 不知道那個方法是不是對的
回复 支持 反对

使用道具 举报

3d596d24 发表于 2016-11-21 13:30:43 | 显示全部楼层
第三轮我觉得是找 Longest Consecutive Sequence
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-21 13:44:41 | 显示全部楼层
3d596d24 发表于 2016-11-21 13:30
第三轮我觉得是找 Longest Consecutive Sequence

貌似是對的..
回复 支持 反对

使用道具 举报

幻灭天神 发表于 2016-11-21 14:16:23 | 显示全部楼层
G家的面试都是上来就coding吗?有没有啥project deep dive或者behavior questions?
回复 支持 反对

使用道具 举报

 楼主| chs5003 发表于 2016-11-21 23:14:55 | 显示全部楼层
catinclay 发表于 2016-11-21 14:05 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
想了一下 应该是Longest Consecutive Sequence的变形
找str1里面最长的suffix使得在str2中有最长的Seque ...
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我觉得你的解法是对的。我当时是怎么也想不到可以用suffix去找match,看来我还是道行不够啊。
回复 支持 反对

使用道具 举报

 楼主| chs5003 发表于 2016-11-21 23:17:27 | 显示全部楼层
幻灭天神 发表于 2016-11-21 14:16
G家的面试都是上来就coding吗?有没有啥project deep dive或者behavior questions?

没有问过我什么behavior questions。基本都是一上来他们自我介绍,最后结束前几分钟让你问他们问题,这一部分加起来大概10分钟吧。但是不同的人可能做法也不太一样,都要有心理准备吧。
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-11-21 23:43:37 | 显示全部楼层
chs5003 发表于 2016-11-21 23:14.1point3acres缃
我觉得你的解法是对的。我当时是怎么也想不到可以用suffix去找match,看来我还是道行不够啊。

那一楼的解法是不对的。。
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-11-21 23:44:02 | 显示全部楼层
3d596d24 发表于 2016-11-21 13:30
第三轮我觉得是找 Longest Consecutive Sequence

请问可以举一个例子说明一下嘛
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-22 00:03:56 | 显示全部楼层
pawprinter 发表于 2016-11-21 23:43. Waral 鍗氬鏈夋洿澶氭枃绔,
那一楼的解法是不对的。。
. 1point3acres.com/bbs
請問有反例嗎?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-11-22 00:12:57 | 显示全部楼层

抱歉回复错了,我说的是一开始说的解法,后面的解法感觉是对的. more info on 1point3acres.com
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-22 00:41:08 | 显示全部楼层
楼主能不能说一下第三轮跟第四轮, 题有点没明白

补充内容 (2016-11-22 04:51):
说错了是第四轮那两题
回复 支持 反对

使用道具 举报

shiningdong 发表于 2016-11-22 01:14:16 | 显示全部楼层

我也觉得不对,例如anagram和nagaram,两个字符串从头开始扫,common prefix是a…而答案是1
回复 支持 反对

使用道具 举报

catinclay 发表于 2016-11-22 03:09:18 | 显示全部楼层
shiningdong 发表于 2016-11-22 01:14
我也觉得不对,例如anagram和nagaram,两个字符串从头开始扫,common prefix是a…而答案是1

可以看一下我貼的另一個解 對於anagram和nagaram, str1的suffix在str2中的longest sequence是agaram, 所以答案是"anagram".length - "agaram".length = 1
回复 支持 反对

使用道具 举报

xiaoxiao0801 发表于 2016-11-22 03:27:09 | 显示全部楼层
第三题 向前移动一个位置的cost算1 还是无论向前移几个位置的cost都算1?可以用longest common subsequence解吗
回复 支持 反对

使用道具 举报

 楼主| chs5003 发表于 2016-11-22 03:42:44 | 显示全部楼层
xiaoxiao0801 发表于 2016-11-22 03:27
第三题 向前移动一个位置的cost算1 还是无论向前移几个位置的cost都算1?可以用longest common subsequence ...

选定要移动的char只能移到String的第一位,不管你从哪里移到第一位,都属于一次操作。
回复 支持 反对

使用道具 举报

shiningdong 发表于 2016-11-22 04:14:34 | 显示全部楼层
catinclay 发表于 2016-11-22 03:09
可以看一下我貼的另一個解 對於anagram和nagaram, str1的suffix在str2中的longest sequence是agaram, 所 ...
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
sry,我没注意到题目是只能移到最左端,个人觉得这个方法是对的
回复 支持 反对

使用道具 举报

新宿车站 发表于 2016-11-24 14:25:20 | 显示全部楼层
求问LZ能详细讲讲第4轮的题目么?没太明白意思
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 19:38

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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