一亩三分地论坛

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

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

gg全套

[复制链接] |试试Instant~ |关注本帖
hyperspace 发表于 2016-9-15 03:10:14 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Google - 内推 - 技术电面 Onsite 在线笔试 |Passfresh grad应届毕业生

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

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

x
今年6月份找人refer的。拿着别的offer使劲催终于在上周走完了全过程。借个别人的号来写一下我能想起来的题。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
但个人觉得gg的题库太大,而且一直在改动,面经的帮助远远不如小公司大。所以大家要面gg的话还是要基本功扎实才靠谱呀。

1. OA -> 看这个帖子~http://www.1point3acres.com/bbs/thread-193639-1-1.html
OA的题目一直都有些不同的题。但一般题都差不多,最多是求最大或最小这样的小区别。

2. tech phone interview
input一个string str,方法要求split str into elements,return符合要求的最大elements数量。。这题有点怪我来写几个例子:.鐣欏璁哄潧-涓浜-涓夊垎鍦
eg1. input: abab -》 return 2. visit 1point3acres.com for more.
         可以被分成 ab | ab, 这样子[ab][ab]是对称的;
         但是不能分成 a | b | a | b, 因为[a][a]不对称。
eg2.input: teammate -》 return 6
        可以被分成 te | a | m | m | a | te, [te][a][m][m][a][te]是对称的
eg3: input: ab -》 return 1
        [ab], 这直接是1
eg4: input: aaa -> reurn 3
       这个可以分成 a|a|a 或者直接不分: aaa。 但题目要求返回最大可能值,所以是3
eg5: 空字符串返回0

3.ONSITE [4轮 + 1 lunch]
(1) gas pipeline game
上我的手绘!!. 1point3acres.com/bbs
所以有这么些不同类型的管子:

管子们

管子们


然后我们有个网格要把这些管子放进去。设计游戏并且实现一个方法来检验:气体能否从左下进去,右上出去并且不泄漏。
比如这个就是true:
Screen Shot 2016-09-14 at 11.31.37 AM.png
这个就是false (画一半笔没水了。。):. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
Screen Shot 2016-09-14 at 11.31.42 AM.png
. From 1point 3acres bbs
.1point3acres缃
(2).这个题很简单,但是follow up和细节问题特。别。多。
input : a set of points S+ target point P+ integer k. visit 1point3acres.com for more.
return: k points selected from S, which are the closest to P
follow up就是说如果这个set特别特别大你要怎么办。有什么办法提高效率(用hashmap存一部分比较的结果)之类的。。再多我不太记得了。。

(3).给一个matrix,里面全都是integer,要求实现一个update方法和一个sum方法。
例子:
1 2 3
4 5 6. 1point3acres.com/bbs
7 8 9. visit 1point3acres.com for more.

update: 输入position和value 直接更新就行了。
比如(0,0),2:matrix变成
2 2 3
4 5 6
7 8 9. 1point3acres.com/bbs

sum:输入两个position 返回两个position定下的这个小matrix里面的元素的和。
比如 (1,1) (2,2)
返回
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴5 6
8 9
的和。
. more info on 1point3acres.com
要求两个方法都是O(n)。 -》 用到extra space
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
(4) 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
给一个string of strings,判断是不是一个word square:
比如[WALL][AREA][LEAD][LADY]就是。因为你写成
WALL
AREA
LEAD
LADY
的时候, 第一行和第一列是一样的。第二行和第二列也一样等等。
第二小题:
给一个string of strings,返回里面所有word squares:. from: 1point3acres.com/bbs
比如[AREA][LEAD][WALL][LADY][BALL]
你就要返回[[WALL][AREA][LEAD][LADY]],[[BALL][AREA][LEAD][LADY]]. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
用dfs做就行了。

我个人感觉gg更看重的是对问题的理解和交流过程。就是这样啦!祝大家好运!!



. 1point 3acres 璁哄潧
补充内容 (2016-9-15 04:39):. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
啊对忘记了提。onsite第一题。那个十字形的管子。面试官说为了简化就假设左边进就只右边出。上面进就只下面出。直着走。简单多了

评分

7

查看全部评分

本帖被以下淘专辑推荐:

harrypotter 发表于 2016-9-15 13:10:49 | 显示全部楼层
Onsite第三题matrix是用二维数组来存吗?如果是用二维数组的话,update时间是O(1)吧?Sum应该是O(n), 因为要把那些数字一个个加起来。
回复 支持 1 反对 0

使用道具 举报

jennyEternal 发表于 2016-9-15 13:09:31 | 显示全部楼层
感谢楼主分享!我把能有的米都贡献给你,祝你以后offer多多!

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

Henry要工作 发表于 2016-9-15 03:19:23 | 显示全部楼层
楼主电面过了多久,HR联系onsite啊
回复 支持 反对

使用道具 举报

Henry要工作 发表于 2016-9-15 03:20:00 | 显示全部楼层
恭喜楼主,回家送大米!
回复 支持 反对

