FB一面，还是热乎的

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

国人大哥，在FB做mobile js
1. Count Unique Path DP秒之

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

ute-force会比较好
如果要时间，binary-merge会比较好

求onsite！

第二题，用 divide and conquer 挺好的，复杂度跟heap一样，还比用heap要灵活多变。

1. vector<int> mergeKVector(vector<vector<int>> &lists) {
   
2.     vector<int> result;
   
3.     if(lists.empty()) return result;
   
4.     return helper(lists, 0, lists.size() - 1);
   
5. }
   
6. 
   
7. vector<int> helper(vector<vector<int>> &lists, int low, int high) {
   
8.     if(low >= high) return lists[low];
   
9.     int mid = low + (high - low) / 2;
   
10.     vector<int> left = helper(lists, low, mid);
    
11.     vector<int> right = helper(lists, mid + 1, high);
    
12.     return mergeTwoVector(left, right);
    
13. }
    
14. 
    
15. vector<int> mergeTwoVector(vector<int> a, vector<int> b) {
    
16.     vector<int> result(a.size() + b.size(), 0);
    
17.     int i = 0, j = 0;
    
18.     for(int k = 0; k < result.size(); ++k) {
    
19.         if(i < a.size() && j < b.size()) {
    
20.             if(a[i] < b[j]) result[k] = a[i++];
    
21.             else result[k] = b[j++];
    
22.         } else if(i < a.size()) {
    
23.             result[k] = a[i++];
    
24.         } else if(j < b.size()) {
    
25.             result[k] = b[j++];
    
26.         }
    
27.     }
    
28.     return result;
    
29. }
    
30. 
    
31. int  main() {
    
32.     vector<int> v1 = {3, 5, 6, 8, 22, 33, 44, 55};
    
33.     vector<int> v2 = {1, 4, 7, 9, 11, 13, 14 ,15, 18, 35, 61};
    
34.     vector<int> v3 = {1, 2, 10};
    
35.     vector<int> v4 = {20, 30, 40, 50, 60, 70, 80};
    
36. 
    
37.     vector<vector<int>> lists = {v1, v2, v3, v4};
    
38. 
    
39.     vector<int> result = mergeKVector(lists);
    
40. 
    
41.     for(auto l : lists) {
    
42.         for(int n : l) {
    
43.             cout << n << " ";
    
44.         }
    
45.         cout << endl;
    
46.     }
    
47.     for(int r : result) cout << r << " ";
    
48. 
    
49. 
    
50.     return 0;
    
51. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

问下楼主unique path是怎么优化的？

jy_121 发表于 2015-10-24 04:37
问下楼主unique path是怎么优化的？

一行table就够了

补充内容 (2015-10-24 04:48):
因为每一行的更新只和上一行有关

xuchen1m3fd 发表于 2015-10-24 04:44
一行table就够了

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

那不是要保存上一行和当前行吗？两行？

jy_121 发表于 2015-10-24 04:53
那不是要保存上一行和当前行吗？两行？

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

xuchen1m3fd 发表于 2015-10-24 05:03
当前行更新完成之后就变成了上一行，建议自己写出两行的程序，仔细看看就会发现是可以删减的

好的，谢谢了

xuchen1m3fd 发表于 2015-10-24 04:44
一行table就够了

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

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

如果要时间最优， 应该用heap吧， 参看external sort

如果要时间最优， 应该用heap吧， 参看external sort

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies