11月Google和BLOOMBERG实习电面

bobzhang2004 发表于 2015-11-27 02:14
那个data steam的应该是bucket计数吧，请问楼主那个island周长的是怎么做的？

划完岛了以后DFS

wjf1990 发表于 2015-11-27 02:19
划完岛了以后DFS

楼主可以具体说一下吗？因为岛的形状可能出现多边形啊，这样的话不好算吧？

bobzhang2004 发表于 2015-11-27 05:14
楼主可以具体说一下吗？因为岛的形状可能出现多边形啊，这样的话不好算吧？

我觉得是这样的。即使是多边形，计算周长的时候也是可以把他看成是矩形的，这个矩形就是这个多边形的最小外包矩形。然后矩形的四个点的坐标，就是多边行四个方向的最值。

jkingxt 发表于 2015-11-27 06:39
我觉得是这样的。即使是多边形，计算周长的时候也是可以把他看成是矩形的，这个矩形就是这个多边形的最小 ...

duide   jiushizhwyang

写了下max island size，欢迎指教

1. public class IslandMaximumSize {
   
2. 
   
3.         public static void main(String[] args) {
   
4.                 int[][] matrix =   {{0, 0, 1, 0},
   
5.                                                         {0, 1, 0, 1},
   
6.                                                         {0, 1, 0, 1},
   
7.                                                         {1, 0, 0, 0},};
   
8.                 getIslandMaximumSize(matrix);
   
9.         }
   
10.        
    
11.         public static int getIslandMaximumSize(int[][] matrix) {
    
12.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
13.                         return 0;
    
14.                 }
    
15.                 int res = 0;
    
16.                 for (int i = 0; i < matrix.length; i++) {
    
17.                         for (int j = 0; j < matrix[0].length; j++) {
    
18.                                 if (matrix[i][j] == 1) {
    
19.                                         res = Math.max(res, helper(matrix, i, j));
    
20.                                 }
    
21.                         }
    
22.                 }
    
23.                
    
24.                 System.out.println(res);
    
25.                 return res;
    
26.         }
    
27.         private static int helper(int[][] matrix, int i, int j) {
    
28.                 if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != 1) {
    
29.                         return 0;
    
30.                 }
    
31.                 matrix[i][j] = 2;
    
32.                 int size = 1;
    
33.                 int[] dx = {1, -1, 0, 0};
    
34.                 int[] dy = {0, 0, 1, -1};
    
35.                 for (int k = 0; k < dx.length; k++) {
    
36.                         int x = i + dx[k];
    
37.                         int y = j + dy[k];
    
38.                         size += helper(matrix, x, y);
    
39.                 }
    
40.                
    
41.                 return size;
    
42.         }
    
43. }
    

复制代码

写了下max island perimeter的代码，电面考这个代码量真多啊。楼主代码中得输出应该是12? 欢迎指教。

1. public class IslandPerimeter {
   
2.         public static void main(String[] args) {
   
3.                 int[][] matrix =   {{0, 0, 1, 0},
   
4.                                                         {0, 1, 0, 1},
   
5.                                                         {0, 1, 1, 1},
   
6.                                                         {1, 0, 1, 0},};
   
7.                 int res = getMaxIslandPerimeter(matrix);
   
8.                 System.out.println("res " + res);
   
9.         }
   
10.        
    
11.         static class Direction {
    
12.                 int left;
    
13.                 int right;
    
14.                 int up;
    
15.                 int down;
    
16.                 public Direction(int left, int right, int up, int down) {
    
17.                         this.left = left;
    
18.                         this.right = right;
    
19.                         this.up = up;
    
20.                         this.down = down;
    
21.                 }
    
22.         }
    
23.        
    
24.         public static int getMaxIslandPerimeter(int[][] matrix) {
    
25.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
    
26.                         return 0;
    
27.                 }
    
28.                 int max = 0;
    
29.                 int x = -1;
    
30.                 int y = -1;
    
31.                 for (int i = 0; i < matrix.length; i++) {
    
32.                         for (int j = 0; j < matrix[0].length; j++) {
    
33.                                 if (matrix[i][j] == 1) {
    
34.                                         int size = helper(matrix, i, j);
    
35.                                         if (size > max) {
    
36.                                                 max = size;
    
37.                                                 x = i;
    
38.                                                 y = j;
    
39.                                         }
    
40.                                 }
    
41.                         }
    
42.                 }
    
43.                 Direction direction = new Direction(y, y, x, x);
    
44.                 if (x != -1 && y != -1) {
    
45.                         getPerimeter(matrix, x, y, direction);
    
46.                         return ((direction.down - direction.up + 1) + (direction.right - direction.left + 1)) * 2;
    
47.                 } else {
    
48.                         return 0;
    
49.                 }
    
50.         }
    
51.        
    
52.        
    
53.         private static void getPerimeter(int[][] matrix, int x, int y, Direction direction) {
    
54.                 if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] != 2) {
    
55.                         return;
    
56.                 }
    
57.                 matrix[x][y] = 1;
    
58.                 direction.down = Math.max(direction.down, x);
    
59.                 direction.up = Math.min(direction.up, x);
    
60.                 direction.left = Math.min(direction.left, y);
    
61.                 direction.right = Math.max(direction.right, y);
    
62.                 getPerimeter(matrix, x + 1, y, direction);
    
63.                 getPerimeter(matrix, x - 1, y, direction);
    
64.                 getPerimeter(matrix, x, y + 1, direction);
    
65.                 getPerimeter(matrix, x, y - 1, direction);
    
66.         }
    
67.        
    
68.        
    
69.         private static int helper(int[][] matrix, int i, int j) {
    
70.                 if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != 1) {
    
71.                         return 0;
    
72.                 }
    
73.                 matrix[i][j] = 2;
    
74.                 int size = 1;
    
75.                 int[] dx = {1, -1, 0, 0};
    
76.                 int[] dy = {0, 0, 1, -1};
    
77.                 for (int k = 0; k < dx.length; k++) {
    
78.                         int x = i + dx[k];
    
79.                         int y = j + dy[k];
    
80.                         size += helper(matrix, x, y);
    
81.                 }
    
82.                
    
83.                 return size;
    
84.         }
    
85. }
    

复制代码

bobzhang2004 发表于 2015-12-1 13:04
写了下max island perimeter的代码，电面考这个代码量真多啊。楼主代码中得输出应该是12? 欢迎指教。

应该是没错  我晚上回家看看

第二题：merge 2 unsorted array(in-place) 请问这个怎么in place做呢 谢谢

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies