一亩三分地论坛

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

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

Google 电面 + Onsite面经

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

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

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

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

x
美国西北角的那个城市的office,非MTV。

电面,一个小时,阿三面试官,非常nice。
Word Square:
A B C D
B N R T. more info on 1point3acres.com
C R M Y
D T Y E
. 1point 3acres 璁哄潧
Word Square的定义是,任取0<=k<n(长/宽),第k行和第k列的字符组成的字符串是一样的,比如第一行ABCD和第一列ABCD,是一样的。

除此之外,以下这种情况也是valid的。
A B C D
B N R T
C R M.鐣欏璁哄潧-涓浜-涓夊垎鍦
D T

先写一下假设你要写一个函数判断给定的输入是不是WS你会怎么写test case
然后,给一个list of 字符串,给一个length,求长宽为length的所有valid的word square,以list of list of 字符串的形式返回。
我是用backtracking/DFS的方法做的。. From 1point 3acres bbs

. 1point3acres.com/bbs最后分析一下复杂度。我的方法是n!,估计有更好的,但是后来结果还是pass了。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.


很快收到了onsite邀请。这个office部门以白人和国人为主,很少有三哥。

第一轮. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
LC的抢劫犯第一题和第二题。做完以后还有半小时。
接着是一个设计一个游戏算法,不需要写code。游戏是让用户猜单词。
一开始屏幕会显示一串下划线,代表这个词有多长,比如是 _ _ _ (假设答案是DAD的话)
玩家输入'E',屏幕会显示 _ _ _
玩家输入'D', 屏幕会显示D _ D
玩家有一个尝试次数的上限。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
现在要设计的算法是,这个词库,给定的是有限的(假设长度是一样的),计算机想要cheat,就是一开始这个词其实并没有确定,而是根据玩家输入的字符进行动态调整,目的是让玩家输,怎样去设计这个算法,同时保证不会让玩家发现程序在cheat(也就是每次程序返回的结果都是valid的)。这题面试官也只想让我聊一聊,基本的思路就是根据现有词库里的单词里的字符的组成,结合用户的输入,尽可能保住多的词库吧,用一点简单的概率,我没给出最后的完整算法,本来时间也不多了。

第二轮
LC 340
这题虽然是hard难度,其实思路很简单,代码量也不大。我是用类似multiset的思路,1 pass。不过面试官不熟悉C++,白板上code也不好看,花了挺多时间解释和走test case,面试官后来终于理解了。. 1point3acres.com/bbs
Follow up:
如果这个string是一个输入流,string非常大,内存里放不下怎么办。我扯了一些,最后没给出一个让面试官满意的方法。不过面试官最后也说觉得已经很不错了。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
. more info on 1point3acres.com
第三轮:
LC 391. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我今天写面经的时候刚刚出现的题,目前2290提交160个AC的hard题。当时真的把我难住了。面试官说他是第二次问这个问题。. Waral 鍗氬鏈夋洿澶氭枃绔,
我给的方法是,首先找所有矩阵的最左上角,最右上角,最右下角和最左下角的点,求这个面积,然后sum up所有小矩阵面积,两者必须相等。这一步很简单。
在满足以上条件下,先按照每个矩阵的垂直边X轴坐标排序,track当前矩阵的左边和右边沿,每个矩阵往上加的时候必须刚好贴在左边沿或者右边沿。这样做两次,一次正序,一次逆序。
同理,对水平边Y轴也做一次。
面试官心中的解法不是如此,但是也举不出一个bad example。我自己也无法证明自己。这一轮估计没让我过。

第四轮:
给一堆用户信息,含有名字,邮箱地址和号码,要求把重复的用户成组地返回。重复的定义是,名字,邮箱和电话号码三者有一个相同就是重复的。
这道题后来经过面试官提醒了一下,是一个图的连接问题。
每个用户信息可以视作一个node,首先通过重复定义,可以得到一堆edge,这些edge把一些用户连接起来。我们最后要返回的就是所有内部node数量大于1的小graph。
代码量比较大,最后有个bug来不及了,跟面试官说了一下union find的算法。
. more info on 1point3acres.com
第五轮:
LC 108。2分钟秒过了。面试官半开玩笑地说,你不应该做这么快。
然后是一道迷宫题。. from: 1point3acres.com/bbs
假设你在一个迷宫里,你不知道迷宫大小,不知道自己方向。你只有以下3个API函数可以调用:
1. 检查是不是已经到了出口. visit 1point3acres.com for more.
2. 往前move一格(返回true表示成功move,返回false表示失败,不能移动,即撞墙)
3. 原地向左转90度。-google 1point3acres
要求写个函数把这个迷宫走出去。假设迷宫本身没有loop。
正常情况来说楼主应该是可以顺利做出来的,无非就是DFS,唯一要小心的就是不要走圈子,或者说走回头路。但是那天生病了,特别不舒服,最后一轮了体力不行了。面试官说我very close,但真的没精力去检查最后那个小BUG了。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
吐槽一下
G提供的酒店非常糟糕,楼下是工地,很吵,房间能听到隔壁打电话看电视。面试当天楼主生病了,长途跋涉又有时差,身体极其不舒服,几乎站不住,真的也是运气不好。

.鐣欏璁哄潧-涓浜-涓夊垎鍦


评分

5

查看全部评分

本帖被以下淘专辑推荐:

edyyy 发表于 2016-8-29 01:30:27 | 显示全部楼层
楼主看起来其实你面的不错,不一定要所有题都做的全队的
祝好运
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-29 01:55:21 | 显示全部楼层
edyyy 发表于 2016-8-29 01:30
楼主看起来其实你面的不错,不一定要所有题都做的全队的
祝好运

感谢安慰,已跪
回复 支持 反对

使用道具 举报

pushazhiniao 发表于 2016-8-29 04:25:29 | 显示全部楼层
楼主 想请问一下是哪家酒店呀
回复 支持 反对

使用道具 举报

lzb700m 发表于 2016-8-29 04:27:16 | 显示全部楼层
我在想,他们挂你的原因是不是因为你题目秒的太快了啊。
回复 支持 反对

使用道具 举报

lvvvvv 发表于 2016-8-29 07:12:39 | 显示全部楼层
第三轮: 能不能这样

先求各自面积, sum ,  必须等于最左下到最右上 的面积, 这是第一个条件。 (如果找不到最左下,最右上, 则必然不是矩阵)

然后 sweep line x 轴 查有没有交集就行了吧 ?
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-29 07:23:38 | 显示全部楼层
pushazhiniao 发表于 2016-8-29 04:25. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主 想请问一下是哪家酒店呀

The HXXXXXXX HOTEL
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-29 07:25:07 | 显示全部楼层
lvvvvv 发表于 2016-8-29 07:12
第三轮: 能不能这样

先求各自面积, sum ,  必须等于最左下到最右上 的面积, 这是第一个条件。 (如 ...

因为在LC上已经出现这道题,你大可以试一下~我过阵子去做这题。
回复 支持 反对

使用道具 举报

bcc 发表于 2016-8-29 07:38:52 | 显示全部楼层
google真的好难哦,请问lz第一轮follow up 怎么整啊?
回复 支持 反对

使用道具 举报

mren 发表于 2016-8-29 09:40:13 | 显示全部楼层
楼主确实运气不好, 第三题先求面积是否相等, 然后再查是否有重叠, 目前查重叠我是O(n^2), 大数据过不掉, 如果要求O(n)完成确实不容易
回复 支持 反对

使用道具 举报

lingeast 发表于 2016-8-29 15:26:49 | 显示全部楼层
感觉楼主真的已经面得很好了,每一轮都能做好几道题目。BTW,我最近的Google电面面了一样的word square的题目。
回复 支持 反对

使用道具 举报

helloc93 发表于 2016-8-29 15:54:20 | 显示全部楼层
楼主onsite题有点难,遇到两道hard题,感觉391那题尤其难. 现在google onsite已经动不动就出hard题了么?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-29 21:47:01 | 显示全部楼层
LC391如果对时间复杂度没有要求的话可以两两查overlap,然后最后看sum of area是否=bounding box area
如果要求复杂度的话,也许他要的是sweep line或者2D range tree。如果口头说思路的话可以提,不过觉得bug free有点难。
下面这个做法是我当时做的,复杂度更低容易实现。但是我觉得思路太tricky了,不太可能40分钟里想到。我自己是在想了大约2小时以后想到的。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
https://discuss.leetcode.com/top ... tailed-explaination

补充内容 (2016-8-30 03:21):
后来自己写了一下sweepline发现其实想明白了也不太难...
虽然还是觉得何必要求人会计算几何的东西...
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-29 22:07:15 | 显示全部楼层
hxtang 发表于 2016-8-29 21:47. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
LC391如果对时间复杂度没有要求的话可以两两查overlap,然后最后看sum of area是否=bounding box area
如 ...

两两查overlap是比较straight forward,我当时真应该先用这个方法做的,我只是一味地感觉按边坐标排序一定可以得到一个n logn的方法,就没去说这个比较直接的N2方法。以后也会注意,不熟悉的题先求做对,再求效率。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-8-29 22:43:11 | 显示全部楼层
ladyM1896 发表于 2016-8-29 22:07
两两查overlap是比较straight forward,我当时真应该先用这个方法做的,我只是一味地感觉按边坐标排序一 ...

我后来想了一下,可能他要的就是你先说两两overlap那个方法。然后他就可以问你怎么避免O(n^2)的检查,然后你就可以提sweep line可以把速度改进到O(n log n)。

第二轮LC340那个题的最优解可以解决followup的,就是存每个字符最后一次出现的位置。把它们放在一个priority queue里。每次跳到最早的last occurrence后面就行了。这样占用的memory就和字母表一个数量级了。
回复 支持 反对

使用道具 举报

 楼主| ladyM1896 发表于 2016-8-30 03:23:16 | 显示全部楼层
hxtang 发表于 2016-8-29 22:43.鏈枃鍘熷垱鑷1point3acres璁哄潧
我后来想了一下,可能他要的就是你先说两两overlap那个方法。然后他就可以问你怎么避免O(n^2)的检查,然 ...

我看到LC上你的帖子了,你好厉害
回复 支持 反对

使用道具 举报

Catherine995 发表于 2016-8-30 04:50:03 | 显示全部楼层
我觉得你已经面得很好了,碰到的题目确实偏难,而且自己身体有不舒服. 谢谢你的分享!!!
回复 支持 反对

使用道具 举报

Tsien 发表于 2016-8-30 07:28:58 | 显示全部楼层
lingeast 发表于 2016-8-29 15:26
感觉楼主真的已经面得很好了,每一轮都能做好几道题目。BTW,我最近的Google电面面了一样的word square的题 ...

根据一些字符串产生所有有效的word square能不能给个例子?
有点不太明白==
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-8-30 09:23:00 | 显示全部楼层
第二轮的follow up感觉可以只存每个distinct character最开始出现的位置和最后出现的位置,这样内存开销就会小很多
回复 支持 反对

使用道具 举报

sniffsky 发表于 2016-8-30 09:31:07 | 显示全部楼层
楼主有碰到系统设计的题吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 19:15

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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