一亩三分地论坛

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

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

11.19 电面一轮和二轮

[复制链接] |试试Instant~ |关注本帖
roosterxie 发表于 2015-11-20 05:35:36 | 显示全部楼层 |阅读模式

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

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

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

x

一轮是个国人面试官 就做了一题 lintcode wood cut. 之前只刷了leetcode没刷lintcode 感觉这波很亏,

二轮是个三哥
第一题plus one
第二题 有个x,y坐标系的array A[(1,0),(0,1)] 都在一个圆上 圆心会给(0,0)
   有第二个点的arrayB[(8,9),(12,-5)] 求问 对于每个在B array里的点,找出A里距离最近的点

第二题把A的点换成极坐标sort 然后binary search 最后没写完。 感觉要黑。

评分

1

查看全部评分

本帖被以下淘专辑推荐:

Augustus 发表于 2015-11-21 00:46:18 | 显示全部楼层
阿三太阴险了,给这么难的题目.......
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-11-22 14:10:42 | 显示全部楼层
为什么要换成极坐标啊?感觉和极坐标没有什么关系啊?可以解释一下么?
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-23 01:15:00 | 显示全部楼层
jkingxt 发表于 2015-11-22 14:10
为什么要换成极坐标啊?感觉和极坐标没有什么关系啊?可以解释一下么?

换成极坐标 就可以通过binary search最接近的角度来直接得到最近的点 而不用计算距离再比较。计算距离需要O(a*b),而binary search是O(bloga)+O(aloga) 更快
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-11-23 12:12:27 | 显示全部楼层
roosterxie 发表于 2015-11-23 01:15. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
换成极坐标 就可以通过binary search最接近的角度来直接得到最近的点 而不用计算距离再比较。计算距离需 ...

但是使用极坐标来获得角度最近的点不一定是距离的点啊,还是需要计算距离啊
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-24 03:52:26 | 显示全部楼层
jkingxt 发表于 2015-11-23 12:12
但是使用极坐标来获得角度最近的点不一定是距离的点啊,还是需要计算距离啊

我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-11-24 05:27:41 | 显示全部楼层
roosterxie 发表于 2015-11-24 03:52. 1point3acres.com/bbs
我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离

哦哦,好的,那我差不多懂了。谢谢lz说的这么详细
回复 支持 反对

使用道具 举报

cherylshang 发表于 2015-11-27 22:50:13 | 显示全部楼层
LZ有消息了么?
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-28 00:23:16 | 显示全部楼层

挂了 明年再接再厉。
回复 支持 反对

使用道具 举报

liangyue268 发表于 2015-11-28 00:41:55 | 显示全部楼层
roosterxie 发表于 2015-11-24 03:52.1point3acres缃
我没说清楚。 这里我说的极坐标的中心点是圆心。 角度最近的点就是距离最近的点。不需要计算距离

不好意思,我还没明白什么意思。
如果A中有两个点(0,1),(1,10),而B中有一个点(0,10)
如果按角度来说(0,1)和(0,10)角度最近(一样),但是明明是(1,10)和(0,10)距离更近啊?
回复 支持 反对

使用道具 举报

gc1993114 发表于 2015-11-28 03:30:13 | 显示全部楼层
哎lz加油!
是感恩节前有消息的?我20号面的,还没信。。哎
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-30 09:22:50 | 显示全部楼层
liangyue268 发表于 2015-11-28 00:41
不好意思,我还没明白什么意思。
如果A中有两个点(0,1),(1,10),而B中有一个点(0,10)
如果按 ...
. visit 1point3acres.com for more.
角度是根据a的圆心来算 不是(0,0) 我在楼上某层说过了

补充内容 (2015-11-30 09:47):
你给的两个点(0,1)(1,10)可以假设圆心是(0.5,5.5) 因为A的点都在圆上面.那么对于你给的B点(0,10),角度是 96,对与Aarray里点的角度276, 83.近点就是 (1,10) 角度算法参考三角函数,面试不要求
回复 支持 反对

使用道具 举报

 楼主| roosterxie 发表于 2015-11-30 09:24:50 | 显示全部楼层
gc1993114 发表于 2015-11-28 03:30. 1point 3acres 璁哄潧
哎lz加油!
是感恩节前有消息的?我20号面的,还没信。。哎

明年再接再厉吧,是感恩节前的消息。 现在准备学校考试 寒假准备准备明年春季冲一冲amazon
回复 支持 反对

使用道具 举报

liangyue268 发表于 2015-12-1 00:20:27 | 显示全部楼层
roosterxie 发表于 2015-11-30 09:22
角度是根据a的圆心来算 不是(0,0) 我在楼上某层说过了. visit 1point3acres.com for more.

补充内容 (2015-11-30 09:47):

哦哦,谢谢楼主!
. from: 1point3acres.com/bbs
补充内容 (2015-12-1 00:26):
是我之前没理解,楼主还把我例子的的角度算出来了,这么有心一定会有好offer的!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 00:40:28 | 显示全部楼层
哪位大神可以贴下第二面代码吗?没太懂。。
回复 支持 反对

使用道具 举报

yueyub 发表于 2016-1-19 13:57:50 | 显示全部楼层
Augustus 发表于 2015-11-21 00:46
阿三太阴险了,给这么难的题目.......
.1point3acres缃
物理系的觉得很简单。对计算机的来说,确实有点绕。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 22:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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