如何在一个新城市*快速*安顿物品清单

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 2014|回复: 37
收起左侧

[FB]非死不可最新电面

[复制链接] |试试Instant~ |关注本帖
我的人缘0
Iceinvoker 发表于 2018-6-12 07:44:59 | 显示全部楼层 |阅读模式
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩

2018(4-6月) 码农类General 硕士 全职@Facebook - 内推 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
刚刚五分钟前电面,听说来地里发面经,人品会UP UP。-google 1point3acres
给我电面的是个萌萌的伊朗小哥,虽然口音有点捉急,但不影响总体交流。
第一题:哈希
Input:
A seq of int <3, 4, 1, 2>
A target int 5
Output:
whether a continuous subseq sums up to the target
target 5 -> True. more info on 1point3acres
target 4 -> True
target 6 -> False
follow up: 分析时间复杂度,空间复杂度,改成输出最短长度的subsequence的长度,以及有什么test case

第二题: 拓扑排序+BFS. 留学申请论坛-一亩三分地

n jobs 0 .. n-1 single processor.Executing each job taked one unit of time i, j  -> before starting i, we should have finished j Input:n
<(i,j)> list ofjob dependencies
Output:
min req time forfinishing job index 0
Input:
6
1 2
1 3
4 1
0 1
4 5
Output: 4 (3, 2, 1, 0)
求这位伊朗小哥能看我顺眼让我过了电面!各位大佬请随意赏些大米


补充内容 (2018-6-14 14:53):
在各位地里小伙伴的指点下,我决定更正一下:第二题只是个构建图然后从job0出发的搜索问题,并不是拓扑排序。

评分

参与人数 10大米 +35 收起 理由
PciPca + 3 给你点个赞!
dlwlrma + 5 给你点个赞!
yzkst06100 + 3 欢迎来一亩三分地论坛!
flyforevergc + 2 给你点个赞!
leetcoder1995 + 3 给你点个赞!
czhang1974 + 3 给你点个赞!
litus + 3 很有用的信息!
martinliu2218 + 5 给你点个赞!
jeff_xu001 + 5 给你点个赞!
shy90109 + 3 给你点个赞!

查看全部评分


上一篇:亚麻从口头offer到正式offer需要多久
下一篇:为了我们 柒拾分钟OA

本帖被以下淘专辑推荐:

我的人缘0
Big_Biang 发表于 2018-6-13 10:09:30 | 显示全部楼层
本楼: 【顶】   100% (2)
 
 
0% (0)   【踩】
全局: 顶  86% (26)
 
 
13% (4)  踩
laskuma 发表于 2018-6-13 03:14
同样是构建图,从0开始做bfs,我觉得可以用一个set存bfs访问过的节点,如果bfs到已访问的节点就说明存在 ...

反着bfs的话节点不是按照入度来分层的,用set存访问过的节点来判断环不太对,比如边是(0,1), (0,2), (2,3), (3,1) 。第一层0,第二层1,2, 第三层3, 访问3的时候1已经访问过了,同时3还要再访问1, 但是这里并没有环

不过你说的也是,直接拓扑排序判断环也会误伤。。。感觉要先bfs把需要走的点都记下来,然后再拓扑排序,然后只走之前bfs过的点。。。好麻烦,不知道有没有简洁一点的思路啊。。
回复

使用道具 举报

我的人缘0
landy622 发表于 2018-6-12 12:26:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  75% (3)
 
 
25% (1)  踩
楼主第二题是 course scheduler 2吗?按照拓扑的话,不是有23510这样子吗?能再解释一下不
回复

使用道具 举报

我的人缘0
martinliu2218 发表于 2018-6-12 12:39:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  65% (51)
 
 
34% (27)  踩
同问第二题是不是就是拓扑排序呢?谢谢!
回复

使用道具 举报

我的人缘0
csprogramming 发表于 2018-6-12 12:45:40 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (23)
 
 
0% (0)  踩
请问楼主什么时候内推的 大概多久hr联系啊

21.000+ students read the Road to learn React. The course weaves all the opinionated roadmaps into one roadmap to master React. It gives you all the fundamentals in React. You will build a Hacker News App along the way.

回复

使用道具 举报

我的人缘0
houqingniao 发表于 2018-6-12 13:48:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (34)
 
 
8% (3)  踩
第二题简单的拓扑排序会包含一些不必要的步骤,比如这个例子,按排序做应该是2,3,5,1,0, 会多了个5,LZ是怎么把这个踢出的啊
回复

使用道具 举报

我的人缘0
z001242001 发表于 2018-6-12 13:49:17 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (7)
 
 
12% (1)  踩
請問樓主是今年什麼時候畢業呢? 面的是什麼時候入職的?
謝謝
回复

使用道具 举报

我的人缘0
say543 发表于 2018-6-12 14:38:39 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  85% (34)
 
 
15% (6)  踩
houqingniao 发表于 2018-6-12 13:48. Waral 博客有更多文章,
第二题简单的拓扑排序会包含一些不必要的步骤,比如这个例子,按排序做应该是2,3,5,1,0, 会多了个5,L ...

我的想法是反向建graph 然后从target node bfs 回朔 这样感觉可行

