一亩三分地论坛

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

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

Google Onsite

[复制链接] |试试Instant~ |关注本帖
kevinwangjk 发表于 2016-9-18 04:32:40 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 全职@Google - 内推 - Onsite |Fail在职跳槽

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

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

x
一个月前面的,第一家面的公司,HR说非常close但是还是挂了。求加点分。
1. 设计一个class,可以实现往里面加interval和给一个value返回这个value在不在之前加的interval里。
2. Game of life,要求每个cell查看少于8个周围cell的value,然后followup就是board无限大怎么处理。
3. 一个房间,左下角是(0,0)右上角是(1,1),给若干个sensor,每个censor有(x,y,r),r代表圆的半径,问有没有办法可以从左下走到右上不被任何censor探到。
4. 设计朋友的朋友,可以加朋友,然后查看两个人是不是朋友。讨论朋友的朋友也算朋友,然后要实现可以删除朋友。难点在于A和B可能不是直接朋友,但是可以是通过各种不同的人成为间接朋友,删除其中一条链接不一定两个人就不是朋友了。讨论很久最后写代码只有十分钟左右,没写完。
5. minimum substring containing only 2 unique characters, followup - k characters. 鍥磋鎴戜滑@1point 3 acres

评分

2

查看全部评分

本帖被以下淘专辑推荐:

小A要当码农 发表于 2016-9-18 04:53:05 | 显示全部楼层
请问楼主第三题什么解法啊?
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-18 04:58:50 | 显示全部楼层
求问第四题思路, 用类似存graph的方法来存吗?
还是用别的什么办法?
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 05:00:38 | 显示全部楼层
小A要当码农 发表于 2016-9-18 04:53. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
请问楼主第三题什么解法啊?

用的是DFS,起点为所有碰到X=0和Y=1的边的censor,终点是X=1或者Y=0的边,如果有一条censor形成的path从任意起点到终点,就表示过不去. 1point3acres.com/bbs
. more info on 1point3acres.com
补充内容 (2016-9-18 05:01): 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
X=0或者Y=1
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 05:02:55 | 显示全部楼层
william_gong 发表于 2016-9-18 04:58
求问第四题思路, 用类似存graph的方法来存吗?
还是用别的什么办法?

我想了好久想不出什么好办法,结果他最后提示就是每次删朋友后要重新建立所有有关人的关系图。每个人有一个直接朋友和间接朋友的list。
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-18 05:38:13 | 显示全部楼层
楼主朋友那题我有个不明白的, 如果A 有朋友B, B有朋友C,那么A和C就是朋友,如果想删除A的朋友C,那要怎么做呢, 在不影响B的朋友关系的情况下?
感觉如果B一直有朋友A和C,那么A和C怎么都没法删除朋友关系?
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 05:41:20 | 显示全部楼层
xpli521 发表于 2016-9-18 05:38
楼主朋友那题我有个不明白的, 如果A 有朋友B, B有朋友C,那么A和C就是朋友,如果想删除A的朋友C,那要怎 ...

要删除A和C的关系只能删除A和B或者B和C的关系,不能直接删除A和C。然后如果A->D->C的话,那删除了A和B的朋友关系,A和C也还是朋友
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-18 05:54:45 | 显示全部楼层
kevinwangjk 发表于 2016-9-17 14:41
要删除A和C的关系只能删除A和B或者B和C的关系,不能直接删除A和C。然后如果A->D->C的话,那删除了A和B的 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
原来是这个意思,那楼主你看看下面这个思路可行吗,
class Person{
  int id;
  Set<Person> directFriend;
  Set<Person> indirectFriend;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
}

