fb onsite 这样“黑”的我真的很不舒服

不要问我具体问了啥，这只是一个写故事的peaceful马甲号。我一般双卡双待，你懂的。

2轮coding, 1轮design, 1轮 career/hehavior （夹带1coding). 面了前三轮觉得要拿下了，结果最后一轮的三哥直接为我关上了大门。不管是不是我个人原因，我只想弄个马甲写个故事，给每一个准备面试的朋友喊声加油。希望以此少点怨气，做个真正能屈能伸peaceful的人。我了解奋战在一线的感受，只愿战友们能继续加油。

这天小雨，最不喜欢的天气。三姐姐的HR，人很好。接了我之后一路聊着天走到会议室，然后她发现会议室被占了（我一脸蒙逼），然后去下一个会议室（fb连大楼都是connected network，我一路试图帮她找会议室)，再然后发现又错了，就又去了最后正确的会议室（15mins passed). 然后顺理成章开始第一轮。小三哥人很好，出了一个利特代码和一个新题（很有意思的题），45分钟两个正好完毕，个人觉得code 质量上乘，还教会了小哥Collections.binarySearch()。期间有个插曲，国人妹妹（很漂亮）敲门乱入，说她的面试早就开始了，为啥我们还没结束，我告诉她我的名

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

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

。我全程尽最大努力保持了calm & peaceful，要是我不care这个机会或者我能再man点（实力再强点）我会跟他干起来的。再然后他说，我应该是最后一个面试官，咱们撤吧。再见。

实在不想再描述了，，，整个人都不好了。发了邮件给HR告诉她最后一面的情况，然后说我觉得25分钟让我承受这些（太重了。。。），她说他会尽快反馈。跟伙计回来诉苦，查找发现四sum可以N2LGN的，然后我就告诉自己，洗洗睡吧。这就是命。我把标题“黑”加了引号，因为我不想把失败交给随机因素，只想给悲伤的故事添点乐趣。

唉。

mysteryjoe 发表于 2016-10-28 10:38
4sum average应该没有n2logn的吧，看过很多自称n2logn的方法，分析都是至少n3的

理论上O(n^2)可以做，把所有(x,y) pair的和放到hash table里面，看有没有两个pair加起来是target。K sum的理论复杂度是O(n^(K+1)/2)

coldknight 发表于 2016-11-1 13:24
是的，他的证明没问题。我又回了他一个链接。我没权限在这里发链接。你再看看吧。

还有，我现在突然之 ...

不，Big-O并不是"upper bound of all cases"，而是"upper bound of XXX"。这个XXX根据不同的context可取“最差输入的执行时间” (worst time big O)，“所有case的平均执行时间期望” (average case big O)，甚至“最好输入的执行时间”(best case big O)。你甚至取任意特定输入的执行时间都可以。但是一般最常用的就是前两个。

之所以容易混淆，是因为多数常见算法的worst case O=average case O。比如常见排序算法中也只有Quicksort不满足这点。而对于不满足这点的实用算法，我们通常会强调average case，因为这个指标最实际。而且听上去好听一些。

证明worst case O，只需举出一个特例即可；而证明average case O，则需要经过一些数学分析了。对于需要列举所有quadruplet的4SUM来说，worst case O是O(N^3)，这点Stephan的证明没有问题，因为他举出了一个特例。但是average case究竟是什么，这点还需要进一步证明。

写了下代码

