一亩三分地论坛

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

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

脸家10.17实习第二轮电面

[复制链接] |试试Instant~ |关注本帖
yeyelovenimo 发表于 2016-10-18 03:12:54 | 显示全部楼层 |阅读模式

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

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

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

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

面完一小时就说进pool了,太喜欢脸家的效率,尤其是跟某家相比,大家都懂的,咳咳. more info on 1point3acres.com

以下是流水账......
一接电话是印度小哥, 感觉略慌
大概20分钟做完题, 就开始脑跑test case,跑完一个又来一个,大概印度小哥觉得我的方法不对?. visit 1point3acres.com for more.
发现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

查看全部评分

wtcupup 发表于 2016-10-18 03:17:07 | 显示全部楼层
博士还有第三轮的吧。。。目测是project dive
回复 支持 反对

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-18 03:21:06 | 显示全部楼层
wtcupup 发表于 2016-10-18 03:17
博士还有第三轮的吧。。。目测是project dive

第三轮就是team match了,求好运
回复 支持 反对

使用道具 举报

iPhD 发表于 2016-10-18 03:26:01 | 显示全部楼层
yeyelovenimo 发表于 2016-10-18 03:21
第三轮就是team match了,求好运

最后多线程的时间空间复杂度该怎么答呀?需要多少个thread的呢?
回复 支持 反对

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-18 03:30:56 | 显示全部楼层
iPhD 发表于 2016-10-18 03:26
最后多线程的时间空间复杂度该怎么答呀?需要多少个thread的呢?

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

使用道具 举报

iPhD 发表于 2016-10-18 03:35:55 | 显示全部楼层
yeyelovenimo 发表于 2016-10-18 03:30
时间复杂度是O(lgn), 空间复杂度是O(1), 我答得是需要number of leaves个thread, 但感觉不对, 应该是 ...

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

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-18 04:40:07 | 显示全部楼层
iPhD 发表于 2016-10-18 03:35
楼主用的是哪种方法做的?是先整个转化成一个doubly linked list,最后转化成circular?还是每一次递归返 ...

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

使用道具 举报

celtspirit 发表于 2016-10-18 08:30:23 | 显示全部楼层
yeyelovenimo 发表于 2016-10-18 03:30. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
时间复杂度是O(lgn), 空间复杂度是O(1), 我答得是需要number of leaves个thread, 但感觉不对, 应该是 ...

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

使用道具 举报

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

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

使用道具 举报

smellycat 发表于 2016-10-18 22:41:27 | 显示全部楼层
PhD要team match么?那master用不用呀?怎么知道自己进没进pool呀?
回复 支持 反对

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-18 23:55:06 | 显示全部楼层
smellycat 发表于 2016-10-18 22:41
PhD要team match么?那master用不用呀?怎么知道自己进没进pool呀?

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

使用道具 举报

kiru 发表于 2016-10-19 00:01:36 | 显示全部楼层
请问lz是自己投的,还是内推呀
回复 支持 反对

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-19 02:21:54 | 显示全部楼层
kiru 发表于 2016-10-19 00:01. more info on 1point3acres.com
请问lz是自己投的,还是内推呀

我是内推的
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-10-19 03:43:13 | 显示全部楼层
yeyelovenimo 发表于 2016-10-18 14:15
是左子树放到一个thread, 右子树放到一个thread, 再用constant的time接起来, assumption是有不限制的th ...

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

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-19 06:40:34 | 显示全部楼层
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
回复 支持 反对

使用道具 举报

hongshaoqiezi 发表于 2016-11-1 06:39:26 | 显示全部楼层
话说楼主已经match上了吗?
回复 支持 反对

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-11-1 06:41:52 | 显示全部楼层
hongshaoqiezi 发表于 2016-11-1 06:39
话说楼主已经match上了吗?

还没,才约好host match interview
回复 支持 反对

使用道具 举报

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

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-11-1 07:22:46 | 显示全部楼层
hongshaoqiezi 发表于 2016-11-1 06:56
楼主能介绍一下约好host match i流程吗?我通知jinlepool后,被转给另一个叫Maggie Kemper的,有几天了,我 ...
. From 1point 3acres bbs
我也是她,过了好久才联系我,我就等着,也可以催催吧
回复 支持 反对

使用道具 举报

hongshaoqiezi 发表于 2016-11-1 07:27:29 | 显示全部楼层
谢谢了,感觉找实习就一直在各种等的节奏
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 21:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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