使用道具 举报

haveto 发表于 2016-9-15 03:26:07 | 显示全部楼层
第一题管子求思路 ,对每个管子类型怎么建模啊?。。。
回复 支持 反对

使用道具 举报

readman 发表于 2016-9-15 03:36:03 | 显示全部楼层
楼主电面那题你的方法空间是n^2么, 二维dp做的?. from: 1point3acres.com/bbs

然后onsite管子那题是union-find么? 下边的是2d fenwick tree. 再下边的暴力就好...
回复 支持 反对

使用道具 举报

oily 发表于 2016-9-15 03:54:41 | 显示全部楼层
readman 发表于 2016-9-15 03:36
楼主电面那题你的方法空间是n^2么, 二维dp做的?
. 鍥磋鎴戜滑@1point 3 acres
然后onsite管子那题是union-find么? 下边的是2d fenwick ...

union find做两个方块的连通吗?
回复 支持 反对

使用道具 举报

feichangh 发表于 2016-9-15 04:00:42 | 显示全部楼层
第四题第一小问暴力检查除了对角线的半个matrix(i = 0 ~ m, j = i+1 ~ n)看看m[i][j]是不是等于m[j][i]。第二小问有什么优化么?只能想到暴力O(n4)跑一遍
回复 支持 反对

使用道具 举报

readman 发表于 2016-9-15 04:15:06 | 显示全部楼层
oily 发表于 2016-9-15 03:54 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
union find做两个方块的连通吗?

是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:30:20 | 显示全部楼层
Henry要工作 发表于 2016-9-15 03:19
楼主电面过了多久,HR联系onsite啊

很快就通知过了。但是安排onsite安排了特别久的时间。快一个月吧。。还是我催催催的结果。。。
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:32:05 | 显示全部楼层
啊对忘记了提。onsite第一题。那个十字形的管子。面试官说为了简化就假设左边进就只右边出。上面进就只下面出。直着走。简单多了
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:33:29 | 显示全部楼层
haveto 发表于 2016-9-15 03:26
第一题管子求思路 ,对每个管子类型怎么建模啊?。。。

我的方法是有一个boolean[4]。分别代表上下左右有没有口子。
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:34:03 | 显示全部楼层
readman 发表于 2016-9-15 03:36. visit 1point3acres.com for more.
楼主电面那题你的方法空间是n^2么, 二维dp做的?
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
然后onsite管子那题是union-find么? 下边的是2d fenwick ...

我咩有用dp做。。用的recursion。。
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:37:46 | 显示全部楼层
feichangh 发表于 2016-9-15 04:00
第四题第一小问暴力检查除了对角线的半个matrix(i = 0 ~ m, j = i+1 ~ n)看看m[j]是不是等于m[j]。第二小 ...

第二小问我是提议建一个trie tree先建字典。然后面试官说可以假设我已经有一个hashmap里面key是prefix,value是所有prefix是key的单词。然后再dfs。

因为当第一个单词选定的时候,第二个单词的第一个字母已经确定了,可以用prefix在字典里找。同理第三第四。
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:38:32 | 显示全部楼层
readman 发表于 2016-9-15 04:15-google 1point3acres
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构
. From 1point 3acres bbs
这些都没有说死,基本就是你怎么想就怎么设计,我觉得这里可能考了一点OOD
回复 支持 反对

使用道具 举报

plich 发表于 2016-9-15 04:52:32 | 显示全部楼层
第二题感觉上用heap会比较好

第三题用额外空间的话楼主是怎么处理edge case的啊, 我assume你是提前把加和存起来了……
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 05:12:12 | 显示全部楼层
plich 发表于 2016-9-15 04:52
第二题感觉上用heap会比较好

第三题用额外空间的话楼主是怎么处理edge case的啊, 我assume你是提前把加 ...

嗯第二题是heap-google 1point3acres
第三题就存每行的和 然后edge case就算的时候判断一下。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-9-15 06:55:46 | 显示全部楼层
hyperspace 发表于 2016-9-15 04:33
我的方法是有一个boolean[4]。分别代表上下左右有没有口子。

然后四方向做BFS ?
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 09:44:43 | 显示全部楼层
wtcupup 发表于 2016-9-15 06:55. from: 1point3acres.com/bbs
然后四方向做BFS ?

没有四方向了。题目的设定就是只有一个入口和一个出口。
回复 支持 反对

使用道具 举报

todayand 发表于 2016-9-15 12:05:57 | 显示全部楼层
请问lz,电面那题是不是直接从中间向两边遍历就可以了?O(n)的时间复杂度
回复 支持 反对

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 13:00:55 | 显示全部楼层
todayand 发表于 2016-9-15 12:05
请问lz,电面那题是不是直接从中间向两边遍历就可以了?O(n)的时间复杂度
. 1point3acres.com/bbs
我是从两头从向中间弄的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-9 12:00

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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