facebook 电面

jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。

真相了。。。。。。

qjx026 发表于 2015-3-17 05:13
真相了。。。。。。

确实不能再同意

yuxrose 发表于 2015-3-17 01:59
请问这题面试官expect的答案是DFS还是union find呢？各自有什么优劣呢?

不知道……面试官的心思，真心猜不透。

方法本身没有优劣之分。

所有算法，都需要基于一定的环境下来评判。

如果面试官一定要考察一个人掌握知识的广度，我觉得没有什么意义。

思维的深度远比广度更重要。

这题并查集是可以做，不过并查集的复杂度略高于线性额。

最好flood fill

一个电面，，，我一直主张电面不要炫技。。就plain的暴力就ok。贴个子集拙劣的code吧 这是DFS的。

1. public class SolutionDFS {
   
2.    
   
3.     private int row;
   
4.     private int col;   
   
5. 
   
6.     public int solve(int[][] a) {
   
7.         this.row = a.length;
   
8.         this.col = a[0].length;
   
9.         int ans = 0;
   
10.         for (int i = 0; i < row; i++) {
    
11.             for (int j = 0; j < col; j++) {
    
12.                 if (a[i][j] == 1) {
    
13.                     dfs(a, i, j);
    
14.                     ans++;
    
15.                 }
    
16.             }
    
17.         }
    
18.         
    
19.         return ans;
    
20.     }
    
21. 
    
22.     private void dfs(int[][] a, int i, int j){
    
23.         if (i < 0 || i >= row || j < 0 || j >= col || a[i][j] != 1) {
    
24.             return;
    
25.         }
    
26.         a[i][j] = 2;
    
27.         dfs(a, i + 1, j);
    
28.         dfs(a, i, j + 1);
    
29.         dfs(a, i - 1, j);
    
30.         dfs(a, i, j - 1);
    
31.     }
    
32. }

复制代码

已跪。。。

pandafolk 发表于 2015-3-18 05:02
一个电面，，，我一直主张电面不要炫技。。就plain的暴力就ok。贴个子集拙劣的code吧 这是DFS的。

这个就叫 flood fill是吧？

seabiscuit119 发表于 2015-3-18 00:19
这个就叫 flood fill是吧？

恩~~字数字数。

我听hr说，90%的fb面试都要面两道题才能过

1. def check(row, col, board, visit):
   
2.         m = len(board)
   
3.         n = len(board[0])
   
4.         if row >= 0 and row < m and col >= 0 and col < n and visit[row][col] == False and board[row][col] == 1:
   
5.                 return True
   
6.         return False
   
7. def dfs(row, col, board, visit, curcount):
   
8.         nbrow = [1, 0, -1, 0]
   
9.         nbcol = [0, 1, 0, -1]
   
10.         visit[row][col] = True
    
11.         curcount += 1
    
12.         for k in xrange(4):
    
13.                 if check(row + nbrow[k], col + nbcol[k], board, visit):
    
14.                         #curcount += 1
    
15.                         dfs(row + nbrow[k], col + nbcol[k], board, visit, curcount)
    
16.         print curcount
    
17. 
    
18. 
    
19. 
    
20. def getRes(board):
    
21.         count = 0
    
22.         visit = [[False for i in range(len(board[0]))] for j in range(len(board))]
    
23.         curcount = 0
    
24.         res = []
    
25. 
    
26.         for row in xrange(len(board)):
    
27.                  for  col in xrange(len(board[0])):
    
28.                          if board[row][col] == 1 and visit[row][col] == False:
    
29.                                  dfs(row, col, board, visit, curcount)
    
30.                                  count += 1
    
31.                                  res.append(curcount)
    
32.         print visit
    
33.         return count, res
    
34. 
    
35. board = [[1, 1, 0, 0, 1], [1, 0, 0, 1, 1]]
    
36. 
    
37. print getRes(board)
    
38. 
    

复制代码

一亩三分地严打"顶""好贴""收藏了"之类的垃圾回复帖！被警告三次，系统会自动封杀ID！

想支持楼主，请点击帖子下方的"好苗""分享""收藏"键，酌情给楼主加大米（系统不扣你自己的分）。
积分不够看不了帖子，请参考论坛导航里的"帮助"，"新手提纲"里有攒积分指南