當了一年的 Facebook Rotational Software Engineer 心得分享

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4260|回复: 25
收起左侧

Bloomberg 电面

[复制链接] |试试Instant~ |关注本帖
hj867955629 发表于 2015-9-19 03:02:34 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类General 硕士 全职@Bloomberg - 网上海投 - 技术电面  | Other | fresh grad应届毕业生

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

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

x
刚面完电面,没给出最优解,唉思维定势了。。。问了实习经历,问了多态,然后就出题了。

给定matrix,
0 0 0. Waral 博客有更多文章,
B G G
0 0 0
找到每个0到G的最短距离,B是障碍。
输出:.留学论坛-一亩-三分地
2 1 1
B G G
2 1 1
虽然在提示下最后讲出了最优解,可是时间都快没了。感觉不好。唉求加米安慰下。

.留学论坛-一亩-三分地

补充内容 (2015-9-21 23:44):
刚收到邮件,电面过了

评分

4

查看全部评分

本帖被以下淘专辑推荐:

albee_fighting 发表于 2015-11-12 13:40:05 | 显示全部楼层
LawranceH 发表于 2015-9-19 04:33
这是我写的,你们看看, 我就是把所有G 当成bfs 开始点, 每个level 附近的点加1.  当 当前点已经不是0的时 ...

应该不需要比较,如果用BFS,那就已经默认是最短路径了。
回复 支持 1 反对 0

使用道具 举报

 楼主| hj867955629 发表于 2015-9-19 03:18:11 | 显示全部楼层
突然发现一个问题,我是依次bfs,但是我把沿途节点的值都保存了下来,我的复杂度应该也是mn

补充内容 (2015-9-19 03:19):
我跟他说了,他说我这样有的元素可能不是小的path,当时没想明白就说maybe,不过现在想来不可能啊,每个节点我都是bfs,一定是最小路径,完了感觉被坑了。。

补充内容 (2015-9-19 03:50):
无视这楼。。。我傻逼了,还是(mn)^2
回复 支持 反对

使用道具 举报

juslun 发表于 2015-9-19 03:42:36 | 显示全部楼层
楼主怎么把沿途的值保存
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-19 03:50:38 | 显示全部楼层
juslun 发表于 2015-9-19 03:42
楼主怎么把沿途的值保存
. 1point 3acres 论坛
恩不行。。当时太紧张了没想通
回复 支持 反对

使用道具 举报

juslun 发表于 2015-9-19 04:04:54 | 显示全部楼层
hj867955629 发表于 2015-9-19 03:50
恩不行。。当时太紧张了没想通

我的想法是只有邻居是bfs过的点才能优化。。  感谢分享,要祝lz好运
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-19 04:06:21 | 显示全部楼层
juslun 发表于 2015-9-19 04:04
我的想法是只有邻居是bfs过的点才能优化。。  感谢分享,要祝lz好运

对。。正确做法是从G开始把周围元素加1,再从所有1开始把1周围的所有元素加1,一个队列就行了。。唉
回复 支持 反对

使用道具 举报

larry_cn 发表于 2015-9-19 04:09:59 | 显示全部楼层
感觉可以 把所有的G 当成是 bfs 初试入 queue的 点
然后 就开始 bfs
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

