Facebook 2015暑期实习面经

marthew777 发表于 2015-4-9 07:26
上面的代码我说了是给一个算法实现的大概思路，肯定有syntax error的好吗，我花几分钟随手写的。。
完整 ...

赞，我当时在飞机上，照你思路编着编..，谢谢你提供完整代码

时间空间复杂度都是O(m*n), 每个点遍历一次即可

1. //Assume '_' is 0, 'G' is 1, 'W' is 2
   
2.         private class Position{
   
3.                 int x;
   
4.                 int y;
   
5.                 public Position(int x, int y){
   
6.                         this.x = x;
   
7.                         this.y = y;
   
8.                 }
   
9.         }
   
10.         public void findLen(int[][] matrix){
    
11.                 int m = matrix.length;
    
12.                 if(m<1) return;
    
13.                 int n = matrix[0].length;
    
14.                 int[][] result = new int[m][n];
    
15.                 boolean[][] visited = new boolean[m][n];
    
16.                 Queue<Position> queue = new LinkedList<Position>();
    
17.                 int curLevel_nums = 0;
    
18.                 int nextLevel_nums = 0;
    
19.                 int level = 1;
    
20.                 for(int i=0; i<m; ++i){
    
21.                         for(int j=0; j<n; ++j){
    
22.                                 if(matrix[i][j] == 1){//enqueue gate
    
23.                                         visited[i][j] = true;
    
24.                                         queue.add(new Position(i, j));
    
25.                                         curLevel_nums++;
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 while(!queue.isEmpty()){
    
30.                         Position cur = queue.poll();
    
31.                         curLevel_nums--;
    
32.                         int[] arr = {1,-1,1,-1};
    
33.                         for(int i=0; i<arr.length; ++i){
    
34.                                 Position newP;
    
35.                                 if(i<2){
    
36.                                         newP = new Position(cur.x+arr[i], cur.y);
    
37.                                 }
    
38.                                 else{
    
39.                                         newP = new Position(cur.x, cur.y+arr[i]);
    
40.                                 }
    
41.                                 if(newP.x<0 || newP.x>=m || newP.y<0 || newP.y>=n || visited[newP.x][newP.y]){
    
42.                                         continue;
    
43.                                 }
    
44.                                 else{
    
45.                                         if(matrix[newP.x][newP.y]==2){
    
46.                                                 visited[newP.x][newP.y] = true;
    
47.                                                 result[newP.x][newP.y] = -1;
    
48.                                         }
    
49.                                         else{//matrix[newP.x][newP.y]==0
    
50.                                                 visited[newP.x][newP.y] = true;
    
51.                                                 result[newP.x][newP.y] = level;
    
52.                                                 queue.add(newP);
    
53.                                                 nextLevel_nums++;
    
54.                                         }
    
55.                                 }
    
56.                         }
    
57.                         if(curLevel_nums==0){
    
58.                                 curLevel_nums = nextLevel_nums;
    
59.                                 nextLevel_nums = 0;
    
60.                                 level++;
    
61.                         }
    
62.                 }
    
63.                
    
64.                 //print
    
65.                 for(int i=0; i<m; ++i){
    
66.                         for(int j=0; j<n; ++j){
    
67.                                 System.out.print(result[i][j]+ "  ");
    
68.                         }
    
69.                         System.out.println();
    
70.                 }
    
71.         }

复制代码

能问下啊，lz啥时网上海投的？

Aprilyn 发表于 2015-4-9 10:41
能问下啊，lz啥时网上海投的？

我是三月下旬海投的，当时过了两天之后，安排我在4月7号面试。

都这么晚了．．．facebook实习真还有坑？

offfer 发表于 2015-4-10 01:18
都这么晚了．．．facebook实习真还有坑？

现在不知道有没有了，不过那个时候确实还有。

想请问一下FB如果挂了的话，冷冻期会影响到接下来投full time的吗

JamesJi 发表于 2015-4-10 22:36
想请问一下FB如果挂了的话，冷冻期会影响到接下来投full time的吗

会的,我刚刚问过HR...所以有点小慌. 今天店面.

楼主，不太明白，最后返回值需要是什么？ 一个matrix? 如果一个_到多个gate, 需要print哪一个距离？

resoy 发表于 2015-4-11 01:20
楼主，不太明白，最后返回值需要是什么？ 一个matrix? 如果一个_到多个gate, 需要print哪一个距离？

返回一个matrix，如果有多个G，找最近的那一个。