FB 昂赛

wkvictor 发表于 2016-12-29 06:05
求问lz 总结FB BQ的帖子在哪儿？我只找到了一个general的（http://www.1point3acres.com/bbs/forum.php?mod ...

就看的这个

lela900900 发表于 2017-1-26 13:50
lz 你这是面的fb infrastructure? 他家infra 主要是做什么的？考system design看样子很深？

面试内容都是general的

zjiang42 发表于 2017-1-27 16:27
请问楼主 friend relationship那个题目 应该需要自己建一下graph吗，刚才想了下貌似不能省掉那步。后面在按 ...

我是自己建了graph

请问楼主他家通知是用电话还是邮件

同问楼主last visited key那题，是不是类似于lru。然后follow up使用set又是什么意思。

问楼主的结果是电话还是邮件出的？

关于第三题的design,如果是设计题目，那应该不是考察数据结构吧，各类数据结构应该都不是他想要的答案吧。我觉得考察的是类似倒排索引的东西，然后简单说一下倒排索引是怎么一回事。最后考虑一下ＦＢ的用户个数，决定如果存储？

洗了下第四题，

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. }
    

复制代码

第四题,

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. }
    

复制代码

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

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