《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 4114|回复: 25
收起左侧

Bloomberg 电面

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

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

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

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

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

给定matrix,
0 0 0
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.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的 点
然后 就开始 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);
    . From 1point 3acres bbs
  6.                                 }
  7.                         }
  8.                 }
  9.                 return m;
  10.                 . 1point 3acres 璁哄潧
  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>();. 鍥磋鎴戜滑@1point 3 acres
  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 ++) {
  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 {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                                         int now = (m[x][y]) - ('0');
  36.                                         m[x][y] =  now > level ? (char)(level + '0') : m[x][y];. more info on 1point3acres.com
  37.                                 }
  38.                                 q.add(new Cell(x,y));
  39.                             }
  40.                         }
  41.                         . visit 1point3acres.com for more.
  42.                         }
  43. . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  44.                         level ++;
  45.                        
  46.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  47.                
  48.         }
  49.         class Cell {
  50.                 int i;
  51.                 int j; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  52.                 public Cell(int i, int j) {
  53.                         this.i = i;
  54.                         this.j = j;
  55.                 } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  56.         }
复制代码
当前点已经有
回复 支持 反对

使用道具 举报

 楼主| 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复杂度

不好意思,没太明白
. 1point 3acres 璁哄潧
这个思路怎么保证结果是正确的,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):
    . 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]. from: 1point3acres.com/bbs
  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:. 1point3acres.com/bbs
  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:.1point3acres缃
  33.                     board[i][j + 1] = distance + 1.鏈枃鍘熷垱鑷1point3acres璁哄潧
  34.                     queue.append((i, j + 1))
  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:
  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的最近距离。
比如
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 {
                int x;
                int y;
. 1point 3acres 璁哄潧                public Point(int x, int y) {
                        this.x = x;
                        this.y = y;
                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
        }
       
        int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};. more info on 1point3acres.com
        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; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                }
                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();
                        for (int l = 0; l < size; l++) {
                                Point cur = q.poll();.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                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) {. more info on 1point3acres.com
                                                continue;
                                        }
                                        res[j][i] = lens;
                                        q.offer(new Point(j, i));. 鍥磋鎴戜滑@1point 3 acres
                                }
                        }
                        lens++;
                }
                return res;
        }
}
回复 支持 反对

使用道具 举报

 楼主| hj867955629 发表于 2015-9-21 12:03:35 | 显示全部楼层
OracleDesire 发表于 2015-9-21 11:42 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
大概这样?
.1point3acres缃
不会python...
回复 支持 反对

使用道具 举报

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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 10:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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