FB新鲜出炉的电面

第一轮电面：1. LC 191 Number of 1 Bits
2. 给2D平面上的N个点，求离

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

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

16-6-7 23:14):
已经拿到onsite

感觉，如果最近的k个点那道题只要求用heap解决就行的话，这几道题都好良心啊。。希望遇到这难度的题。。
quick select本身就挺麻烦，放这道题里更麻烦。。虽然是O(n)

laonawuli 发表于 2016-6-5 11:45
·1. 有一个数组，里面有0和非0元素，要求把所有非0元素移动到数组的前端，并返回非0元素的个数，非零元素 ...

感觉两个pointer， 左边找第一个0， 右边找第一个非0， 两边推进

laonawuli 发表于 2016-6-5 11:57
卧槽这题怎么O(n)? 不应该是 nLogn么

补充内容 (2016-6-4 19:58):

nlogk是用堆的，O(n)的是用快排的partition。每次随机抽取一个元素，把数组分为小于这个元素和大于这个元素的两个部分，这样，由于是随机的抽取的，期望就是把数组平均分成两半，所以T(n) = T(n / 2) + O(n)。根据主定理，T(n) = O(n)。可以参考一下我LC这道题的代码。

1. import java.util.Random;
   
2. 
   
3. public class Solution {
   
4.    
   
5.     Random r = new Random();
   
6.    
   
7.     private void swap(int[] nums, int i, int j) {
   
8.         int t = nums[i];
   
9.         nums[i] = nums[j];
   
10.         nums[j] = t;
    
11.     }
    
12.    
    
13.     private int kth(int[] nums, int left, int right, int k) {
    
14.         int i = left, n = right;
    
15.         int mid = r.nextInt(right - left + 1) + left;
    
16.         int pivot = nums[mid];
    
17.         for(int j = left; j <= n;) {
    
18.             if(nums[j] > pivot) swap(nums, i++, j++);
    
19.             else if(nums[j] < pivot) swap(nums, j, n--);
    
20.             else ++j;
    
21.         }
    
22.         if(k + left < i) return kth(nums, left, i - 1, k);
    
23.         else if(k + left <= n) return nums[k + left];
    
24.         else return kth(nums, n + 1, right, k - (n - left + 1));
    
25.     }
    
26.    
    
27.     public int findKthLargest(int[] nums, int k) {
    
28.         return kth(nums, 0, nums.length - 1, k - 1);
    
29.     }
    
30. }

复制代码

请问楼主第二题怎么弄的？

laonawuli 发表于 2016-6-5 10:59
请问楼主第二题怎么弄的？

我用了一个size为k的最大堆。当然也可以用类似快排的做法

facebook 校招开始了？

zzz1322 发表于 2016-6-4 19:01
我用了一个size为k的最大堆。当然也可以用类似快排的做法

请问第二题有详细的描述吗？LC上有没有？

另外decode ways 是和LC上完全相同的返回所有可能性的数量int， 还是说返回所有结果List<String>?

blackrose 发表于 2016-6-5 11:04
facebook 校招开始了？

我也不知道，我是内推进去的，4月份推的

·1. 有一个数组，里面有0和非0元素，要求把所有非0元素移动到数组的前端，并返回非0元素的个数，非零元素顺序随意。非零元素之后数组有什么我们不关心。要求最小化写入次数。·

这题用一个pointer自加，是不是就已经是最小化写入次数了？感觉不知道该在哪个点优化了

laonawuli 发表于 2016-6-5 11:43
请问第二题有详细的描述吗？LC上有没有？

没有。一个二维平面上，给定N个点，求离原点最近的前K个点。

laonawuli 发表于 2016-6-5 11:45
·1. 有一个数组，里面有0和非0元素，要求把所有非0元素移动到数组的前端，并返回非0元素的个数，非零元素 ...

一个pointer不是最佳的方案。我说了这个方案，貌似小哥很不满意，问我有没有其他的方案，我想了半天没想出来。
比如[1,0,3,0,6,7,0,4,0,0]，按照一个pointer从前往后扫，结果应该是[1,3,6,7,4,7,0,4,0,0]，长度为5