FB 昂赛

刚刚结束的onsite，准备了挺久的，但感觉是要跪的节奏，放个帖子攒攒人品吧。。。。。。。

1.印度多年经验老哥，BQ，就那儿总结FB BQ 的帖子看看就好，就是project， conflict啥的。coding postorder tree iterative。
2.国人小哥，一直玩儿手机。。。。。。写个数据结构支持，get， set， delete，last visited key。 很快秒掉。 follow up，怎么opt， 额。。。已经用了 O（1）了， 人后说可以用set。。。感觉follow up答得不是很好，拍了照就走了
lunch 中国小哥带着转了转。
3.sys design， 本来是中国小哥的，但换成了另一个人，感觉ABC，桑心。

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

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

4.中国小哥，非常nice， 一直follow我的思路。 1.input friends relation {{1，2}， {2，3}， {3，4}} 把用户存在两个group里， 每个group里大家都不互相认识。所以exp应该g1{1，3} g2{2，4}。
其他情况和小哥讨论一下，我自己想如何设计都可以，比如所有人都不认。 很快写完，最后考虑corner case的时候，小哥提醒了一下。2.input 是array {1，2，3，0，4}。到达最后一个格子最短步数，每个数字代表最多可以跳几下。应该是lc的题吧，忘记了。不过很快dp秒掉。 后来，小哥就把我送了出来。。。

感觉面的很一般， 并没有出彩的地方，估计是没有strong hire了，保佑别negative就好。 总体感觉难度并不是很大，但是要快点写，第二轮只写了一道题，感觉不太够。关于design，哎，本来想写个总结的，发现自己复习的，和他问道的都不一样。。。还是算了

自己祈祷一下吧。。。

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

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

第四题,

1. public class Group {
   
2. 
   
3.     public static void  main(String[] args) {
   
4.         Group g = new Group();
   
5.         int[][] rs =  {{1, 2}, {2,3}, {3,4}};
   
6.         List<Set<Integer>> res = g.getGroup(rs);
   
7.         for (int i = 0; i < res.size(); i++) {
   
8.             for (int k : res.get(i)) {
   
9.                 System.out.print(k + " ");
   
10.             }
    
11.             System.out.println();
    
12.         }
    
13.     }
    
14. 
    
15.     public List<Set<Integer>> getGroup(int[][]  relations) {
    
16.         List<Set<Integer>> res = new ArrayList<>();
    
17.         if (relations == null || relations.length == 0) {
    
18.             return res;
    
19.         }
    
20. 
    
21.         HashMap<Integer, Set<Integer>> map = new HashMap<>();
    
22.         for (int[] r : relations) {
    
23.             if (!map.containsKey(r[0])) {
    
24.                 map.put(r[0], new HashSet<>());
    
25.             }
    
26.             if (!map.containsKey(r[1])) {
    
27.                 map.put(r[1], new HashSet<>());
    
28.             }
    
29.             map.get(r[0]).add(r[1]);
    
30.             map.get(r[1]).add(r[0]);
    
31.         }
    
32. 
    
33.         Set<Integer> set1 = new HashSet<>();
    
34.         Set<Integer> set2 = new HashSet<>();
    
35.         boolean flag = true;
    
36.         Queue<Integer> queue = new LinkedList<>();
    
37.         queue.offer(relations[0][0]);
    
38.         set1.add(relations[0][0]);
    
39.         while (!queue.isEmpty()) {
    
40.             int size = queue.size();
    
41.             for (int i = 0; i < size; i++) {
    
42.                 int cur = queue.poll();
    
43.                 if ((flag && set2.contains(cur)) || (!flag && set1.contains(cur))) {
    
44.                     return res;
    
45.                 }
    
46.                 if (!set1.contains(cur) && !set2.contains(cur)) {
    
47.                     if (flag) {
    
48.                         set1.add(cur);
    
49.                     } else {
    
50.                         set2.add(cur);
    
51.                     }
    
52.                 }
    
53.                 for (int k : map.get(cur)) {
    
54.                     if (!set1.contains(k) && !set2.contains(k)) {
    
55.                         queue.offer(k);
    
56.                     }
    
57.                 }
    
58.             }
    
59.             flag = !flag;
    
60.         }
    
61. 
    
62.         res.add(set1);
    
63.         res.add(set2);
    
64. 
    
65.         return res;
    
66.     }
    
67. }
    

复制代码

洗了下第四题，

1. public class MinimumSteps {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         MinimumSteps ms = new MinimumSteps();
   
5.         int[] arr = {1, 2, 3, 0, 4};
   
6.         System.out.println(ms.getMinimumSteps(arr));
   
7.     }
   
8. 
   
9.     public int getMinimumSteps(int[] arr) {
   
10.         if (arr == null || arr.length == 0) {
    
11.             return 0;
    
12.         }
    
13. 
    
14.         int[] dp = new int[arr.length];
    
15.         Arrays.fill(dp, Integer.MAX_VALUE);
    
16.         dp[0] = 1;
    
17.         for (int i = 1; i < arr.length; i++) {
    
18.             for (int j = 0; j < i; j++) {
    
19.                 if (dp[j] != Integer.MAX_VALUE && j + arr[j] >= i) {
    
20.                     dp[i] = Math.min(dp[j] + 1, dp[i]);
    
21.                 }
    
22.             }
    
23.         }
    
24.         
    
25.         return dp[arr.length - 1];
    
26.     }
    
27. }
    

复制代码

哥们，同刚刚面完回到宾馆，“关于design，哎，本来想写个总结的，发现自己复习的，和他问道的都不一样。。。还是算了”，看到这句话我真想跟你握个手，被system design虐了。

friends relationship 那道题有啥思路吗？

FTD2014 发表于 2016-12-17 08:50
哥们，同刚刚面完回到宾馆，“关于design，哎，本来想写个总结的，发现自己复习的，和他问道的都不一样。。 ...

是的啊，准备的都没用。。。哎

wtcupup 发表于 2016-12-17 08:57
friends relationship 那道题有啥思路吗？

把他想成图，然后BFS就行了，用array存visited。不难。

celtspirit 发表于 2016-12-17 10:30
把他想成图，然后BFS就行了，用array存visited。不难。

感觉楼主design也都做出来了，应该结果不错的。

FTD2014 发表于 2016-12-17 13:12
感觉楼主design也都做出来了，应该结果不错的。

没有哎，他对我的data structure不是很满意。。。。

celtspirit 发表于 2016-12-17 10:30
把他想成图，然后BFS就行了，用array存visited。不难。

详细说说吧。
直接bfs容易，但是怎么分成两个group呢？

freemail165 发表于 2016-12-18 12:45
详细说说吧。
直接bfs容易，但是怎么分成两个group呢？

the algo may be like BFS for bipartite graph check ??

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

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