一亩三分地论坛

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

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

Bloomberg 电面

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

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

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

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

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

给定matrix,
0 0 0
B G G
0 0 0
找到每个0到G的最短距离,B是障碍。. 1point 3acres 璁哄潧
输出:
2 1 1
B G G
2 1 1
虽然在提示下最后讲出了最优解,可是时间都快没了。感觉不好。唉求加米安慰下。



补充内容 (2015-9-21 23:44):. more info on 1point3acres.com
刚收到邮件,电面过了

评分

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. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主怎么把沿途的值保存

恩不行。。当时太紧张了没想通
回复 支持 反对

使用道具 举报

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好运
.鏈枃鍘熷垱鑷1point3acres璁哄潧
对。。正确做法是从G开始把周围元素加1,再从所有1开始把1周围的所有元素加1,一个队列就行了。。唉
回复 支持 反对

使用道具 举报

larry_cn 发表于 2015-9-19 04:09:59 | 显示全部楼层
感觉可以 把所有的G 当成是 bfs 初试入 queue的 点. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
然后 就开始 bfs
回复 支持 反对

使用道具 举报

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.                
  11.         }
  12.     static final int[] directionX = {+1, -1, 0, 0};. 1point 3acres 璁哄潧
  13.     static final int[] directionY = {0, 0, +1, -1};. 1point 3acres 璁哄潧
  14.    
  15.         public void bfs(char[][] m,int i,int j) {-google 1point3acres
  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;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  21.                 while(!q.isEmpty()) {. 1point 3acres 璁哄潧
  22.                         int size = q.size();
  23.                         for(int z = 0; z < size; z ++) {
  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.                            
  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');
  34.                                 } else {-google 1point3acres
  35.                                         int now = (m[x][y]) - ('0');
  36.                                         m[x][y] =  now > level ? (char)(level + '0') : m[x][y];
  37.                                 }
  38.                                 q.add(new Cell(x,y));
  39.                             }
  40.                         }
  41.                         
  42.                         }

  43.                         level ++;
  44.                        
  45.                 }
  46.                
  47.         }
  48.         class Cell {
  49.                 int i;
  50.                 int j;
  51.                 public Cell(int i, int j) {
    . more info on 1point3acres.com
  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.         . 鍥磋鎴戜滑@1point 3 acres
  5.         for i in xrange(m):
  6.             for j in xrange(n):
  7.                 if board[i][j] == 'G':
  8.                     self.bfs(board, i, j)-google 1point3acres
  9.                     
  10.     def bfs(self, board, i, j):
  11.         m, n = len(board), len(board[0])
  12.         queue = [(i, j)]
  13.         
  14.         while queue:
  15.             i, j = queue.pop(0)
  16.             distance = 0 if board[i][j] == 'G' else board[i][j]
    . visit 1point3acres.com for more.
  17.             if j - 1 >= 0:. 鍥磋鎴戜滑@1point 3 acres
  18.                 if board[i][j - 1] == 'B' or board[i][j - 1] == 'G':. 1point 3acres 璁哄潧
  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)). visit 1point3acres.com for more.
  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))
  35.             if i + 1 < m:-google 1point3acres
  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: 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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的最近距离。. 1point3acres.com/bbs
比如
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 | 显示全部楼层

这个好像是对的, 也剪枝了
回复 支持 反对

使用道具 举报

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 {. more info on 1point3acres.com
                int x;
                int y;
                public Point(int x, int y) {
                        this.x = x;
                        this.y = y;
                }
        }
        .1point3acres缃
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int[][] minDis(char[][] board) {
                int wid = board.length, len = board[0].length;. 1point3acres.com/bbs
                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;
                        }. from: 1point3acres.com/bbs
                }
                Queue<Point> q = new LinkedList<>();
                for (int j = 0; j < wid; j++) {
                        for (int i = 0; i < len; i++) {
                                if (board[j][i] == 'B') {. more info on 1point3acres.com
                                        res[j][i] = -1;
                                }
                                else if (board[j][i] == 'G') {
                                        res[j][i] = 0;
                                        q.offer(new Point(j, i));
                                } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }. 1point3acres.com/bbs
                }
                int lens = 1;
-google 1point3acres                while (!q.isEmpty()) {
                        int size = q.size();
                        for (int l = 0; l < size; l++) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                                Point cur = q.poll();
. 1point3acres.com/bbs                                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));
                                }
                        }
                        lens++;
                }
                return res;
        }
}
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 06:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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