LawranceH 发表于 2015-9-19 04:33:20 | 显示全部楼层
这是我写的,你们看看, 我就是把所有G 当成bfs 开始点, 每个level 附近的点加1.  当 当前点已经不是0的时候, 比较当前点的值 和 要 加的level, 取最小的赋值。 复杂度 为 G的个数*M*N.
  1.         public char[][] minMatrix(char[][] m) {.留学论坛-一亩-三分地
  2.                 for(int i = 0; i < m.length; i++) {
  3.                         for(int j = 0; j < m[0].length; j++) {
  4.                                 if(m[i][j] == 'G') {
  5.                                         bfs(m,i,j);
  6.                                 }
  7.                         } 来源一亩.三分地论坛.
  8.                 }
  9.                 return m;
  10.                 . 1point3acres
  11.         }
  12.     static final int[] directionX = {+1, -1, 0, 0};
  13.     static final int[] directionY = {0, 0, +1, -1};. 围观我们@1point 3 acres
  14.    
  15.         public void bfs(char[][] m,int i,int j) {. From 1point 3acres bbs
  16.                 Queue<Cell> q = new LinkedList<Cell>();
  17.                 int level = 1;
  18.                 boolean[][] vis = new boolean[m.length][m[0].length];
  19.                 q.offer(new Cell(i,j));
  20.                 vis[i][j] = true;. 一亩-三分-地,独家发布
  21.                 while(!q.isEmpty()) {
  22.                         int size = q.size();
  23.                         for(int z = 0; z < size; z ++) {
    .本文原创自1point3acres论坛
  24.                                 Cell cell = q.poll(); 来源一亩.三分地论坛.
  25.                         for (int b = 0; b < directionX.length; b++) {
  26.                             int x = cell.i + directionX[b];
  27.                             int y = cell.j + directionY[b];
  28.                             . more info on 1point3acres
  29.                             // check validity
  30.                             if (x >= 0 && x < m.length && y >= 0 && y < m[0].length && m[x][y] != 'G' && m[x][y] != 'B' &&!vis[x][y]) {
  31.                                     vis[x][y] = true;
  32.                                 if(m[x][y] == '0') {
  33.                                         m[x][y] = (char)(level + '0');
    . From 1point 3acres bbs
  34.                                 } else {
  35.                                         int now = (m[x][y]) - ('0');
  36.                                         m[x][y] =  now > level ? (char)(level + '0') : m[x][y];.1point3acres网
  37.                                 }
  38.                                 q.add(new Cell(x,y));
  39.                             }
  40.                         }.留学论坛-一亩-三分地
  41.                         
    . 1point3acres
  42.                         }. 一亩-三分-地,独家发布

  43.                         level ++;. 一亩-三分-地,独家发布
  44.                        
  45.                 }
  46.                
  47.         }
  48.         class Cell {
  49.                 int i;
  50.                 int j;
  51.                 public Cell(int i, int j) {
  52.                         this.i = i;
  53.                         this.j = j;
  54.                 }
  55.         }
复制代码
当前点已经有
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-19 04:36:27 | 显示全部楼层
LawranceH 发表于 2015-9-19 04:33
这是我写的,你们看看, 我就是把所有G 当成bfs 开始点, 每个level 附近的点加1.  当 当前点已经不是0的时 ...

我上面说了呀,从G开始更新周围的节点为1,然后从值为1的节点更新周围节点为2,这样是mn复杂度
回复 支持 反对

使用道具 举报

ww55201 发表于 2015-9-19 04:52:08 | 显示全部楼层
健神必过,必过,必过
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-20 14:15:22 | 显示全部楼层
LawranceH 发表于 2015-9-19 04:33
这是我写的,你们看看, 我就是把所有G 当成bfs 开始点, 每个level 附近的点加1.  当 当前点已经不是0的时 ...
来源一亩.三分地论坛.
那个..那个....
你用vis确保一个点只访问一次么?

如果是...那么你里面有!vis[x][y]的那个if 就进不去了..怎么update 里面的值, 如果找到更小的....
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-20 15:17:49 | 显示全部楼层
这个输入格式怎么给啊
回复 支持 反对

使用道具 举报

notturno 发表于 2015-9-21 11:17:24 | 显示全部楼层
hj867955629 发表于 2015-9-19 04:36
我上面说了呀,从G开始更新周围的节点为1,然后从值为1的节点更新周围节点为2,这样是mn复杂度
. 牛人云集,一亩三分地
不好意思,没太明白
.留学论坛-一亩-三分地
这个思路怎么保证结果是正确的,1周围的节点不一定是2啊

不太清楚m*n复杂度怎么实现
回复 支持 反对

使用道具 举报

