一亩三分地论坛

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

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

Facebook第一轮Onsite(相当于电面)

[复制链接] |试试Instant~ |关注本帖
jimmyzzxhlh 发表于 2016-6-25 01:46:34 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 Onsite |Fail其他

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

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

x
首先建议如果第一轮能电面的话最好还是电面,本来想去参观一下office的,但第一轮需要在45分钟内完成2道coding,去掉互相介绍和提问的环节可能就只剩下半小时,白板上要写出2道bug free的code几乎不太可能,除非以前见过。。题目是给定一个list of sorted integer arrays,要求找所有的数的median
e.g. [1,3,6,7,9], [2,4], [5], return 5


. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-7-18 23:44):
第二个数组应该是[2,4,8],这样median是5

评分

2

查看全部评分

窗外一棵树 发表于 2016-7-19 03:12:26 | 显示全部楼层
jimmyzzxhlh 发表于 2016-7-18 23:46
用heap是可以的,只不过我当时想和实现花的时间久了点

大概想了下,有不对的地方请指正~. 1point 3acres 璁哄潧
可以用heap在O(n)时间内搞定,n为一共元素的数量,但我们heap不用维护全部元素,只用维护m个就好了(m是array的数量),但前提是我们得把给定的元素转化成linked list,想法有点借鉴leetcode 23, merge  k sorted list那道题。 不过这样的话空间复杂度就做不到O(1)了,需要O(n)

个人感觉这题不是想让我们把所有元素直接丢进heap,因为给我们的是sorted array,这个sorted肯定是可以利用的。

评分

1

查看全部评分

回复 支持 0 反对 2

使用道具 举报

readman 发表于 2016-6-26 10:47:14 | 显示全部楼层
我也同意使用 priority queue, 然后 lgk
回复 支持 1 反对 0

使用道具 举报

mnmunknown 发表于 2016-6-25 02:01:41 | 显示全部楼层
Order Statistics ?
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-6-25 02:56:07 | 显示全部楼层
对空间有要求么?要constant space吧。。
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-6-25 03:14:56 | 显示全部楼层
leetcode 4变种
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-6-25 03:53:01 | 显示全部楼层
zpinthehouse 发表于 2016-6-25 02:56
对空间有要求么?要constant space吧。。

空间一定是越小越好,constant space要怎么做?我当时用的是heap,只是一开始没想清楚heap里面的结构
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-6-25 04:18:55 | 显示全部楼层
jimmyzzxhlh 发表于 2016-6-25 03:53
空间一定是越小越好,constant space要怎么做?我当时用的是heap,只是一开始没想清楚heap里面的结构

如果heap的话,你放的是一个median-length pair么?就是每个array的median和length然后根据median sort?这样感觉length是偶数处理起来容易出错,不过heap的复杂度是klog(k),应该是最低的。。

constant space我也不知道。。LT4是binary search,不过那就两个array。。

补充内容 (2016-6-25 04:25):
好像这样搞不对。。
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-6-25 04:25:12 | 显示全部楼层
zpinthehouse 发表于 2016-6-25 04:18
如果heap的话,你放的是一个median-length pair么?就是每个array的median和length然后根据median sort? ...

好像这样搞不对。。楼主怎么做的。。
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-6-25 04:27:05 | 显示全部楼层
zpinthehouse 发表于 2016-6-25 04:18
如果heap的话,你放的是一个median-length pair么?就是每个array的median和length然后根据median sort? ...

LT上面那个binary search要考虑很多种情况,还蛮复杂的
heap的关键就是放什么东西进去,一开始面试官提示我说放一个data structure,我误解了以为他说我用heap不对,后来才想到是要我建一个class放到heap里去

补充内容 (2016-6-25 04:31):
其实就是要放三个东西,两个pointer,一个pointer表示当前array在list里面的index,一个pointer表示当前array里面的index,还有一个存指向的value,用这个value作为heap的比较对象. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

补充内容 (2016-6-25 05:48):
我曾经提过skip每个median,被面试官直接否决,说不用在这个路上浪费时间囧

