《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 7035|回复: 30
收起左侧

脸家10.17实习第二轮电面

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

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

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

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

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

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

以下是流水账......
一接电话是印度小哥, 感觉略慌
大概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

查看全部评分

 楼主| yeyelovenimo 发表于 2016-10-19 06:40:34 | 显示全部楼层
knight0clk 发表于 2016-10-19 03:43.1point3acres缃
楼主,我也不太理解为什么space是O(1)。感觉每个thread处理一个node,每个node至少建立一个list node,空 ...

. From 1point 3acres bbs估计是我没说清楚, 之前TreeNode的定义是
Node {
int val;. 1point 3acres 璁哄潧
Node left, right;
}
改成doubly linkedlist的时候并不新建ListNode, 而是更改left, right指针, left相当于prev, right相当于next, 所以space是constant
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| yeyelovenimo 发表于 2016-10-18 03:21:06 | 显示全部楼层
wtcupup 发表于 2016-10-18 03:17
博士还有第三轮的吧。。。目测是project dive
. Waral 鍗氬鏈夋洿澶氭枃绔,
第三轮就是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.鏈枃鍘熷垱鑷1point3acres璁哄潧
最后多线程的时间空间复杂度该怎么答呀?需要多少个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
请问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),感觉只能时间减少时间,空间无法优化吧?
回复 支持 反对

使用道具 举报

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的,有几天了,我 ...

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-22 03:34

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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