一亩三分地论坛

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

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

11.9新鲜google电面

[复制链接] |试试Instant~ |关注本帖
vinoblade 发表于 2015-11-10 07:15:34 | 显示全部楼层 |阅读模式

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

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

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

x
趁着题目还挺有印象发一下。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
一轮是google NY的一个女生,问的问题还算中规中矩。
一问warm up:sort color
二问:给一个stream类,里面有next()方法和hasmore()方法,要求写一个UnionSet类,实现unionOp()和next()方法
二轮是CA的一个白人小哥,问的第二个问题简直血崩。。。
一问warm up:longest increasing value sequence
二问:给一堆点,判断有没有一条line使得这些点关于这条line对称。一上来简直懵逼。。。小哥看我搞不出来,出了个简化版本,给一堆点和一条line,判断这堆点是否关于这条line对称,假设判断关于这条line对称的function是存在的。写出这个来以后小哥又让我继续写original problem,结果时间就到了。。。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
祝大家好运!!!!

评分

6

查看全部评分

本帖被以下淘专辑推荐:

宝贝忆彼岸 发表于 2015-11-10 07:55:09 | 显示全部楼层
感谢分享,请问第一轮第二问能详细说说嘛?UnionSet类有什么特点和功能呢?
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 08:21:10 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 07:55
感谢分享,请问第一轮第二问能详细说说嘛?UnionSet类有什么特点和功能呢?

不是特别好描述,简单说就是要通过给的IntStream类中的方法来构建新的UnionStream类。要求实现UnionOp,就是把两个stream做union操作,以及next()方法,类似于iterator。主要难点在于要一边call IntStream里的next()和hasmore()一边做unionOp,不能直接生成新的unionset。
回复 支持 反对

使用道具 举报

宝贝忆彼岸 发表于 2015-11-10 08:31:41 | 显示全部楼层
vinoblade 发表于 2015-11-10 08:21
不是特别好描述,简单说就是要通过给的IntStream类中的方法来构建新的UnionStream类。要求实现UnionOp, ...

明白了,union的规则是什么呢?是说新生成的unionStream每次call next()方法都来自于不同的stream是吗?比如上一个来自stream a,那么下一个next()方法的元素就要来自stream b?
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 08:39:53 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 08:31
明白了,union的规则是什么呢?是说新生成的unionStream每次call next()方法都来自于不同的stream是吗? ...

没有特定的规则。就是相当于stream a生成一个setA,stream b生成一个setB,然后union setA and setB.
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-10 10:08:45 | 显示全部楼层
lz 点关于直线对称后来有想出来吗?
回复 支持 反对

使用道具 举报

孤笑客 发表于 2015-11-10 10:09:17 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-10 08:31
明白了,union的规则是什么呢?是说新生成的unionStream每次call next()方法都来自于不同的stream是吗? ...

IntStream A和B本身都是set。
然后你需要实现一个新的UnionStream,这个UnionStream的next()是A和B里的数字。但是同时需要保证UnionStream自己也是具有set属性的。

恩…换通俗的话说就是,A里的数字都没有重复,B里的数字也没有重复,请实现一个新的方法去输出A/B里的数,并保证输出的数也没有重复。
举例:. Waral 鍗氬鏈夋洿澶氭枃绔,
A = [1,2,3]
B = [1,4,5,6]. more info on 1point3acres.com
输出就是[1,2,3,4,5,6]
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 10:32:44 | 显示全部楼层
孤笑客 发表于 2015-11-10 10:09
IntStream A和B本身都是set。
然后你需要实现一个新的UnionStream,这个UnionStream的next()是A和B里的 ...
.1point3acres缃
基本上是这么个意思。但是新的UnionSet实时更新的。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-10 10:35:59 | 显示全部楼层
对称那道我网上都搜不到啊~
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 10:40:00 | 显示全部楼层
mooc 发表于 2015-11-10 10:35
对称那道我网上都搜不到啊~

就是这么回事儿。。。
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-10 10:46:11 | 显示全部楼层
vinoblade 发表于 2015-11-10 10:40
就是这么回事儿。。。

LZ现在有啥思路么?
回复 支持 反对

使用道具 举报

ljdsoft 发表于 2015-11-10 10:49:32 | 显示全部楼层
直线对称那题,看可不可以这样想。如果点数是偶数,那把所有的点坐标加起来除以总数,得到平均值,即为中心点,line应该通过这个中心点是吧。然后通过这个中心点计算到每个点的距离,看两两相不相等。如果点数是奇数,那必须有个点在直线上,咋办?没想出来。。。。
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 10:52:28 | 显示全部楼层
ljdsoft 发表于 2015-11-10 10:49
直线对称那题,看可不可以这样想。如果点数是偶数,那把所有的点坐标加起来除以总数,得到平均值,即为中心 ...

No,这个思路我面试的时候提出来了,但不对。你可以考虑这个例子,输入点为(0,0),(0,1),(1,1),(1,2)
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 10:52:56 | 显示全部楼层
mooc 发表于 2015-11-10 10:46
LZ现在有啥思路么?

没思路。感觉这题真的很奇怪,发散性太强了。
回复 支持 反对

使用道具 举报

yimingzi 发表于 2015-11-10 11:02:41 | 显示全部楼层
brute force一点呢?..我们可以枚举每一个使两点对称的直线O(n^2),然后调用2的方法?...
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 11:08:12 | 显示全部楼层
yimingzi 发表于 2015-11-10 11:02.鐣欏璁哄潧-涓浜-涓夊垎鍦
brute force一点呢?..我们可以枚举每一个使两点对称的直线O(n^2),然后调用2的方法?...

这个也不行。。因为line可以是any line也就是说可以精确到double的。。根本迭代不过来。
回复 支持 反对

使用道具 举报

yimingzi 发表于 2015-11-10 11:13:25 | 显示全部楼层
vinoblade 发表于 2015-11-10 11:08. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
这个也不行。。因为line可以是any line也就是说可以精确到double的。。根本迭代不过来。

可以使两个点对称的直线有且只有一条吧?...
回复 支持 反对

使用道具 举报

mooc 发表于 2015-11-10 11:14:15 | 显示全部楼层
yimingzi 发表于 2015-11-10 11:13. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
可以使两个点对称的直线有且只有一条吧?...

你不知道是哪两个点对称啊~
回复 支持 反对

使用道具 举报

yimingzi 发表于 2015-11-10 11:15:37 | 显示全部楼层
mooc 发表于 2015-11-10 11:14
你不知道是哪两个点对称啊~

所以枚举所有的点..O(n^2)..
回复 支持 反对

使用道具 举报

 楼主| vinoblade 发表于 2015-11-10 11:28:43 | 显示全部楼层
想了一下,应该可以先计算所有点连成的线的中点,然后依次判断计算两两中点连成的线是不是symmetry line。但是这样复杂度就太高了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:02

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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