一亩三分地论坛

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

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

FB 电面 10/20/2015

[复制链接] |试试Instant~ |关注本帖
lightmark 发表于 2015-10-24 01:11:25 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 博士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
一开始废话讲太多了。。。还剩20min

1.Given two inputs, lists or arrays of sorted integers
Write a method to return a list or array of sorted integers containing all the integers in the two inputs
Can assume that there are no duplicate integers 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
Example:
input1: 1 3 6 9
input2: 2 3 4
output: 1 2 3 4 6 9.1point3acres缃



2. Instead of 2 inputs, lets handle k inputs. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
Output would be the sorted array/vector containing all the elements in the k inputs

收到onsite了。

评分

1

查看全部评分

akluffy 发表于 2015-10-31 12:49:16 | 显示全部楼层
follow up就一个吗
回复 支持 1 反对 0

使用道具 举报

gamespeed 发表于 2015-10-26 06:49:09 | 显示全部楼层
恭喜楼主!过两天我也要电面他家。第一题我觉得应该是两个指针,每次找较小的输出并右移那个指针,如果相等就只输出一个并右移两个指针,复杂度O(N)。第二题用heap放所有array,heap以每个array最后的元素排序,每次取最的顶部元素输出,所有顶部元素与这个元素相等的array都pop_back把最后一个元素去掉。第二题从最后开始输出的原因是array从尾部去掉一个元素的复杂度是O(1),从头部去掉元素的复杂度是O(N)因为要移动其他所有元素。
回复 支持 1 反对 0

使用道具 举报

gamespeed 发表于 2015-10-27 03:51:39 | 显示全部楼层
haifengc 发表于 2015-10-27 01:01
我想问的是,没有答辩就没有毕业,可以先全职工作吗?是用OPT吗,OPT不是毕业之后才能用吗?谢谢。

phd好像可以的,只要把该修的课、research学分之类搞定,然后毕业课题搞的差不多,老板同意就行

当然应该也要看学校和系里的政策吧

OPT的要求并不是毕业,而是满足了program的毕业要求即可

补充内容 (2015-10-27 03:56):
具体还是得跟学校的国际办公室问问,有些细节东西不清楚不行
回复 支持 1 反对 0

使用道具 举报

AndrewFish 发表于 2015-10-26 07:41:34 | 显示全部楼层
gamespeed 发表于 2015-10-25 15:49. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
恭喜楼主!过两天我也要电面他家。第一题我觉得应该是两个指针,每次找较小的输出并右移那个指针,如果相等 ...

把k 个序列两两归并,然后把归并后的结果再两两归并不就可以了吗,时间复杂度是O(nk),用heap能比这更快吗?
回复 支持 反对

使用道具 举报

theocrasy 发表于 2015-10-26 07:48:04 | 显示全部楼层
大牛四年就UIUC PHD毕业了?? 拜。。。。
回复 支持 反对

使用道具 举报

theocrasy 发表于 2015-10-26 07:48:10 | 显示全部楼层
大牛四年就UIUC PHD毕业了?? 拜。。。。
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 09:03:08 | 显示全部楼层
theocrasy 发表于 2015-10-26 07:48
大牛四年就UIUC PHD毕业了?? 拜。。。。

quit~~~~~~~
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 09:05:55 | 显示全部楼层
AndrewFish 发表于 2015-10-26 07:41
把k 个序列两两归并,然后把归并后的结果再两两归并不就可以了吗,时间复杂度是O(nk),用heap能比这更快吗 ...

我也是这样做的。heap当然也可以复杂度应该是一样的不过heap做法更适用于linked list~
况且divide and conquer更scalable
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 09:22:07 | 显示全部楼层
gamespeed 发表于 2015-10-26 06:49
恭喜楼主!过两天我也要电面他家。第一题我觉得应该是两个指针,每次找较小的输出并右移那个指针,如果相等 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你放array不如放vector的iterator了
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 10:20:22 | 显示全部楼层
AndrewFish 发表于 2015-10-26 07:41
把k 个序列两两归并,然后把归并后的结果再两两归并不就可以了吗,时间复杂度是O(nk),用heap能比这更快吗 ...

鏉ユ簮涓浜.涓夊垎鍦拌鍧. 归并两个序列的复杂度是O(N),N是序列大小。O(k)次序列归并,复杂度是O(k)。但这个地方由于每次归并导致新的序列尺寸x2,所以总的复杂度高于O(Nk),应该是O(N k log k)。可以想像一个类似完全二叉树由底层向顶层走,每向上归并一层,复杂度都是O(Nk),树的层数是log k,所以总体复杂度O(N k log k)。

