周末读物之聊聊三观

一亩三分地论坛

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

最近看过此主题的会员

坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
前Google华人高管创立
面试offer一键直通
Leap.ai助你进入热门独角兽
查看: 7554|回复: 30
收起左侧

脸家10.17实习第二轮电面

[复制链接] |试试Instant~
我的人缘0
yeyelovenimo 发表于 2016-10-18 03:12:54 | 显示全部楼层 |阅读模式
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩

2016(10-12月) 码农类General 博士 实习@Facebook - 内推 - 技术电面  | Pass | 其他

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

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

x
Convert binray search tree to circular doubly linkedlist.本文原创自1point3acres论坛
面经里的老题了, lintcode也有类似的题, 只是不要求circular
. from: 1point3acres http://www.lintcode.com/en/probl ... doubly-linked-list/. From 1point 3acres bbs
一面面经在这里, 虽然code很messy而且写出了bug, 但好在是国人小哥, lol
http://www.1point3acres.com/bbs/thread-205369-2-1.html

面完一小时就说进pool了,太喜欢脸家的效率,尤其是跟某家相比,大家都懂的,咳咳
-google 1point3acres
以下是流水账......
一接电话是印度小哥, 感觉略慌.本文原创自1point3acres论坛
大概20分钟做完题, 就开始脑跑test case,跑完一个又来一个,大概印度小哥觉得我的方法不对? 来源一亩.三分地论坛.
发现code木有问题之后就开始refactoring,把repeated code写成function,开始没明白想让我干嘛耽误了一点时间
最后还有10分钟问follow up, 说如果是balanced bst应该怎么优化?我有点懵逼, 之前的code是O(n) time, O(h) space, 如果bst是balanced, 只是h = log(n), 还能有更好的算法优化么?
沉默了一会儿印度小哥说你想想如果有多个thread, 恍然大悟原来是想让我parallel啊, 于是立马说, 左子树右子树分thread算然后再合并, 之后被问到时间空间复杂度和需要多少个thread

评分

参与人数 1大米 +3 收起 理由
bych0223 + 3 感谢分享!

查看全部评分


上一篇:来报一个上周的Facebook电面
下一篇:Facebook第二轮电面10/17
我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-19 06:40:34 | 显示全部楼层
本楼: 【顶】   100% (1)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
knight0clk 发表于 2016-10-19 03:43
楼主,我也不太理解为什么space是O(1)。感觉每个thread处理一个node,每个node至少建立一个list node,空 ...

估计是我没说清楚, 之前TreeNode的定义是
Node {
.留学论坛-一亩-三分地 int val;
Node left, right;
}
改成doubly linkedlist的时候并不新建ListNode, 而是更改left, right指针, left相当于prev, right相当于next, 所以space是constant
回复

使用道具 举报

我的人缘0
wtcupup 发表于 2016-10-18 03:17:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  61% (346)
 
 
38% (215)  踩
博士还有第三轮的吧。。。目测是project dive
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-18 03:21:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
wtcupup 发表于 2016-10-18 03:17
博士还有第三轮的吧。。。目测是project dive

第三轮就是team match了,求好运
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 03:26:01 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
yeyelovenimo 发表于 2016-10-18 03:21
第三轮就是team match了,求好运
. From 1point 3acres bbs
最后多线程的时间空间复杂度该怎么答呀?需要多少个thread的呢?

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
 楼主| yeyelovenimo 发表于 2016-10-18 03:30:56 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
iPhD 发表于 2016-10-18 03:26
最后多线程的时间空间复杂度该怎么答呀?需要多少个thread的呢?

时间复杂度是O(lgn), 空间复杂度是O(1), 我答得是需要number of leaves个thread, 但感觉不对, 应该是number of leaves/2个因为leave不用处理
回复

使用道具 举报

我的人缘0
iPhD 发表于 2016-10-18 03:35:55 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  87% (61)
 
 
12% (9)  踩
yeyelovenimo 发表于 2016-10-18 03:30
时间复杂度是O(lgn), 空间复杂度是O(1), 我答得是需要number of leaves个thread, 但感觉不对, 应该是 ...

