国内一线互联网在职谈谈对归国留学生的看法

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
[Google级团队]
实时大数据分析领域践行者
北京/深圳-大数据/搜索/机器学习岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 10238|回复: 35
收起左侧

Google Onsite

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

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

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

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

x
一个月前面的,第一家面的公司,HR说非常close但是还是挂了。求加点分。.鏈枃鍘熷垱鑷1point3acres璁哄潧
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

评分

3

查看全部评分

本帖被以下淘专辑推荐:

小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
请问楼主第三题什么解法啊?
. 1point 3acres 璁哄潧
用的是DFS,起点为所有碰到X=0和Y=1的边的censor,终点是X=1或者Y=0的边,如果有一条censor形成的path从任意起点到终点,就表示过不去

补充内容 (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;. From 1point 3acres bbs
  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。
回复 支持 反对

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 05:58:08 | 显示全部楼层
xpli521 发表于 2016-9-18 05:54
原来是这个意思,那楼主你看看下面这个思路可行吗,
class Person{. 鍥磋鎴戜滑@1point 3 acres
  int id;

如果A和B是direct friends,删除了A和B后,还得找到A通过B而得到的各层indirect friends然后更新,然后vice versa。
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.鐣欏璁哄潧-涓浜-涓夊垎鍦
求大神解答==

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

使用道具 举报

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

使用道具 举报

 楼主| kevinwangjk 发表于 2016-9-18 08:12:13 | 显示全部楼层
william_gong 发表于 2016-9-18 07:18
请问第一轮那题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
非大神。。上面已经提到过了,就是要删除的时候重新建立所有间接朋友。。。很慢,但是假设就是删除朋友发 ...

在想可不可以这样做:
为每个间接朋友设一个计数器,表示和间接朋友share多少个直接朋友
这样比如原来A-B-C,A和B的连接断掉以后A-C之间的计数器-1,如果计数器是0才删掉间接朋友。这样不用整个重构
加直接朋友的时候也需要更新计数器就是了,但是本来就要检查是否会导致增加间接朋友,所以不会多出多少开销
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

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

使用道具 举报

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

删除A-B的时候肯定是要访问所有A的间接朋友和B的所有间接朋友
我觉得导致慢的可能是对A的每个间接朋友C,还要检查A的直接朋友和C的直接朋友的交集,这个操作不是O(1)的,感觉至少是线性的。但是用计数器的话,就是直接减一下。
. visit 1point3acres.com for more.
不过也许我把不用计数器更新间接朋友的算法想复杂了?
回复 支持 反对

使用道具 举报

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

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-4-26 19:47

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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