推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 7796|回复: 49
收起左侧

新鲜Google电面面经

[复制链接] |试试Instant~ |关注本帖
dokolo 发表于 2016-11-11 08:09:26 | 显示全部楼层 |阅读模式

2017(10-12月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
5分钟前面完

Round 1
1. LC 249
2. 8*8国际象棋棋盘,给定Knight的起始和结束位置,输出最短的从起点到终点的路径。

两题都是瞬秒了,然后面试官都说有小BUG,遂讨论之,都是面试官想错了...
做完两道题还剩15分钟,聊天十分钟,结束面试。.1point3acres缃

Round 2
1. Valid Number
我的人我的心都是崩溃的.... 最后写出来的代码有一个小问题,但是看起来乱糟糟的。.鏈枃鍘熷垱鑷1point3acres璁哄潧

2. LC 356, 但是直线可以是任意直线... 傻逼了我居然没想出正确解... 挂完电话一分钟想到了解,日了狗. more info on 1point3acres.com

就这样,感觉够呛. from: 1point3acres.com/bbs

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| dokolo 发表于 2016-12-6 10:20:06 | 显示全部楼层
上周二收到邮件开始Team Match,给大家参考一下时间线。Google的HR跟Facebook比实在是太效率了
回复 支持 1 反对 0

使用道具 举报

slarkzz 发表于 2016-11-11 08:15:20 | 显示全部楼层
为什么面了两轮啊?
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-11 08:16:24 | 显示全部楼层
slarkzz 发表于 2016-11-11 08:15
为什么面了两轮啊?

Google实习电面都是两轮吧
回复 支持 反对

使用道具 举报

blooe 发表于 2016-11-11 09:09:11 | 显示全部楼层
祝楼主好运,我觉得楼主至少都有加面

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sgm12 发表于 2016-11-11 09:45:01 | 显示全部楼层
不知楼主最后一个题的解是怎样呢?只想到先求重心,再之后就不太会了。。。
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-11 10:03:17 | 显示全部楼层
sgm12 发表于 2016-11-11 09:45
不知楼主最后一个题的解是怎样呢?只想到先求重心,再之后就不太会了。。。

我当时给出的解是对所有可能的两点间的直线分组,然后判断是否有一组包含所有点..

挂掉电话以后,想到了解... 应该是对第一个点和所有其他点,求垂直平分线,然后判断其他点的距离是不是对称分布在直线的两端,奇数个点的话,可能第一个点在对称轴上,这种情况需要另外再选其他端点
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-11 10:04:53 | 显示全部楼层
blooe 发表于 2016-11-11 09:09
祝楼主好运,我觉得楼主至少都有加面

谢谢你的祝福!
回复 支持 反对

使用道具 举报

lic10 发表于 2016-11-11 11:02:42 | 显示全部楼层
请问第一轮第二题是只要求长度还是必须找到路径?谢谢!
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-11 12:25:19 | 显示全部楼层
lic10 发表于 2016-11-11 11:02
请问第一轮第二题是只要求长度还是必须找到路径?谢谢!

需要找到路径,不是长度
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-11 12:27:05 | 显示全部楼层
当时给出的解法是,对于每一个点对,计算其垂直平分线,用约分的(a,b,c)表示唯一的直线ax+by+c=0,对于所有n^2的点对,用(a,b,c)作key来用hashtable分组,最后看看是不是有哪一组包含所有的点。现在想了下似乎也没错?不知道各位怎么想...
回复 支持 反对

使用道具 举报

mingruiyrh 发表于 2016-11-11 12:58:12 | 显示全部楼层
dokolo 发表于 2016-11-11 12:25
需要找到路径,不是长度

是找到所有的最短路径吗?还是只要输出一条就可以?
回复 支持 反对

使用道具 举报

guoyuezhong 发表于 2016-11-11 17:14:15 | 显示全部楼层
楼主任意直线怎么做?我想到的时候对于一个点A,遍历点集合,组成pair以后,pair的中垂线是候选直线,然后用o(n)的时间看是否ok.总时间复杂度n^2
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-12 03:24:38 | 显示全部楼层
mingruiyrh 发表于 2016-11-11 12:58
是找到所有的最短路径吗?还是只要输出一条就可以?

输出一条就可以了
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-12 03:27:09 | 显示全部楼层
guoyuezhong 发表于 2016-11-11 17:14
楼主任意直线怎么做?我想到的时候对于一个点A,遍历点集合,组成pair以后,pair的中垂线是候选直线,然后用 ...

我昨晚仔细思考了这个问题,你的这个做法是我想到的第二个做法。但是如果允许点在对称轴上的话,两个做法都不行。. 1point 3acres 璁哄潧

试想,所有的点都在一条直线上,而且关于其重心不对称,那么是没有任何中垂线能对称分割的。所以应该是p1和任意pi的中垂线,以及连线作为候选,来判断是否可行
回复 支持 反对

使用道具 举报

guoyuezhong 发表于 2016-11-12 18:25:14 | 显示全部楼层
dokolo 发表于 2016-11-12 03:27
我昨晚仔细思考了这个问题,你的这个做法是我想到的第二个做法。但是如果允许点在对称轴上的话,两个做法 ...

是的,我的确没有考虑到p1在对称轴的情况。

. visit 1point3acres.com for more.我觉得"p1和任意pi的中垂线,以及连线作为候选,来判断是否可行" 这个思路会有一个case过不了,不知道我理解你的意思对不。比方说p1 = (1, 0), p2 = (2, 1) p3 = (2, -1) 这时p1在对称轴上,但是p2 p3和p1的中垂线或者连线都不是对称轴。

我想解决的方法是 选两个点p1 和 p2,分别对剩下的点做中垂线检验。如果这些都不满足,那么如果存在对称轴,只有可能是p1 p2均在对称轴上,再看p1 p2的连线是否是对称轴。

这样总复杂度还是n^2,但是计算量变成两倍了。
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-14 13:16:29 | 显示全部楼层
guoyuezhong 发表于 2016-11-12 18:25
是的,我的确没有考虑到p1在对称轴的情况。

我觉得"p1和任意pi的中垂线,以及连线作为候选,来判断是 ...

你的做法是对的...
面官写完feedback了,不知道结果如何,哈哈
回复 支持 反对

使用道具 举报

blooe 发表于 2016-11-15 06:00:14 | 显示全部楼层
dokolo 发表于 2016-11-14 13:16
你的做法是对的...
. From 1point 3acres bbs面官写完feedback了,不知道结果如何,哈哈
.1point3acres缃
啊,楼主怎么知道面官写完feedback了??
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-15 08:26:28 | 显示全部楼层
blooe 发表于 2016-11-15 06:00
啊,楼主怎么知道面官写完feedback了??
.鏈枃鍘熷垱鑷1point3acres璁哄潧
内推人能看到
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-23 02:39:03 | 显示全部楼层
昨天内推人告诉我进HC了
回复 支持 反对

使用道具 举报

如果我是金牛座 发表于 2016-11-23 02:53:02 | 显示全部楼层
恭喜楼主啊!请问你有没有收到HR的回复啊?我上周刚面好,昨天发邮件问内推人,内推人也没有回复…超级紧张……
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-8-20 20:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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