facebook电面

第一轮电面move zero ，问了complexity。
follow up： 如果只需要把非0的数移到左边，而不care右边是什么数要怎么做。举例 2，0，0，1，3，0，5，输出2，1，3，5，*，*

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

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

ook家很喜欢问复杂度问题，而且需要解释清楚不是随便说个O就可以的。

跪求onsite！！

blackrose 发表于 2016-6-12 13:32
谢谢你的好心，我压根没说我不会，只不过说了句 code需要点时间。。。。。

就这样吧 在这帖子里跟你理论真没有什么意义 加油吧 能实现出来就好啊 写个解题报告 特别能帮你提高解决类似题目的效率

blackrose 发表于 2016-6-10 06:12
恩，就是这么写的，存下来M个start 和 end， 但是感觉这么些，半个小时写不完的样子。。。还不算压力情况 ...

你会用堆吗？

练习了一下第二问，跑了几个简单case，没有问题，不知道有没有bug。

1. vector<int> sort(vector<int>& nums) {
   
2.         int size = nums.size();
   
3.         vector<int> res;
   
4.         if (size == 0) return res;
   
5.    
   
6.         //min heap, element is pair of <num, idx>
   
7.         priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int,int>>> Q;
   
8.         Q.push(make_pair(nums[0], 0));
   
9. 
   
10.         //The next index of ending point
    
11.         unordered_set<int> endIdx;
    
12.         for(int i = 0; i < size - 1; ++i) {
    
13.                 //Find the boundary of sub-arrays
    
14.                 if (nums[i] > nums[i+1]) {
    
15.                            endIdx.insert(i+1);
    
16.                            //push the first element of the next sub-array to heap
    
17.                            Q.push(make_pair(nums[i+1], i+1));      
    
18.           }
    
19.      }
    
20.      endIdx.insert(size);
    
21. 
    
22.     while(res.size() < size) {
    
23.               int val = Q.top().first;
    
24.        int idx = Q.top().second;
    
25.               Q.pop();
    
26.               res.push_back(val);
    
27.               ++idx;
    
28.              //Check if we have reached the end of current sub array
    
29.               if (endIdx.count(idx) == 0)
    
30.                        Q.push(make_pair(nums[idx], idx));   
    
31.        }
    
32.         return res;
    
33. }

复制代码

二面那个题有意思。

第二个题写了有一会儿，还写的很乱，楼主有代码没

blackrose 发表于 2016-6-10 05:16
第二个题写了有一会儿，还写的很乱，楼主有代码没

用M个指针存每个有序segment的起始位置，然后按照K路归并的思路

forteller 发表于 2016-6-10 05:28
用M个指针存每个有序segment的起始位置，然后按照K路归并的思路

恩，就是这么写的，存下来M个start 和 end， 但是感觉这么些，半个小时写不完的样子。。。还不算压力情况吓。。。。

forteller 发表于 2016-6-11 14:50
你会用堆吗？

不明白 什么意思

blackrose 发表于 2016-6-11 23:00
不明白 什么意思

max heap min heap知道吗

forteller 发表于 2016-6-12 04:34
max heap min heap知道吗

即使知道也要code一阵阿。而且要先找出来M个断点。。。。我太挫，你是大神