心塞的fb电面跪经

刚刚结束的fb电面。

约了2:00PM PST，结果楼主左等右等等到了2:10才接到了电话。。。。这十分钟简直度日如年。。

烙印打来的电话，加上国人姐姐（？）shadow。国人姐姐只在开头自我介绍了一下，然后没有说过话。 三哥自我介绍了一下说是instagram组的（国人姐姐也是），在fb22个月。似乎烙印开了电话免提还没有戴耳机，声音超级不清楚（还属于口音重的那种三哥）。后来做题的时候我说听不清他似乎才把听筒拿起来。免提的时候背景还有别人说话的声音。（难道是为了让shadow听？）

也没让我自我介绍，直接上题

利特口散失酒，小变动是给的vector里面有重复元素（感觉毫无意义啊，本来就可以重复使用）。

第二题似乎没在面经见过，给定一个超级大的排好序的vector     [1(a个),

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

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

,3,3,3,3,3,3,3,3,3,3]这样一个数组，
返回{1, 4}, {2, 7}, {3, 10}
其实就是不同的数字要你计数，但是要求优于O(n)......

补充内容 (2017-1-30 23:04):
排序好的数组

补充内容 (2017-2-1 21:58):
多谢三哥的不杀之恩！收到onsite了！

感谢楼主分享。按照楼主的思路，第二题是不是这样做的？

1. class Solution {
   
2. public:
   
3.     vector<pair<int, int>> countNums(vector<int> &nums) {
   
4.         vector<pair<int, int>> res;
   
5.         int st = 0;
   
6.         while (st < (int)nums.size()) {
   
7.             int ed = findLastOf(nums, st, nums[st]);
   
8.             res.push_back( {nums[st], ed - st + 1} );
   
9.             st = ed + 1;
   
10.         }
    
11.         return res;
    
12.     }
    
13. 
    
14. private:
    
15.     int findLastOf(const vector<int> &nums, int st, int target) {
    
16.         int left = st;
    
17.         int diff = 1;
    
18.         while (left + diff < (int)nums.size()) {
    
19.             if (nums[left + diff] <= target) {
    
20.                 left += diff;
    
21.                 diff *= 2;
    
22.             } else {
    
23.                 break;
    
24.             }
    
25.         }
    
26. 
    
27.         int right = min((int)nums.size() - 1, left + diff);
    
28.         return binarySearch(nums, left, right, target);
    
29.     }
    
30. 
    
31.     int binarySearch(const vector<int> &nums, int left, int right, int target) {
    
32.         while (left + 1 < right) {
    
33.             int mid = left + (right - left) / 2;
    
34.             if (nums[mid] <= target) {
    
35.                 left = mid;
    
36.             } else {
    
37.                 right = mid;
    
38.             }
    
39.         }
    
40. 
    
41.         if (nums[right] == target)
    
42.             return right;
    
43.         return left;
    
44.     }
    
45. };
    

复制代码

第二题

1. public class DecodeVector {
   
2. 
   
3.     class Pair {
   
4.         int c;
   
5.         int count;
   
6.         public Pair(int c, int count) {
   
7.             this.c = c;
   
8.             this.count = count;
   
9.         }
   
10.     }
    
11. 
    
12.     public List<Pair> getCount(int[] arr) {
    
13.         List<Pair> list = new ArrayList<>();
    
14.         if (arr == null || arr.length == 0) {
    
15.             return list;
    
16.         }
    
17. 
    
18.         int start = 0;
    
19.         while (start < arr.length) {
    
20.             int end = findLast(start, arr);
    
21.             list.add(new Pair(arr[start], end - start + 1));
    
22.             start = end + 1;
    
23.         }
    
24. 
    
25.         return list;
    
26.     }
    
27. 
    
28.     private int findLast(int start, int[] arr) {
    
29.         int c = arr[start];
    
30.         int diff = 1;
    
31.         while (start + diff < arr.length && arr[start + diff] == c) {
    
32.             diff <<= 1;
    
33.         }
    
34.         if (start + diff >= arr.length) {
    
35.             return arr.length - 1;
    
36.         }
    
37. 
    
38.         int end = start + diff;
    
39.         while (start + 1 < end) {
    
40.             int mid = (end - start) / 2 + start;
    
41.             if (arr[mid] == c) {
    
42.                 start = mid;
    
43.             } else {
    
44.                 end = mid;
    
45.             }
    
46.         }
    
47.         if (arr[end] == c) {
    
48.             return end;
    
49.         } else {
    
50.             return start;
    
51.         }
    
52.     }
    
53. 
    
54. 
    
55.     public static void main(String[] args) {
    
56.         int[] arr = {1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3};
    
57.         DecodeVector d = new DecodeVector();
    
58.         List<Pair> res = d.getCount(arr);
    
59.         for (Pair p : res) {
    
60.             System.out.println(p.c + ": " + p.count);
    
61.         }
    
62.     }
    
63. }
    

复制代码

假设abbcccddddeeee => {{1,a}, {2,b},{3,c},{4,d},{5,e}} 没看懂用binary search怎么做。。。。

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

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

第二题很像在stream里面做binary search

同问 看不懂第二题。

david.fang 发表于 2017-1-30 22:42
同问 看不懂第二题。

我补充在1l了

感觉就是用二分查找，但是最坏情况并不能比o(n)更优化吧，至少要把每个数学都访问一边，那就是o(n)了

楼主什么时候内推的？报下time line吧，多谢

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

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

WhatsFLAG 发表于 2017-1-31 00:42
感觉就是用二分查找，但是最坏情况并不能比o(n)更优化吧，至少要把每个数学都访问一边，那就是o(n)了

二分的话最差应该nlgn吧？ 假如所有数字都不一样，找上界下界都是lgn，然后要找n次。。。