近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3364|回复: 19
收起左侧

facebook 电面

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

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

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
intern第一轮面试。小哥应该不是三哥。
给一个0 1 矩阵,连在一起的1算做岛。求问岛的个数. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
11001
10011

这就是2个岛。

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

评分

2

查看全部评分

qjx026 发表于 2015-3-17 05:13:58 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
jzy637 发表于 2015-3-16 07:42
学校牛b就能过。
背景一般就跪。
. more info on 1point3acres.com
真相了。。。。。。
回复 支持 1 反对 0

使用道具 举报

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

使用道具 举报

 楼主| douya 发表于 2015-3-16 10:29:16 | 显示全部楼层
jzy637 发表于 2015-3-16 07:42.鏈枃鍘熷垱鑷1point3acres璁哄潧
学校牛b就能过。. from: 1point3acres.com/bbs
背景一般就跪。

我了去。。。还可以这样啊
回复 支持 反对

使用道具 举报

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

使用道具 举报

shawlin 发表于 2015-3-17 00:12:17 | 显示全部楼层
.1point3acres缃
感觉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
……这个是典型的连通图问题。

无向图一般两种做法,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呢?各自有什么优劣呢?

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

方法本身没有优劣之分。

所有算法,都需要基于一定的环境下来评判。. 1point3acres.com/bbs

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

思维的深度远比广度更重要。
回复 支持 反对

使用道具 举报

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

最好flood fill
回复 支持 反对

使用道具 举报

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

  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++) {
  10.             for (int j = 0; j < col; j++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  11.                 if (a[i][j] == 1) {
  12.                     dfs(a, i, j);
  13.                     ans++;
  14.                 }. 1point 3acres 璁哄潧
  15.             }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  16.         }
  17.         
  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;. more info on 1point3acres.com
  23.         }
  24.         a[i][j] = 2;. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.         dfs(a, i + 1, j);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  26.         dfs(a, i, j + 1);
  27.         dfs(a, i - 1, j);. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.         dfs(a, i, j - 1);
  29.     }
  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):. from: 1point3acres.com/bbs
  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]. Waral 鍗氬鏈夋洿澶氭枃绔,
  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):. From 1point 3acres bbs
  14.                         #curcount += 1
  15.                         dfs(row + nbrow[k], col + nbcol[k], board, visit, curcount). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.         print curcount



  17. def getRes(board):
  18.         count = 0
  19.         visit = [[False for i in range(len(board[0]))] for j in range(len(board))]
  20.         curcount = 0. from: 1point3acres.com/bbs
  21.         res = []

  22.         for row in xrange(len(board)):
  23.                  for  col in xrange(len(board[0])):
  24.                          if board[row][col] == 1 and visit[row][col] == False:
  25.                                  dfs(row, col, board, visit, curcount)
  26.                                  count += 1. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  27.                                  res.append(curcount)
  28.         print visit
  29.         return count, res

  30. board = [[1, 1, 0, 0, 1], [1, 0, 0, 1, 1]]. more info on 1point3acres.com

  31. print getRes(board)

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-6-28 08:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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