一亩三分地论坛

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

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

Youtube/Google 11/23电面

[复制链接] |试试Instant~ |关注本帖
xiaoniuona 发表于 2015-12-1 00:35:03 | 显示全部楼层 |阅读模式

2015(10-12月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
挺nice的一个中国大姐,在google干了7年了~上来什么也没问直接做题
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
1. plus one,no negative number
2. input是一个二维char数组代表一个gym,#是wall,不能通过,*是健身器材,其他都是空格,要求找一个空格到所有*的距离最短. from: 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
求onsite啊!!!
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

评分

1

查看全部评分

queeniejing 发表于 2015-12-1 02:29:48 | 显示全部楼层
谢谢LZ 分享, 请问你的第二题是 用BFS 做吗
回复 支持 反对

使用道具 举报

hyliu0000 发表于 2015-12-1 04:39:08 | 显示全部楼层
同问第二题。  目测是建立二维数组记录, dfs or bfs, 然后遍历数组得到最小
回复 支持 反对

使用道具 举报

queqichao 发表于 2015-12-1 05:34:26 | 显示全部楼层
第二题,建立一个2d table of int,然后从每一个健身器材开始BFS,对每个非wall cell对应的table里面cell累加到起始健身器材的距离。然后扫一遍table里面所有cell,找到距离之和最小的一个。
回复 支持 反对

使用道具 举报

 楼主| xiaoniuona 发表于 2015-12-1 05:51:02 | 显示全部楼层
queeniejing 发表于 2015-12-1 02:29
谢谢LZ 分享, 请问你的第二题是 用BFS 做吗

是的,参考LC那道walls and gates,这道题就是每次bfs不是找最小距离,而是把距离加起来
回复 支持 反对

使用道具 举报

 楼主| xiaoniuona 发表于 2015-12-1 05:51:48 | 显示全部楼层
hyliu0000 发表于 2015-12-1 04:39
同问第二题。  目测是建立二维数组记录, dfs or bfs, 然后遍历数组得到最小
. more info on 1point3acres.com
bfs,我和3楼做法差不多
回复 支持 反对

使用道具 举报

ssross 发表于 2015-12-1 10:53:20 | 显示全部楼层
xiaoniuona 发表于 2015-12-1 05:51
是的,参考LC那道walls and gates,这道题就是每次bfs不是找最小距离,而是把距离加起来

请问一下LC 那道题不是只能求每个非wall的cell到一个最近的gate的距离吗?怎么样在bfs的时候求一个cell到所有gate的累加的距离的和?
回复 支持 反对

使用道具 举报

 楼主| xiaoniuona 发表于 2015-12-2 07:21:12 | 显示全部楼层
ssross 发表于 2015-12-1 10:53
请问一下LC 那道题不是只能求每个非wall的cell到一个最近的gate的距离吗?怎么样在bfs的时候求一个cell到 ...

从每个gate开始bfs,到一个cell的时候,update的不是更小的距离,而是把这次的距离累加上去。等到所有bfs结束,每个cell上就是到所有gate的距离的和了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-2 23:46:39 | 显示全部楼层
写了下代码,有个问题是当计算从*到其他地方的位置时,可以经过'*'的吗?还是需要绕开?代码为可以经过的情况
  1. public class GymAndWall {

  2.         public static void main(String[] args) {
  3.                 GymAndWall gaw = new GymAndWall();. Waral 鍗氬鏈夋洿澶氭枃绔,
  4.                 char[][] matrix =  {{' ', ' ', ' ', ' '},
  5.                                                         {' ', '*', ' ', ' '},
  6.                                                         {' ', ' ', '*', '#'},
  7.                                                         {' ', '#', '*', ' '},};
  8.                 int[] res = gaw.findShortestDistance(matrix);
  9.                 System.out.println(res[0]);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  10.                 System.out.println(res[1]);
  11.                 // 1 2
  12.         }
  13.        
  14.         public int[] findShortestDistance(char[][] matrix) {
  15.                 int[] res = new int[2];
  16.                 res[0] = -1;
  17.                 res[1] = -1;
  18.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  19.                         return res;
  20.                 }
  21.                 int m = matrix.length;
  22.                 int n = matrix[0].length;. From 1point 3acres bbs
  23.                 int[][] dis = new int[m][n];
  24.                 boolean[][] visited = new boolean[m][n];
  25.                 for (int i = 0; i < m; i++) {
  26.                         for (int j = 0; j < n; j++) {
  27.                                 for (boolean[] row : visited) {
  28.                                         Arrays.fill(row, false);
  29.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  30.                                 if (matrix[i][j] == '*') {
  31.                                         bfs(matrix, i, j, dis, visited);
  32.                                 }. from: 1point3acres.com/bbs
  33.                         }
  34.                 }
  35.                 int min = Integer.MAX_VALUE;
  36.                 for (int i = 0; i < m; i++) {
  37.                         for (int j = 0; j < n; j++) {
  38.                                 if (matrix[i][j] == ' ') {
  39.                                         if (dis[i][j] < min) {. from: 1point3acres.com/bbs
  40.                                                 min = dis[i][j];
  41.                                                 res[0] = i; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  42.                                                 res[1] = j;
  43.                                         }
  44.                                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  45.                         }
  46.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  47.                 for (int[] arr : dis) {
  48.                         for (int i : arr) {
  49.                                 System.out.print(i + " ");
  50.                         }
  51.                         System.out.println();
  52.                 }
  53.                
  54.                 return res;. more info on 1point3acres.com
  55.         }.1point3acres缃

  56.         private int[] dx = {1, -1, 0, 0};
    鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  57.         private int[] dy = {0, 0, 1, -1};.鏈枃鍘熷垱鑷1point3acres璁哄潧
  58.         private void bfs(char[][] matrix, int i, int j, int[][] dis, boolean[][] visited) {
  59.                 if (i < 0 || i >= matrix[0].length || j < 0 || j >= matrix[0].length || matrix[i][j] == '#' || visited[i][j]) {
  60.                         return;
  61.                 }
  62.                 Queue<Integer> queue = new LinkedList<Integer>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  63.                 int len = matrix[0].length;
  64.                 int code = i * len + j;
  65.                 visited[i][j] = true;
  66.                 queue.offer(code);. From 1point 3acres bbs
  67.                 int step = 0;
  68.                 while (!queue.isEmpty()) {
  69.                         int size = queue.size();
  70.                         for (int k = 0; k < size; k++) {
  71.                                 code = queue.poll();
  72.                                 int x = code / len;
  73.                                 int y = code % len;
  74. //                                System.out.println(x + " " + y);
  75.                                 dis[x][y] += step;
  76.                                 for (int index = 0; index < dx.length; index++) {
  77.                                         int nx = x + dx[index];
  78.                                         int ny = y + dy[index];
  79.                                         if (nx >= 0 && nx < matrix.length && ny >= 0 && ny < matrix[0].length && !visited[nx][ny] && matrix[i][j] != '#') {
  80.                                                 queue.offer(nx * len + ny);
  81.                                                 visited[nx][ny] = true;
  82.                                         }
  83.                                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  84.                         }
  85.                         step++;
  86.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  87.         }
  88. }
复制代码

补充内容 (2015-12-2 23:47):.鏈枃鍘熷垱鑷1point3acres璁哄潧
dfs应该不行吧,步数没法控制
回复 支持 反对

使用道具 举报

ssross 发表于 2015-12-3 03:01:35 | 显示全部楼层
自己也写了个。就是对每个‘*’进行BFS!最后把distance累加起来。
  1. /*

  2. '#' stands for obstacle, ' ' is path, and '*' is target. Get one cell in the matrix except obstacles which
  3.         has the shorest distance to all the targets.

  4.         idea: do BFS from each target and obtain the distance to all the other cells. Culmulate the sum of . 1point3acres.com/bbs
  5.         distance to an overall dis matrix. The least sum would be the shortest distance cell.

  6.         Time: O(k * mn) where mn is the cell numbers and k is number of targets.

  7. */
  8. public class getAllShorestDist {
  9.         sprivate static final int[][] DIRECTIONS = new int[][] { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
  10. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.         public static void main(String[] args) {

  12.                 char[][] matrix =  {{' ', '#', '*', ' '},
  13.                                         {' ', ' ', ' ', '#'},
  14.                                         {' ', '#', ' ', '#'},
  15.                                         {'*', '#', ' ', ' '}};
  16.                 getShortestDist(matrix);
  17.                 . 鍥磋鎴戜滑@1point 3 acres
  18.         }

  19.         public static void getShortestDist(char[][] matrix) {. more info on 1point3acres.com
  20.                 if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
  21.                         return;
  22.                
  23.                 int m = matrix.length;
  24.                 int n = matrix[0].length;
  25.                 int[][] dis = new int[m][n];
  26.                 boolean[][] visited = new boolean[m][n];
  27.                 for(int i = 0; i < m; i++) {
  28.                         for(int j = 0; j < n; j++) {
  29.                                 for(boolean[] row : visited)-google 1point3acres
  30.                                         Arrays.fill(row, false);
  31.                                 if(matrix[i][j] == '*') {
  32.                                         int[][] curDis = new int[m][n];
  33.                                         bfs(matrix, i, j, curDis, visited);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  34.                                         sumDistance(dis, curDis, matrix);. from: 1point3acres.com/bbs
  35.                                 }
  36.                         }
  37.                 }. 1point 3acres 璁哄潧
  38.                
  39.                 for(int k = 0; k < m; k++) {
  40.                         System.out.println(Arrays.toString(dis[k]));
  41.                 }
  42.         }
  43. . visit 1point3acres.com for more.
  44.         private static void bfs(char[][] matrix, int i, int j, int[][] curDis, boolean[][] visited) {
  45.                 Queue<int[]> queue = new LinkedList<int[]>();
  46.                 queue.offer(new int[] { i, j });
  47.                 visited[i][j] = true;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  48.                 .鏈枃鍘熷垱鑷1point3acres璁哄潧
  49.                 while(!queue.isEmpty()) {
  50.                         int[] point = queue.poll();
  51.                         int row = point[0];
  52.                         int col = point[1];
  53.                         for(int[] direction : DIRECTIONS) {
  54.                                 int r = row + direction[0];
  55.                                 int c = col + direction[1];
  56.                                 if(r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length ||
  57.                                                 visited[r][c] || matrix[r][c] == '#'). more info on 1point3acres.com
  58.                                         continue;
  59.                                 curDis[r][c] = curDis[row][col] + 1;
  60.                                 visited[r][c] = true;
  61.                                 queue.offer(new int[] { r, c });
  62.                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  63.                 }
  64.         }

  65.         public static void sumDistance(int[][] dis, int[][] curDis, char[][] matrix) {
  66.                 for(int i = 0; i < curDis.length; i++) {
  67.                         for(int j = 0; j < curDis[0].length; j++) {
  68.                                 if(matrix[i][j] != '#')
  69.                                         dis[i][j] += curDis[i][j];
  70.                         }
  71.                 }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  72.         }
  73. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-3 03:48:10 | 显示全部楼层
ssross 发表于 2015-12-3 03:01
自己也写了个。就是对每个‘*’进行BFS!最后把distance累加起来。

这代码的时间复杂度是O(n^4)?
回复 支持 反对

使用道具 举报

ssross 发表于 2015-12-3 03:52:57 | 显示全部楼层
bobzhang2004 发表于 2015-12-3 03:48
这代码的时间复杂度是O(n^4)?

没有这么大。他只从target开始bfs。每个bfs是O(n^2)所以其实总的就是O(k * n^2),k是target的数量!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-3 06:19:57 | 显示全部楼层
ssross 发表于 2015-12-3 03:52
没有这么大。他只从target开始bfs。每个bfs是O(n^2)所以其实总的就是O(k * n^2),k是target的数量!

但是你的sumDistance(dis, curDis, matrix);,是在两重for循环中,感觉如果要做到O(k * n^2),得用hashset来保存是否访问过,因为Arrays.fill也是在三重循环中
回复 支持 反对

使用道具 举报

 楼主| xiaoniuona 发表于 2015-12-3 07:17:20 | 显示全部楼层
bobzhang2004 发表于 2015-12-2 23:46.鏈枃鍘熷垱鑷1point3acres璁哄潧
写了下代码,有个问题是当计算从*到其他地方的位置时,可以经过'*'的吗?还是需要绕开?代码为可以经过的情 ...
-google 1point3acres
不可以,要绕开*
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-16 21:25

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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