一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2598|回复: 19
收起左侧

facebook 电面

[复制链接] |试试Instant~ |关注本帖
douya 发表于 2015-3-16 06:19:24 | 显示全部楼层 |阅读模式

2015(7-9月) 码农类 硕士 实习@Facebook - 内推 - 技术电面 |Other

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
intern第一轮面试。小哥应该不是三哥。
给一个0 1 矩阵,连在一起的1算做岛。求问岛的个数
. From 1point 3acres bbs11001
10011

这就是2个岛。
.1point3acres缃
一开始小哥发了个 code.stypi,然后死活用不了,我看不到他,他看不到我。所以他赶紧又发了个collabedit。。
然后开始写。。感觉小哥心情不太好,比较沉默。写完他发现有bug,然后一起debug。。然后又优化了几行,写简洁点。
写的慢,就这一个题。小哥也没说满意不满意。
不知道能不能过啊。

评分

2

查看全部评分

qjx026 发表于 2015-3-17 05:13:58 | 显示全部楼层
jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。

真相了。。。。。。
回复 支持 1 反对 0

使用道具 举报

jzy637 发表于 2015-3-16 07:42:38 | 显示全部楼层
学校牛b就能过。
背景一般就跪。
回复 支持 反对

使用道具 举报

 楼主| douya 发表于 2015-3-16 10:29:16 | 显示全部楼层
jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。
.鏈枃鍘熷垱鑷1point3acres璁哄潧
我了去。。。还可以这样啊
回复 支持 反对

使用道具 举报

wy193777 发表于 2015-3-16 23:19:49 | 显示全部楼层
这题咋做, bfs吗?
回复 支持 反对

使用道具 举报

shawlin 发表于 2015-3-17 00:12:17 | 显示全部楼层

感觉BFS , DFS都可以,类似于找多少个connected component吧,只是我们关心 1的CC
回复 支持 反对

使用道具 举报

clfhaha1234 发表于 2015-3-17 00:17:16 | 显示全部楼层
有个东西叫做并查集……
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-17 00:36:13 | 显示全部楼层
……这个是典型的连通图问题。
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
无向图一般两种做法,dfs,或者是并查集。

这题可以扩展,

一种是扩展到二分图问题。

另外一种可以扩展成多维并查集,这个比较好举例子,比如说两点之间有多条路径,问连通图。
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-17 00:41:22 | 显示全部楼层
shawlin 发表于 2015-3-17 00:12
感觉BFS , DFS都可以,类似于找多少个connected component吧,只是我们关心 1的CC

BFS一般不是处理这种问题用的。类似的科研中估计也不会用BFS,因为收敛速度的问题。当然这题一定要用也没有问题的。

另外如果是strong connected components,就不是类似的做法了。
回复 支持 反对

使用道具 举报

yuxrose 发表于 2015-3-17 01:59:08 | 显示全部楼层
robinho364 发表于 2015-3-17 00:36-google 1point3acres
……这个是典型的连通图问题。. Waral 鍗氬鏈夋洿澶氭枃绔,
. From 1point 3acres bbs
无向图一般两种做法,dfs,或者是并查集。

请问这题面试官expect的答案是DFS还是union find呢?各自有什么优劣呢?
回复 支持 反对

使用道具 举报

 楼主| douya 发表于 2015-3-17 02:25:31 | 显示全部楼层
yuxrose 发表于 2015-3-17 01:59.1point3acres缃
请问这题面试官expect的答案是DFS还是union find呢?各自有什么优劣呢?

我用dfs做的,面试官好沉默,感觉闷闷不乐的样子。也没说他expect啥。我说dfs,他说好。。
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-17 12:07:01 | 显示全部楼层
qjx026 发表于 2015-3-17 05:13
真相了。。。。。。

确实不能再同意
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-3-17 12:08:42 | 显示全部楼层
yuxrose 发表于 2015-3-17 01:59
请问这题面试官expect的答案是DFS还是union find呢?各自有什么优劣呢?

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

方法本身没有优劣之分。

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

如果面试官一定要考察一个人掌握知识的广度,我觉得没有什么意义。
-google 1point3acres
思维的深度远比广度更重要。
回复 支持 反对

使用道具 举报

dddxhh 发表于 2015-3-17 22:36:39 | 显示全部楼层
这题并查集是可以做,不过并查集的复杂度略高于线性额。

最好flood fill
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-18 05:02:25 | 显示全部楼层
一个电面,,,我一直主张电面不要炫技。。就plain的暴力就ok。贴个子集拙劣的code吧 这是DFS的。
  1. public class SolutionDFS {
  2.     . from: 1point3acres.com/bbs
  3.     private int row;
  4.     private int col;   . 1point 3acres 璁哄潧

  5.     public int solve(int[][] a) {
  6.         this.row = a.length;
  7.         this.col = a[0].length;
  8.         int ans = 0;
  9.         for (int i = 0; i < row; i++) {-google 1point3acres
  10.             for (int j = 0; j < col; j++) {
  11.                 if (a[i][j] == 1) {
  12.                     dfs(a, i, j);
  13.                     ans++;
  14.                 }
  15.             }
  16.         }
  17.         
    . from: 1point3acres.com/bbs
  18.         return ans;
  19.     }

  20.     private void dfs(int[][] a, int i, int j){
  21.         if (i < 0 || i >= row || j < 0 || j >= col || a[i][j] != 1) {
  22.             return;
  23.         }
  24.         a[i][j] = 2;
  25.         dfs(a, i + 1, j);
  26.         dfs(a, i, j + 1);
  27.         dfs(a, i - 1, j);
  28.         dfs(a, i, j - 1);. more info on 1point3acres.com
  29.     }.1point3acres缃
  30. }
复制代码
回复 支持 反对

使用道具 举报

seabiscuit119 发表于 2015-3-18 13:19:27 | 显示全部楼层
北航小涵 发表于 2015-3-18 05:02
一个电面,,,我一直主张电面不要炫技。。就plain的暴力就ok。贴个子集拙劣的code吧 这是DFS的。

这个就叫 flood fill是吧?
回复 支持 反对

使用道具 举报

北航小涵 发表于 2015-3-18 21:20:07 | 显示全部楼层
seabiscuit119 发表于 2015-3-18 00:19
这个就叫 flood fill是吧?

恩~~字数字数。
回复 支持 反对

使用道具 举报

yuruofeifei 发表于 2015-3-19 05:57:02 | 显示全部楼层
我听hr说,90%的fb面试都要面两道题才能过
回复 支持 反对

使用道具 举报

池大侠 发表于 2015-3-23 23:50:00 | 显示全部楼层
  1. def check(row, col, board, visit):.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.1point3acres缃
  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. 鍥磋鎴戜滑@1point 3 acres
  15.                         dfs(row + nbrow[k], col + nbcol[k], board, visit, curcount)
  16.         print curcount. 1point 3acres 璁哄潧

  17. . 1point 3acres 璁哄潧

  18. def getRes(board):
  19.         count = 0
  20.         visit = [[False for i in range(len(board[0]))] for j in range(len(board))]
  21.         curcount = 0
  22.         res = []

  23.         for row in xrange(len(board)):
  24.                  for  col in xrange(len(board[0])):
  25.                          if board[row][col] == 1 and visit[row][col] == False:
  26.                                  dfs(row, col, board, visit, curcount)
  27.                                  count += 1
  28.                                  res.append(curcount)
  29.         print visit
  30.         return count, res

  31. board = [[1, 1, 0, 0, 1], [1, 0, 0, 1, 1]]

  32. print getRes(board)

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

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

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-11 10:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表