如果要删除的盆友 B在person A的directFriend里面,那就直接从A的directFriend 中删除B,B的direct friend中删除A。
如果要删除的盆友 B在person A的indirectFriend里面,那就scan A的directFriend set,任意在该set中的friend k,
如果k有direct or indirect friend B,把所有满足条件的k从A的directFriend set中删除。同时更新k的direct friend set。. Waral 鍗氬鏈夋洿澶氭枃绔,
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 05:58:08 | 显示全部楼层
xpli521 发表于 2016-9-18 05:54
原来是这个意思,那楼主你看看下面这个思路可行吗,
class Person{
  int id;

如果A和B是direct friends,删除了A和B后,还得找到A通过B而得到的各层indirect friends然后更新,然后vice versa。.鏈枃鍘熷垱鑷1point3acres璁哄潧
A和B是indirect friends应该不能直接删除
回复 支持 反对

使用道具 举报

xpli521 发表于 2016-9-18 06:05:10 | 显示全部楼层
kevinwangjk 发表于 2016-9-17 14:58
如果A和B是direct friends,删除了A和B后,还得找到A通过B而得到的各层indirect friends然后更新,然后vi ...

求大神解答==
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 06:08:33 | 显示全部楼层
xpli521 发表于 2016-9-18 06:05. from: 1point3acres.com/bbs
求大神解答==

非大神。。上面已经提到过了,就是要删除的时候重新建立所有间接朋友。。。很慢,但是假设就是删除朋友发生的很少,只要查找两个人是不是朋友快就可以。
回复 支持 反对

使用道具 举报

william_gong 发表于 2016-9-18 07:18:28 | 显示全部楼层
请问第一轮那题lz是怎么做的呢?
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 08:12:13 | 显示全部楼层
william_gong 发表于 2016-9-18 07:18-google 1point3acres
请问第一轮那题lz是怎么做的呢?

用个BST存interval,然后加interval的时候merge重复的,key用lower bound
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-18 11:41:32 | 显示全部楼层
第三题,能详细说说么?
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-18 21:26:34 | 显示全部楼层
kevinwangjk 发表于 2016-9-18 06:08
非大神。。上面已经提到过了,就是要删除的时候重新建立所有间接朋友。。。很慢,但是假设就是删除朋友发 ...
.1point3acres缃
在想可不可以这样做:
为每个间接朋友设一个计数器,表示和间接朋友share多少个直接朋友
这样比如原来A-B-C,A和B的连接断掉以后A-C之间的计数器-1,如果计数器是0才删掉间接朋友。这样不用整个重构
加直接朋友的时候也需要更新计数器就是了,但是本来就要检查是否会导致增加间接朋友,所以不会多出多少开销. From 1point 3acres bbs
回复 支持 反对

使用道具 举报

迷彩的瓜皮帽 发表于 2016-9-19 01:57:54 | 显示全部楼层
题很有意思啊
感谢!
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-19 02:43:31 | 显示全部楼层
hxtang 发表于 2016-9-18 21:26
在想可不可以这样做:
为每个间接朋友设一个计数器,表示和间接朋友share多少个直接朋友-google 1point3acres
这样比如原来A ...

但是worst case还是一样的,而且也还是要看所有的间接朋友有没有到0。
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-9-19 02:51:06 | 显示全部楼层
kevinwangjk 发表于 2016-9-19 02:43
但是worst case还是一样的,而且也还是要看所有的间接朋友有没有到0。

删除A-B的时候肯定是要访问所有A的间接朋友和B的所有间接朋友
我觉得导致慢的可能是对A的每个间接朋友C,还要检查A的直接朋友和C的直接朋友的交集,这个操作不是O(1)的,感觉至少是线性的。但是用计数器的话,就是直接减一下。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
不过也许我把不用计数器更新间接朋友的算法想复杂了?
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-9-20 08:03:59 | 显示全部楼层
请问第二题怎么算满足不查看周围8个value的要求?
回复 支持 反对

使用道具 举报

iFrances 发表于 2016-9-21 01:57:52 | 显示全部楼层
LZ请问 game of life board无限大怎么处理呢?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:06

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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