一亩三分地论坛

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

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

新鲜Google电面面经

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

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

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

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

x
5分钟前面完

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

两题都是瞬秒了,然后面试官都说有小BUG,遂讨论之,都是面试官想错了...
做完两道题还剩15分钟,聊天十分钟,结束面试。-google 1point3acres
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Round 2
1. Valid Number
我的人我的心都是崩溃的.... 最后写出来的代码有一个小问题,但是看起来乱糟糟的。

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

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

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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. 1point3acres.com/bbs
需要找到路径,不是长度

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

使用道具 举报

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的中垂线是候选直线,然后用 ...

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

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

使用道具 举报

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

是的,我的确没有考虑到p1在对称轴的情况。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我觉得"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
你的做法是对的...
面官写完feedback了,不知道结果如何,哈哈

啊,楼主怎么知道面官写完feedback了??
回复 支持 反对

使用道具 举报

 楼主| dokolo 发表于 2016-11-15 08:26:28 | 显示全部楼层
blooe 发表于 2016-11-15 06:00.1point3acres缃
啊,楼主怎么知道面官写完feedback了??

内推人能看到
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 06:48

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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