OracleDesire 发表于 2015-9-21 11:42:38 | 显示全部楼层
大概这样?
  1. class Solution(object):. 牛人云集,一亩三分地
  2.     def minDistance(self, board):
  3.         m, n = len(board), len(board[0])
  4.         
  5.         for i in xrange(m):
  6.             for j in xrange(n):. from: 1point3acres
  7.                 if board[i][j] == 'G':
  8.                     self.bfs(board, i, j)
  9.                     
  10.     def bfs(self, board, i, j):. more info on 1point3acres
  11.         m, n = len(board), len(board[0])
  12.         queue = [(i, j)]
  13.         . 1point3acres
  14.         while queue:
  15.             i, j = queue.pop(0)
  16.             distance = 0 if board[i][j] == 'G' else board[i][j]
  17.             if j - 1 >= 0:
  18.                 if board[i][j - 1] == 'B' or board[i][j - 1] == 'G':
  19.                     pass
  20.                 elif board[i][j - 1] == 0 or board[i][j - 1] > distance + 1:
  21.                     board[i][j - 1] = distance + 1
  22.                     queue.append((i, j - 1))
  23.             if i - 1 >= 0:
  24.                 if board[i - 1][j] == 'B' or board[i - 1][j] == 'G':.留学论坛-一亩-三分地
  25.                     pass
  26.                 elif board[i - 1][j] == 0 or board[i - 1][j] > distance + 1:
  27.                     board[i - 1][j] = distance + 1
  28.                     queue.append((i - 1, j))
  29.             if j + 1 < n:
  30.                 if board[i][j + 1] == 'B' or board[i][j + 1] == 'G':
  31.                     pass
  32.                 elif board[i][j + 1] == 0 or board[i][j + 1] > distance + 1:
  33.                     board[i][j + 1] = distance + 1
  34.                     queue.append((i, j + 1)). 1point 3acres 论坛
  35.             if i + 1 < m:
  36.                 if board[i + 1][j] == 'B' or board[i + 1][j] == 'G':
  37.                     pass
  38.                 elif board[i + 1][j] == 0 or board[i + 1][j] > distance + 1:. 1point 3acres 论坛
  39.                     board[i + 1][j] = distance + 1
  40.                     queue.append((i + 1, j))

  41. s = Solution()
  42. board = [[0, 0, 0], ['B', 'G', 'G'], [0, 0, 0]]
  43. s.minDistance(board)
  44. print board
复制代码
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 11:51:02 | 显示全部楼层
flexwang 发表于 2015-9-20 15:17. 留学申请论坛-一亩三分地
这个输入格式怎么给啊

格式就是二维数组,里面有G, B, 0. B是障碍,求所有0到G的最近距离。. Waral 博客有更多文章,
比如
0 0 0
B G G
0 0 0
返回:
2 1 1
-1 0 0
2 1 1
回复 支持 反对

使用道具 举报

readman 发表于 2015-9-21 11:56:17 | 显示全部楼层
.1point3acres网
这个好像是对的, 也剪枝了
回复 支持 反对

使用道具 举报

flexwang 发表于 2015-9-21 12:01:52 | 显示全部楼层
hj867955629 发表于 2015-9-21 11:51
格式就是二维数组,里面有G, B, 0. B是障碍,求所有0到G的最近距离。
比如
0 0 0

数组里又有数字又有字母吗 好不科学
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 12:02:44 | 显示全部楼层
class Solution2 {
        class Point {
                int x;
                int y;
                public Point(int x, int y) {
                        this.x = x;
                        this.y = y;
                }. 留学申请论坛-一亩三分地
        }
       
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] minDis(char[][] board) {. 牛人云集,一亩三分地
                int wid = board.length, len = board[0].length;
                int[][] res = new int[wid][len];
                for (int j = 0; j < wid; j++) {. 1point3acres
                        for (int i = 0; i < len; i++) {
                                res[j][i] = Integer.MAX_VALUE;
                        }.1point3acres网
                }
                Queue<Point> q = new LinkedList<>();
                for (int j = 0; j < wid; j++) {
                        for (int i = 0; i < len; i++) {. 1point 3acres 论坛
                                if (board[j][i] == 'B') {
                                        res[j][i] = -1;
                                }
                                else if (board[j][i] == 'G') {
                                        res[j][i] = 0;.本文原创自1point3acres论坛
                                        q.offer(new Point(j, i));
                                }. from: 1point3acres
                        }
                }
                int lens = 1;
                while (!q.isEmpty()) {
                        int size = q.size();
                        for (int l = 0; l < size; l++) {
                                Point cur = q.poll();
                                for (int k = 0; k < 4; k++) {
                                        int j = cur.x+dir[k][0], i = cur.y+dir[k][1];
                                        if (j < 0 || j >= wid || i < 0 || i >= len || res[j][i] != Integer.MAX_VALUE) {
                                                continue;
                                        }
                                        res[j][i] = lens;
                                        q.offer(new Point(j, i));. 1point 3acres 论坛
                                }
                        }
                        lens++;. 一亩-三分-地,独家发布
                }
                return res;
        }
}
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 12:03:35 | 显示全部楼层

不会python...
回复 支持 反对

使用道具 举报

wyc25013 发表于 2015-9-24 09:10:54 | 显示全部楼层
请问一下店面后面是直接onsite吗 还是第二轮店面
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

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

custom counter

GMT+8, 2018-5-20 20:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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