推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

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

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

Bloomberg 电面

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

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

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

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

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

给定matrix,
0 0 0
B G G. 鍥磋鎴戜滑@1point 3 acres
0 0 0
找到每个0到G的最短距离,B是障碍。
输出:
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 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
LawranceH 发表于 2015-9-19 04:33
这是我写的,你们看看, 我就是把所有G 当成bfs 开始点, 每个level 附近的点加1.  当 当前点已经不是0的时 ...

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

使用道具 举报

 楼主| hj867955629 发表于 2015-9-19 03:18:11 | 显示全部楼层
关注一亩三分地微博:
Warald
突然发现一个问题,我是依次bfs,但是我把沿途节点的值都保存了下来,我的复杂度应该也是mn.鏈枃鍘熷垱鑷1point3acres璁哄潧

补充内容 (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好运

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

使用道具 举报

larry_cn 发表于 2015-9-19 04:09:59 | 显示全部楼层
感觉可以 把所有的G 当成是 bfs 初试入 queue的 点. more info on 1point3acres.com
然后 就开始 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.                         }. 1point 3acres 璁哄潧
  8.                 }
  9.                 return m;
  10.                 . From 1point 3acres bbs
  11.         }
  12.     static final int[] directionX = {+1, -1, 0, 0};
  13.     static final int[] directionY = {0, 0, +1, -1};
  14.    
  15.         public void bfs(char[][] m,int i,int j) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  16.                 Queue<Cell> q = new LinkedList<Cell>();-google 1point3acres
  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();.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                         for(int z = 0; z < size; z ++) {
  24.                                 Cell cell = q.poll();
  25.                         for (int b = 0; b < directionX.length; b++) {. more info on 1point3acres.com
  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 {
  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.                         . Waral 鍗氬鏈夋洿澶氭枃绔,
  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复杂度

不好意思,没太明白
.鏈枃鍘熷垱鑷1point3acres璁哄潧
这个思路怎么保证结果是正确的,1周围的节点不一定是2啊

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

使用道具 举报

OracleDesire 发表于 2015-9-21 11:42:38 | 显示全部楼层
大概这样?
  1. class Solution(object):. Waral 鍗氬鏈夋洿澶氭枃绔,
  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):. 1point 3acres 璁哄潧
  7.                 if board[i][j] == 'G':
  8.                     self.bfs(board, i, j)
  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]
  17.             if j - 1 >= 0:
  18.                 if board[i][j - 1] == 'B' or board[i][j - 1] == 'G':-google 1point3acres
  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. visit 1point3acres.com for more.
  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.1point3acres缃
  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:. 鍥磋鎴戜滑@1point 3 acres
  36.                 if board[i + 1][j] == 'B' or board[i + 1][j] == 'G':. 1point 3acres 璁哄潧
  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).鏈枃鍘熷垱鑷1point3acres璁哄潧
  44. print board
复制代码
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 11:51:02 | 显示全部楼层
flexwang 发表于 2015-9-20 15:17
这个输入格式怎么给啊

格式就是二维数组,里面有G, B, 0. B是障碍,求所有0到G的最近距离。
比如
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. From 1point 3acres bbs
格式就是二维数组,里面有G, B, 0. B是障碍,求所有0到G的最近距离。
比如
0 0 0

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

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 12:02:44 | 显示全部楼层
class Solution2 {
        class Point {. 1point3acres.com/bbs
                int x;
                int y;
                public Point(int x, int y) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        this.x = x;
                        this.y = y;
                }. 1point3acres.com/bbs
        }
       
        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++) {
                        for (int i = 0; i < len; i++) {
                                res[j][i] = Integer.MAX_VALUE;
                        }. 1point 3acres 璁哄潧
                }
                Queue<Point> q = new LinkedList<>();
                for (int j = 0; j < wid; j++) {
                        for (int i = 0; i < len; i++) {
                                if (board[j][i] == 'B') {
                                        res[j][i] = -1;
                                }
                                else if (board[j][i] == 'G') {
                                        res[j][i] = 0;
                                        q.offer(new Point(j, i));
                                }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        }
                }
                int lens = 1;
                while (!q.isEmpty()) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        int size = q.size();. more info on 1point3acres.com
                        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));
                                }
                        }
                        lens++;
                }. 1point 3acres 璁哄潧
                return res;
        }
}
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 12:03:35 | 显示全部楼层
OracleDesire 发表于 2015-9-21 11:42. 1point3acres.com/bbs
大概这样?

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

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-7-28 03:12

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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