With React+D3v4 you'll learn the basics of building fast data visualization components in about an hour.

回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:04:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
landy622 发表于 2018-6-12 12:26. From 1point 3acres bbs
楼主第二题是 course scheduler 2吗?按照拓扑的话,不是有23510这样子吗?能再解释一下不

跟Course Schedule II 不一样,Course Schedule II 要求返回任意一个上课的顺序,这题要求返回是否能完成“job 0”, 我觉得这个稍微简单一点
回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:05:32 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
martinliu2218 发表于 2018-6-12 12:39
同问第二题是不是就是拓扑排序呢?谢谢!
.本文原创自1point3acres论坛
第二题是拓扑排序滴。我在第二题的开头就写了,我用了拓扑排序加bfs的方法解的
回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:07:05 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
csprogramming 发表于 2018-6-12 12:45.1point3acres网
请问楼主什么时候内推的 大概多久hr联系啊

我大概是5.22左右招人内推的,上周HR才回复我的,中间隔了三周左右吧

Learn React.js, Redux & Immutable.js while building a weather app

回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:11:02 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
houqingniao 发表于 2018-6-12 13:48
第二题简单的拓扑排序会包含一些不必要的步骤,比如这个例子,按排序做应该是2,3,5,1,0, 会多了个5,L ...

好问题!我一开始就是这么做的,后来那个小哥就一个劲儿地跟我说你描述的这种情况,我才意识到我想错了,所以应该把拓扑排序的相对关系反一下存起来,从job0出发来找他的邻居,然后通过bfs层级遍历找job0邻居的邻居,直至出现的邻居入度为零,肯定就是最短路径。不知道这个解释清楚嘛
回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:12:47 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
z001242001 发表于 2018-6-12 13:49
請問樓主是今年什麼時候畢業呢? 面的是什麼時候入職的?. visit 1point3acres for more.
謝謝

我今年五月份刚刚毕业的,具体什么时候入职对方还没问到我呢。具体我个人的话,肯定是八九月份就能入职那最好了!
回复

使用道具 举报

我的人缘0
 楼主| Iceinvoker 发表于 2018-6-12 15:13:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (20)
 
 
0% (0)  踩
say543 发表于 2018-6-12 14:38
我的想法是反向建graph 然后从target node bfs 回朔 这样感觉可行
. 留学申请论坛-一亩三分地
你这个想法非常正确,我解的时候也用了相同的方法
回复

使用道具 举报

我的人缘0
Big_Biang 发表于 2018-6-12 17:03:24 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  86% (26)
 
 
13% (4)  踩
Iceinvoker 发表于 2018-6-12 15:11
好问题!我一开始就是这么做的,后来那个小哥就一个劲儿地跟我说你描述的这种情况,我才意识到我想错了, ...

请问一下楼主的方法怎么判断有没有环呀?想了半天感觉还是要先拓扑排序判断一下。
回复

使用道具 举报

我的人缘0
sw7eets 发表于 2018-6-12 21:14:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (11)
 
 
0% (0)  踩
Big_Biang 发表于 2018-6-12 17:03
请问一下楼主的方法怎么判断有没有环呀?想了半天感觉还是要先拓扑排序判断一下。

我也觉得是这样。
回复

使用道具 举报

我的人缘0
laskuma 发表于 2018-6-13 03:14:33 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
Big_Biang 发表于 2018-6-12 17:03. 留学申请论坛-一亩三分地
请问一下楼主的方法怎么判断有没有环呀?想了半天感觉还是要先拓扑排序判断一下。

同样是构建图,从0开始做bfs,我觉得可以用一个set存bfs访问过的节点,如果bfs到已访问的节点就说明存在环,没有解。个人认为直接做拓扑排序不对,如果在非0的dependency部分出现了环,个人理解不应该返回错误,因为还是存在解的。
回复

使用道具 举报

我的人缘0
BeStrong2017 发表于 2018-6-13 10:41:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  98% (85)
 
 
1% (1)  踩
第一题的follow, 最短subsequence需要连续还是不连续的啊?  如果不连续, 感觉完全不是一个做法了就
回复

使用道具 举报

我的人缘0
laskuma 发表于 2018-6-13 10:50:57 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (1)
 
 
0% (0)  踩
Big_Biang 发表于 2018-6-13 10:09
反着bfs的话节点不是按照入度来分层的,用set存访问过的节点来判断环不太对,比如边是(0,1), (0,2), (2,3 ...

多谢大神指出corner case!目前我也还没想出更好的方法。不知道这道题面试官问的时候到底存不存在有环的情况。。。如果不考虑有环的话,入度就不重要了,因为只要求返回最短时间就行了。
回复

使用道具 举报

我的人缘0
houqingniao 发表于 2018-6-13 14:01:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (34)
 
 
8% (3)  踩
Iceinvoker 发表于 2018-6-12 15:11
好问题!我一开始就是这么做的,后来那个小哥就一个劲儿地跟我说你描述的这种情况,我才意识到我想错了, ...

我感觉就是DFS 或者BFS 就可以搞定了~~~有点像那个坐飞机的题
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-8-16 20:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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