10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 7069|回复: 50
收起左侧

gg全套

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
今年6月份找人refer的。拿着别的offer使劲催终于在上周走完了全过程。借个别人的号来写一下我能想起来的题。
但个人觉得gg的题库太大,而且一直在改动,面经的帮助远远不如小公司大。所以大家要面gg的话还是要基本功扎实才靠谱呀。
. visit 1point3acres.com for more.
1. OA -> 看这个帖子~http://www.1point3acres.com/bbs/thread-193639-1-1.html
OA的题目一直都有些不同的题。但一般题都差不多,最多是求最大或最小这样的小区别。-google 1point3acres
. more info on 1point3acres.com
2. tech phone interview
input一个string str,方法要求split str into elements,return符合要求的最大elements数量。。这题有点怪我来写几个例子:.1point3acres缃
eg1. input: abab -》 return 2
         可以被分成 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. from: 1point3acres.com/bbs
eg5: 空字符串返回0

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

管子们

管子们


然后我们有个网格要把这些管子放进去。设计游戏并且实现一个方法来检验:气体能否从左下进去,右上出去并且不泄漏。-google 1point3acres
比如这个就是true:
Screen Shot 2016-09-14 at 11.31.37 AM.png
这个就是false (画一半笔没水了。。):
Screen Shot 2016-09-14 at 11.31.42 AM.png


(2).这个题很简单,但是follow up和细节问题特。别。多。
input : a set of points S+ target point P+ integer k.鐣欏璁哄潧-涓浜-涓夊垎鍦
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
7 8 9

update: 输入position和value 直接更新就行了。
比如(0,0),2:matrix变成
2 2 3 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4 5 6
7 8 9. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

sum:输入两个position 返回两个position定下的这个小matrix里面的元素的和。
比如 (1,1) (2,2)
返回
5 6 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
8 9
的和。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

要求两个方法都是O(n)。 -》 用到extra space

(4)
给一个string of strings,判断是不是一个word square:
比如[WALL][AREA][LEAD][LADY]就是。因为你写成.鐣欏璁哄潧-涓浜-涓夊垎鍦
WALL
AREA
LEAD
LADY
的时候, 第一行和第一列是一样的。第二行和第二列也一样等等。
第二小题:
给一个string of strings,返回里面所有word squares:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
比如[AREA][LEAD][WALL][LADY][BALL]
你就要返回[[WALL][AREA][LEAD][LADY]],[[BALL][AREA][LEAD][LADY]]
用dfs做就行了。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我个人感觉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做的?

. Waral 鍗氬鏈夋洿澶氭枃绔,然后onsite管子那题是union-find么? 下边的是2d fenwick tree. 再下边的暴力就好...
回复 支持 反对

使用道具 举报

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

然后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做两个方块的连通吗?
. from: 1point3acres.com/bbs
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构
回复 支持 反对

使用道具 举报

 楼主| 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
楼主电面那题你的方法空间是n^2么, 二维dp做的?-google 1point3acres

然后onsite管子那题是union-find么? 下边的是2d fenwick ...

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

使用道具 举报

 楼主| hyperspace 发表于 2016-9-15 04:37:46 | 显示全部楼层
feichangh 发表于 2016-9-15 04:00. 1point 3acres 璁哄潧
第四题第一小问暴力检查除了对角线的半个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
是的..因为题目说的进是左下出是右上...不过我也不知道给的数据什么结构
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
这些都没有说死,基本就是你怎么想就怎么设计,我觉得这里可能考了一点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
第三题就存每行的和 然后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. 鍥磋鎴戜滑@1point 3 acres
然后四方向做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)的时间复杂度
-google 1point3acres
我是从两头从向中间弄的
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-21 09:49

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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