一亩三分地论坛

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

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

FB一面,还是热乎的

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

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

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

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

x
暑假找人内推,然后当时在intern所以推到了现在,但是现在行情这么不好也是很虚的。。。

国人大哥,在FB做mobile js
1. Count Unique Path DP秒之 O(n*m)
follow up: 减少空间到O(m). Waral 鍗氬鏈夋洿澶氭枃绔,
我当时想了个两行的办法,他问我还能不能减,我说我先写两行的再删代码,同意
写出来以后保证无误,删减为一行

2. Merge K sorted Array: 等同merge k sorted list但是要注意空间复杂度
前面写了十来分钟,不想直接丢最好的idea,于是给了三个idea逐一分析
这里有个trade off
如果要空间,brute-force会比较好
如果要时间,binary-merge会比较好

求onsite!. 鍥磋鎴戜滑@1point 3 acres

评分

2

查看全部评分

jy_121 发表于 2015-10-24 04:37:29 | 显示全部楼层
问下楼主unique path是怎么优化的?
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-24 04:44:43 | 显示全部楼层
jy_121 发表于 2015-10-24 04:37
问下楼主unique path是怎么优化的?

一行table就够了

补充内容 (2015-10-24 04:48):. from: 1point3acres.com/bbs
因为每一行的更新只和上一行有关
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-24 04:53:10 来自手机 | 显示全部楼层
xuchen1m3fd 发表于 2015-10-24 04:44
一行table就够了

补充内容 (2015-10-24 04:48):

那不是要保存上一行和当前行吗?两行?
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-24 05:03:56 | 显示全部楼层
jy_121 发表于 2015-10-24 04:53
那不是要保存上一行和当前行吗?两行?

当前行更新完成之后就变成了上一行,建议自己写出两行的程序,仔细看看就会发现是可以删减的
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-24 05:08:22 来自手机 | 显示全部楼层
xuchen1m3fd 发表于 2015-10-24 05:03
当前行更新完成之后就变成了上一行,建议自己写出两行的程序,仔细看看就会发现是可以删减的

好的,谢谢了
回复 支持 反对

使用道具 举报

dylanwen 发表于 2015-10-24 14:52:40 | 显示全部楼层
xuchen1m3fd 发表于 2015-10-24 04:44
一行table就够了

补充内容 (2015-10-24 04:48):

我还以为lz说这题只要一行代码就能够搞定。顿时震惊了
回复 支持 反对

使用道具 举报

smallshrimp 发表于 2015-10-25 07:49:54 | 显示全部楼层
如果要时间最优, 应该用heap吧, 参看external sort
回复 支持 反对

使用道具 举报

smallshrimp 发表于 2015-10-25 07:50:31 | 显示全部楼层
如果要时间最优, 应该用heap吧, 参看external sort
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-10-25 10:50:19 | 显示全部楼层
请教楼主几个问题,谢谢。. Waral 鍗氬鏈夋洿澶氭枃绔,
1. K sorted array作为参数给你传进来的时候,是用ArrayList<int[]>的方式表示的,还是Object[]的方式表示的,还是ArrayList<ArrayList<Integer>>表示的呢?
2. 楼主提到brute-foce的方法会更加节省空间,你这里的Brute force方法是指先将arr1和arr2合并,再用结果和arr3合并,再用结果和arr4合并,。。。。,最后和arrK合并的方法吗?
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-10-25 11:10:43 | 显示全部楼层
smallshrimp 发表于 2015-10-25 07:50
如果要时间最优, 应该用heap吧, 参看external sort

时间最优用楼主说的binary merge和用heap都是一样的,假设K个数组,平均每个数组长度为m, 时间复杂度都为O( m * K * logK)
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-25 12:53:01 | 显示全部楼层
水逼一枚 发表于 2015-10-25 10:50.1point3acres缃
请教楼主几个问题,谢谢。. visit 1point3acres.com for more.
1. K sorted array作为参数给你传进来的时候,是用ArrayList的方式表示的,还是 ...