用heap的话,每次要从heap中取一个最大/小值,从序列中去掉这个值,再把序列放回heap,复杂度为O(k);总共有O(Nk)个数,所以重复操作的结果,总体复杂度同样是O(N k log k)。
. from: 1point3acres.com/bbs
上面说的是时间复杂度。空间复杂度的话,归并时“可能”会用到最多O(Nk)额外存储(如果算法够牛的话也许不用),heap的话额外存储是O(k)用于heap
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 10:25:59 | 显示全部楼层
lightmark 发表于 2015-10-26 09:22
你放array不如放vector的iterator了

我写这个码的时候会把vector的指针放heap里。PS:我面试是用C++,但是其实平时是写C的,所以有些C++ STL其实用的不算精。PPS:我想了想,如果放的是iterator,每次取出再放回时只要做++操作即可,可是要如何判断是否把一个vector遍历完了呢?

话说我是UIC五年quit了的,握抓……

祝你onsite好运,另求问楼主现在offer攒的如何了
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 10:29:12 | 显示全部楼层
gamespeed 发表于 2015-10-26 10:25
我写这个码的时候会把vector的指针放heap里。PS:我面试是用C++,但是其实平时是写C的,所以有些C++ STL ...

忘了。那就放一个pair好了。second是end。.1point3acres缃
没offer呢,找的晚~~~就两个onsite和一些phone
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 10:32:12 | 显示全部楼层
gamespeed 发表于 2015-10-26 10:20
归并两个序列的复杂度是O(N),N是序列大小。O(k)次序列归并,复杂度是O(k)。但这个地方由于每次归并导致 ...

heap的话最后的结果也是O(NK)的space吧。而resursion是每层都用O(NK)其实也是O(NK)
回复 支持 反对

使用道具 举报

 楼主| lightmark 发表于 2015-10-26 10:32:36 | 显示全部楼层
gamespeed 发表于 2015-10-26 10:25
我写这个码的时候会把vector的指针放heap里。PS:我面试是用C++,但是其实平时是写C的,所以有些C++ STL ...

给五年跪了
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 10:37:05 | 显示全部楼层
lightmark 发表于 2015-10-26 10:32
heap的话最后的结果也是O(NK)的space吧。而resursion是每层都用O(NK)其实也是O(NK)

如果考虑要存结果,那么确实是O(Nk);如果允许直接输出结果,就不用这部分存储,仅仅需要heap的存储。
归并的话,有可能需要额外一倍的存储,即O(Nk).1point3acres缃
条件不同,结论就不同。
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 10:39:30 | 显示全部楼层
lightmark 发表于 2015-10-26 10:29. From 1point 3acres bbs
忘了。那就放一个pair好了。second是end。
没offer呢,找的晚~~~就两个onsite和一些phone

我记得我面试时候好像被问过原题(好像是G的onsite?),当时我说的是heap里存pointer,然后每次从vector最后取元素,pop_back。这样虽然是可以省一点heap的尺寸,但是缺点是它改变了输入的值。不过当时面试官也没觉得不妥
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 10:42:34 | 显示全部楼层

我们大师兄都超过8年了,这周都入职了,还没答辩呢,希望他能这学期搞定……
我算上这学期的话,就5.5年了,到时拿MS走人,还是好容易求来的
回复 支持 反对

使用道具 举报

haifengc 发表于 2015-10-27 01:01:37 | 显示全部楼层
gamespeed 发表于 2015-10-26 10:42. 鍥磋鎴戜滑@1point 3 acres
我们大师兄都超过8年了,这周都入职了,还没答辩呢,希望他能这学期搞定……
我算上这学期的话,就5.5年 ...

我想问的是,没有答辩就没有毕业,可以先全职工作吗?是用OPT吗,OPT不是毕业之后才能用吗?谢谢。
回复 支持 反对

使用道具 举报

theocrasy 发表于 2015-10-27 06:02:24 | 显示全部楼层
gamespeed 发表于 2015-10-26 10:42.鐣欏璁哄潧-涓浜-涓夊垎鍦
我们大师兄都超过8年了,这周都入职了,还没答辩呢,希望他能这学期搞定……
我算上这学期的话,就5.5年 ...

这都干嘛呀。。这么好的前途要quit。。。将来公司也不知道你是quit PHD的MS还是普通入学的MS 之前的训练不就荒废了多可惜啊。。。
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-27 09:45:32 | 显示全部楼层
haifengc 发表于 2015-10-27 01:01
我想问的是,没有答辩就没有毕业,可以先全职工作吗?是用OPT吗,OPT不是毕业之后才能用吗?谢谢。

可以。如果你感兴趣可以问问你们学校国际办公室,OPT这块确实不是看是否毕业而是是否满足了degree requirement之类的,区别有点tricky。我是问了我们OIS才搞懂的
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 05:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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