补充内容 (2016-6-25 05:49):
打错,上面是说extract每个median
回复 支持 反对

使用道具 举报

zpinthehouse 发表于 2016-6-25 10:22:51 | 显示全部楼层
jimmyzzxhlh 发表于 2016-6-25 04:27
LT上面那个binary search要考虑很多种情况,还蛮复杂的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
heap的关键就是放什么东西进去,一开始面试官提 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
恩。。明白了。。多谢分享。。
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-6-25 20:13:45 | 显示全部楼层
jimmyzzxhlh 发表于 2016-6-25 04:27
LT上面那个binary search要考虑很多种情况,还蛮复杂的
heap的关键就是放什么东西进去,一开始面试官提 ...
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
那就是Merge k sorted list 加一个counter的方法吧。
如果扩展median of two sorted arrays的思路, 比如median of three sorted arrays, 貌似对原版本做些改进还是可以的。不知道n sorted是不是太复杂了?
回复 支持 反对

使用道具 举报

weitongg 发表于 2016-6-25 20:42:47 | 显示全部楼层
可不可以将三个数组的元素都放到priorityqueue里 然后弹出的第(len-1)/2个元素为所求?
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-6-26 00:17:25 | 显示全部楼层
weitongg 发表于 2016-6-25 20:42
可不可以将三个数组的元素都放到priorityqueue里 然后弹出的第(len-1)/2个元素为所求?

复杂度会上升到O(NlogN), N是所有的元素个数
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-6-26 00:20:54 | 显示全部楼层
Fustang 发表于 2016-6-25 20:13
那就是Merge k sorted list 加一个counter的方法吧。
如果扩展median of two sorted arrays的思路, 比如 ...

能不能说说如何扩展?
回复 支持 反对

使用道具 举报

Fustang 发表于 2016-6-26 00:43:25 | 显示全部楼层
jimmyzzxhlh 发表于 2016-6-26 00:20
能不能说说如何扩展?

并不是很确定哈
如果用findkth的方法做median of two sorted arrays:. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
https://leetcode.com/discuss/673 ... ed-on-binary-search
two sorted arrays时findkth是每次get rid of k/2;那么如果有三个arrays就换成每次recursion get rid of k/3个?
回复 支持 反对

使用道具 举报

ScottShao 发表于 2016-6-26 01:09:42 | 显示全部楼层
可以用merge sort + heap。
给每个array记录一个crt index,然后每次把这个index上的数加到heap里,然后从heap里取出最小的,一直到得到median。. visit 1point3acres.com for more.
复杂度是Nlogk, N是所有数组元素总和 的大小,k是array数。
回复 支持 反对

使用道具 举报

ScottShao 发表于 2016-6-26 01:13:59 | 显示全部楼层
ScottShao 发表于 2016-6-26 01:09
可以用merge sort + heap。
给每个array记录一个crt index,然后每次把这个index上的数加到heap里,然后从 ...

空间复杂度是k。 感觉可能有O(N)的办法。
回复 支持 反对

使用道具 举报

peterzhang45 发表于 2016-6-26 01:44:15 | 显示全部楼层
请问一下lz 一般onsite写白板或者店面写notepad对语言有要求吗 可以用python吗
回复 支持 反对

使用道具 举报

 楼主| jimmyzzxhlh 发表于 2016-6-26 09:22:15 | 显示全部楼层
peterzhang45 发表于 2016-6-26 01:44
请问一下lz 一般onsite写白板或者店面写notepad对语言有要求吗 可以用python吗

一般应该没有,python应该写起来会更简洁
回复 支持 反对

使用道具 举报

hanzhang 发表于 2016-6-27 06:42:40 | 显示全部楼层
如果只是一次操作找median,并且lists是静态的话,我觉得可以
算出所有lists的totelLength,如果是奇数的话,(len+1)/2就是median,偶数的话len/2,len/2+1的mean是median
然后类似merge的方法,但是不merge lists,只是count已经visit的node数,按照以上方法直接算出median。
O(1) space, O(n) time
当然如果lists是动态的话不能用这种方法
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 09:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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