1. public class Four4SumFastest {
   
2. 
   
3.     class Pair {
   
4.         int i;
   
5.         int j;
   
6.         int sum;
   
7.         public Pair(int i, int j, int sum) {
   
8.             this.i = i;
   
9.             this.j = j;
   
10.             this.sum = sum;
    
11.         }
    
12.     }
    
13. 
    
14.     public List<int[]> findFourElements(int[] arr, int k) {
    
15.         List<int[]> res = new ArrayList<>();
    
16.         if (arr == null || arr.length < 4) {
    
17.             return res;
    
18.         }
    
19. 
    
20.         int n = arr.length;
    
21.         Arrays.sort(arr);
    
22.         List<Pair> list = new ArrayList<>();
    
23.         for (int i = 0; i < n - 1; i ++) {
    
24.             for (int j = i + 1; j < n; j++) {
    
25.                 list.add(new Pair(i, j, arr[i] + arr[j]));
    
26.             }
    
27.         }
    
28. 
    
29.         Collections.sort(list, new Comparator<Pair>() {
    
30.             public int compare(Pair p1, Pair p2) {
    
31.                 return p1.sum - p2.sum;
    
32.             }
    
33.         });
    
34.         
    
35.         int i = 0;
    
36.         int j = list.size() - 1;
    
37.         HashSet<String> set = new HashSet<>();
    
38.         while (i < j) {
    
39.             int sum = list.get(i).sum + list.get(j).sum;
    
40.             if (sum == k && nonCommon(list.get(i), list.get(j))) {
    
41.                 int[] tmp = new int[4];
    
42.                 tmp[0] = arr[list.get(i).i];
    
43.                 tmp[1] = arr[list.get(i).j];
    
44.                 tmp[2] = arr[list.get(j).i];
    
45.                 tmp[3] = arr[list.get(j).j];
    
46.                 Arrays.sort(tmp);
    
47.                 String key = tmp[0] + " " + tmp[1] + " " + tmp[2] + " " + tmp[3];
    
48.                 if (!set.contains(key)) {
    
49.                     res.add(new int[] {arr[list.get(i).i], arr[list.get(i).j], arr[list.get(j).i], arr[list.get(j).j]});
    
50.                     set.add(key);
    
51.                 }
    
52.                 i++;
    
53.                 j--;
    
54.             } else if (sum > k) {
    
55.                 j--;
    
56.             } else {
    
57.                 i++;
    
58.             }
    
59.         }
    
60. 
    
61.         return res;
    
62.     }
    
63. 
    
64.     private boolean nonCommon(Pair p1, Pair p2) {
    
65.         if (p1.i == p2.i || p1.i == p2.j || p1.j == p2.j || p1.j == p2.i) {
    
66.             return false;
    
67.         }
    
68. 
    
69.         return true;
    
70.     }
    
71. 
    
72.     public static void main(String[] args) {
    
73.         int[] arr = {10, 2, 3, 4, 5, 9, 7, 8, 7, 8, 2, 2, 7, 7};
    
74.         Four4SumFastest f = new Four4SumFastest();
    
75.         List<int[]> res = f.findFourElements(arr, 23);
    
76.         for (int[] tmp : res) {
    
77.             String key = tmp[0] + " " + tmp[1] + " " + tmp[2] + " " + tmp[3];
    
78.             System.out.println(key);
    
79.         }
    
80.     }
    
81. }

复制代码

感觉LZ挺厉害的呀！说不定拿到offer了！加油！

楼主已经出结果了还是？你要是跟recruiter反馈了没准会加面吧

samuelling 发表于 2016-10-28 10:36
楼主已经出结果了还是？你要是跟recruiter反馈了没准会加面吧

谢谢。反馈了，希望可以加面。HR回复说等collect all feedbck给我评估结果。但是害怕直接给我毙了。

4sum average应该没有n2logn的吧，看过很多自称n2logn的方法，分析都是至少n3的

samuelling 发表于 2016-10-28 10:36
楼主已经出结果了还是？你要是跟recruiter反馈了没准会加面吧

但是说实话，能感觉到要挂。不想保持念想，更折磨人。

mysteryjoe 发表于 2016-10-28 10:38
4sum average应该没有n2logn的吧，看过很多自称n2logn的方法，分析都是至少n3的

我反正不会。面试官感觉想要N2LGN，因为我说了想法可以O3做，他说咱们讨论出最优解再写code。我说我能想到的就是O3，然后才让我写的。。。我擦了

zfrancica 发表于 2016-10-28 10:35
感觉LZ挺厉害的呀！说不定拿到offer了！加油！

谢谢。一时心情不好。你加油。

感觉有机会啊，最后一个三哥只是态度不好，但lz答的没有问题

遇到什么样的interviewer也是看运气的，不过，看楼主描述，多半是过了！最后的三哥说不定本来就不是一个nice guy，只是本性流露而已