楼主用的是哪种方法做的?是先整个转化成一个doubly linked list,最后转化成circular?还是每一次递归返回的值就是circular的?
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-18 04:40:07 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
iPhD 发表于 2016-10-18 03:35.本文原创自1point3acres论坛
楼主用的是哪种方法做的?是先整个转化成一个doubly linked list,最后转化成circular?还是每一次递归返 ...

我用的stack, 就inorder traversal一遍然后把尾接到头就好
回复

使用道具 举报

我的人缘0
celtspirit 发表于 2016-10-18 08:30:23 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  100% (18)
 
 
0% (0)  踩
yeyelovenimo 发表于 2016-10-18 03:30
时间复杂度是O(lgn), 空间复杂度是O(1), 我答得是需要number of leaves个thread, 但感觉不对, 应该是 ...

可以麻烦解释一下为什么是O(lgn)么。是每次遇到新的节点就把左右subtree放入新的thread里面么?感觉空间也不是constant的吧,新建thread不需要空间么?
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-18 14:15:15 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
celtspirit 发表于 2016-10-18 08:30
可以麻烦解释一下为什么是O(lgn)么。是每次遇到新的节点就把左右subtree放入新的thread里面么?感觉空间 ...

是左子树放到一个thread, 右子树放到一个thread, 再用constant的time接起来, assumption是有不限制的thread stand by
回复

使用道具 举报

我的人缘1
smellycat 发表于 2016-10-18 22:41:27 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  88% (182)
 
 
11% (23)  踩
PhD要team match么?那master用不用呀?怎么知道自己进没进pool呀?

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

回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-18 23:55:06 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
smellycat 发表于 2016-10-18 22:41
PhD要team match么?那master用不用呀?怎么知道自己进没进pool呀?

只有PhD要,hr发邮件说进入team match process, master过了直接拿offer了
回复

使用道具 举报

我的人缘0
kiru 发表于 2016-10-19 00:01:36 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  96% (25)
 
 
3% (1)  踩
请问lz是自己投的,还是内推呀
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-10-19 02:21:54 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
kiru 发表于 2016-10-19 00:01
请问lz是自己投的,还是内推呀
. 1point3acres
我是内推的
回复

使用道具 举报

我的人缘0
knight0clk 发表于 2016-10-19 03:43:13 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  91% (91)
 
 
9% (9)  踩
yeyelovenimo 发表于 2016-10-18 14:15
是左子树放到一个thread, 右子树放到一个thread, 再用constant的time接起来, assumption是有不限制的th ...

楼主,我也不太理解为什么space是O(1)。感觉每个thread处理一个node,每个node至少建立一个list node,空间是O(n),感觉只能时间减少时间,空间无法优化吧?
回复

使用道具 举报

我的人缘0
hongshaoqiezi 发表于 2016-11-1 06:39:26 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  71% (78)
 
 
28% (31)  踩
话说楼主已经match上了吗?
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-11-1 06:41:52 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
hongshaoqiezi 发表于 2016-11-1 06:39
话说楼主已经match上了吗?

还没,才约好host match interview
回复

使用道具 举报

我的人缘0
hongshaoqiezi 发表于 2016-11-1 06:56:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  71% (78)
 
 
28% (31)  踩
楼主能介绍一下约好host match i流程吗?我通知jinlepool后,被转给另一个叫Maggie Kemper的,有几天了,我给她发邮件不回呀,怎么破?你是主动出击联系组吗,还是等着人事联系?
回复

使用道具 举报

我的人缘0
 楼主| yeyelovenimo 发表于 2016-11-1 07:22:46 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  97% (39)
 
 
2% (1)  踩
hongshaoqiezi 发表于 2016-11-1 06:56
楼主能介绍一下约好host match i流程吗?我通知jinlepool后,被转给另一个叫Maggie Kemper的,有几天了,我 ...

我也是她,过了好久才联系我,我就等着,也可以催催吧
回复

使用道具 举报

我的人缘0
hongshaoqiezi 发表于 2016-11-1 07:27:29 | 显示全部楼层
本楼: 【顶】   0% (0)
 
 
0% (0)   【踩】
全局: 顶  71% (78)
 
 
28% (31)  踩
谢谢了,感觉找实习就一直在各种等的节奏
回复

使用道具 举报

游客
请先登录

本版积分规则

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

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

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

GMT+8, 2018-9-22 15:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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