facebook 实习 面经

一个月前的fb一面

第一题：plus one原题

第二题：一个数组内

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

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

。lc上有类似题。

求大米~~~~~

第二题不是leetcode原题么，O(n), O(1)
话说怎么贴代码...


public boolean increasingTriplet(int[] nums) {
        if (nums == null || nums.length < 3) {return false;}
        int min = Integer.MAX_VALUE, max = Integer.MAX_VALUE;
        for (int n : nums) {
            if (n > max) { return true;}
            if (n > min) {
                max = n;
            } else {
                min = n;
            }
        }
        return false;
    }

第二题用一个空间为3的栈就行吧？
将第一个元素进栈，loop一遍数组，如果当前元素比栈顶小的话就退栈知道栈顶元素比当前元素小或栈空并将该元素进栈。当栈满表示已经有三个升序元素，返回true就行，复杂度O(n), O(1)

caofang1992 发表于 2016-2-19 00:09
这个是不是只能处理连续的情况，如果是2，4，1，7这种情况呢？求解答，谢谢

对的，我之前没有考虑这种情况。需要加上一个第二大的判断，当栈里的元素为2个的时候和第二大元素比较一下，小的话update。如果当前元素比第二大元素大的话返回true。感觉有点tricky了

1. public boolean increasingTriplet(int[] nums) {
   
2.         if(nums == null || nums.length < 3) return false;
   
3.         
   
4.         int mid = Integer.MAX_VALUE;
   
5.         Stack <Integer> s = new Stack();
   
6.         
   
7.         s.push(nums[0]);
   
8.         
   
9.         for(int i = 1; i < nums.length; i++){
   
10.             
    
11.             while(!s.isEmpty() && s.peek() >= nums[i]){
    
12.                 s.pop();
    
13.             }
    
14.             s.push(nums[i]);
    
15.             
    
16.             if(s.size() == 3 || s.peek() > mid) return true;
    
17.             if(s.size() == 2) mid = Math.min(mid, s.peek());
    
18.         }
    
19.         
    
20.         return false;
    
21.     }

复制代码

lz是内推么？还是自己网投的，大概多久能收到预约电话。

xiaozhuxiaozhu 发表于 2016-1-27 11:43
lz是内推么？还是自己网投的，大概多久能收到预约电话。

内推的 大概一两周

实现了一下第二题的代码 应该可以跑

1. int a, b, c, least;
   
2. bool three_inscreasing(std::vector<int> nums)
   
3. {
   
4.     int n = nums.size();
   
5.     if (n <= 2) return false;
   
6. 
   
7.     int i = 1;
   
8.     while (i < n && nums[i] < nums[i-1]) {
   
9.         i++;
   
10.     }
    
11. 
    
12.     if (i == n-1) {
    
13.         return false;
    
14.     }
    
15. 
    
16.     a = i-1;
    
17.     b = i;
    
18.     least = i-1;
    
19. 
    
20.     for (i = i+1; i < n; i++) {
    
21.         if (nums[i] < nums[least]) {
    
22.             least = i;
    
23.         }
    
24.         if (nums[i] > nums[b]) {
    
25.             c = i;
    
26.             return true;
    
27.         }
    
28.         if (nums[i] < nums[b] && nums[i] > nums[a]) {
    
29.             b = i;
    
30.         } else if (nums[i] > nums[least] && nums[i] < nums[b]) {
    
31.             a = least;
    
32.             b = i;
    
33.         }
    
34.     }
    
35.     return false;
    
36. }

复制代码

singku 发表于 2016-1-27 13:38
实现了一下第二题的代码 应该可以跑

while (i < n && nums[i] < nums[i-1]) {
        i++;
    }

应改为 nums[i]<=nums[i-1]吧

补充内容 (2016-1-27 16:23):
nums[i]<=nums[i-1]

aangel 发表于 2016-1-27 16:22
while (i < n && nums < nums) {
        i++;
    }

你说得没错

请问LZ, 是不连续的x y z吗？要求O(n)解法？

可以不连续的 应该用dp吧

stanleyyyyy 发表于 2016-1-28 07:03
可以不连续的 应该用dp吧

从左到右扫一遍，记下最小值，从右到左扫一遍，记下最大值
最后再从头到尾扫一遍，以每个点作为分割线，
也是O(n)时间，但是需要O(n)空间,
DP怎么做？

第二题这样是o(n)

1. // bool lengthOfLIS(vector<int>& nums) {
   
2. //     vector<int> res;
   
3. //     for(int i=0; i<nums.size(); i++) {
   
4. //         auto it = std::lower_bound(res.begin(), res.end(), nums[i]);
   
5. //         if(it==res.end()) res.push_back(nums[i]);
   
6. //         else *it = nums[i];
   
7. //         if(res.size()>=3)
   
8. //         return true;
   
9. //     }
   
10. //     return false;
    
11. // }

复制代码