不用一个一个合并吧,每次遍历所有Array的头,拿走最小的那个就是了。
回复 支持 反对

使用道具 举报

水逼一枚 发表于 2015-10-25 13:08:26 | 显示全部楼层
snowwolf 发表于 2015-10-25 12:53
不用一个一个合并吧,每次遍历所有Array的头,拿走最小的那个就是了。

恩,我只是在问楼主他说的brute force是什么方法,你说的这个方法拿最小就是用heap做没错吧?只不过这题用heap的话,在元素加入heap前还要做一些操作,要维护元素对应的array和在该array种的index信息。略复杂,我个人认为这题最好的方法是楼主说的binary merge.
回复 支持 反对

使用道具 举报

幸福的小小杏儿 发表于 2015-10-25 13:15:10 | 显示全部楼层
水逼一枚 发表于 2015-10-25 13:08
恩,我只是在问楼主他说的brute force是什么方法,你说的这个方法拿最小就是用heap做没错吧?只不过这题 ...

就把它们都变成linkedlist再做。。。。。
回复 支持 反对

使用道具 举报

snowwolf 发表于 2015-10-25 14:03:12 | 显示全部楼层
水逼一枚 发表于 2015-10-25 13:08-google 1point3acres
恩,我只是在问楼主他说的brute force是什么方法,你说的这个方法拿最小就是用heap做没错吧?只不过这题 ...

brute force的拿走最小,不用heap呀,就直接遍历一遍找最小的那个呀
heap的是O(n*K*log K). Waral 鍗氬鏈夋洿澶氭枃绔,
这个是O(n*K*K)
回复 支持 反对

使用道具 举报

gamespeed 发表于 2015-10-26 00:40:07 | 显示全部楼层
水逼一枚 发表于 2015-10-25 10:50
请教楼主几个问题,谢谢。
1. K sorted array作为参数给你传进来的时候,是用ArrayList的方式表示的,还是 ...

不一定是java吧,取决于你用的什么语言,有可能面试官会让你自己来定
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-26 12:41:42 | 显示全部楼层
水逼一枚 发表于 2015-10-25 10:50
请教楼主几个问题,谢谢。. 鍥磋鎴戜滑@1point 3 acres
1. K sorted array作为参数给你传进来的时候,是用ArrayList的方式表示的,还是 ...

1. int[][]
2. binary merge 就是 [arr1, arr2, arr3, arr4], 先merge 1 2再merge 3 4,再merge上一轮的两个结果,然后时间是O((KL)logK) 假设L是平均长度, 因为外层数组长度只有K,所以递归的层数是logk层。 brute-force是全部丢进heap,这样时间是O((KL)log(KL))。还是有区别的
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-26 12:42:20 | 显示全部楼层
snowwolf 发表于 2015-10-25 12:53
不用一个一个合并吧,每次遍历所有Array的头,拿走最小的那个就是了。

这样的话时间是O(K^2*L),复杂度很高,我也提到了这么但是最后写的不是这个
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-26 12:43:16 | 显示全部楼层
幸福的小小杏儿 发表于 2015-10-25 13:15
就把它们都变成linkedlist再做。。。。。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
我并不觉得面试官想让我们把这题变成链表,因为两者没有区别,如果你这么做很容易引起怀疑吧?
回复 支持 反对

使用道具 举报

 楼主| xuchen1m3fd 发表于 2015-10-26 12:47:05 | 显示全部楼层
snowwolf 发表于 2015-10-25 14:03
brute force的拿走最小,不用heap呀,就直接遍历一遍找最小的那个呀
heap的是O(n*K*log K)
这个是O(n*K ...

bruteforce其实是两种,一种是全部扔进heap一种是遍历头找最小,两种复杂度不一样。但是heap不是O(KLlogKL)吗?还是说层主的方法是维护一个大小为k的heap,我觉得这个方法在维护大小的时候可能略复杂,我面试的时候是直接套用了mergeKSortedList的最优解,个人觉得代码量比较小。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 03:53

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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