一亩三分地论坛

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

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

11月Google和BLOOMBERG实习电面

[复制链接] |试试Instant~ |关注本帖
wjf1990 发表于 2015-11-25 12:11:09 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 博士 实习@Google - 网上海投 - 技术电面 |Passfresh grad应届毕业生

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

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

x
发帖求人品. Waral 鍗氬鏈夋洿澶氭枃绔,
11.9 GOOGLE:
第1轮:中国大哥,data stream of integer 0-999, write add() and median() function, makes them both run in O(1) time.没做出来,只做出了HEAP的
当天第2轮:美国小哥,num of island变种 求最大ISLAND的SIZE,做出来了,问了些他们GROUP的问题
第1轮面的不好,主动要求加面  第三轮被安排在16号
.鐣欏璁哄潧-涓浜-涓夊垎鍦
.1point3acres缃
11.12 BLOOMBERG
第一题:binary search in matrix, leetcode原题  简单
第二题:merge 2 unsorted array(in-place),其实很简单我做的复杂了,没做好
. 1point 3acres 璁哄潧

11.16 GOOGLE加面
第一题NUM OF ISLAND变种,求最大ISLAND的周长
第二题给个binary tree,每个NODE有个变量存着他下面child的个数,让我写o(logn)的in-order traversal(kth),只用stack写出了最简单的o(n) 没写出最佳


16号当天收到b家onsite
18号收到GOOGLE HOST MATCH通知

. Waral 鍗氬鏈夋洿澶氭枃绔,
另外跪求G家TEAM收留,跪求G家内推   我不想淹死在POOL里啊~ . 1point 3acres 璁哄潧

评分

2

查看全部评分

bobzhang2004 发表于 2015-12-2 07:43:12 | 显示全部楼层
reality 发表于 2015-12-2 00:35.1point3acres缃
请问这个解法为什么是o(1)呢?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2015-12-2 00:42):

写了下代码,因为1000是个constance,所以是O(1)
  1. public class DataStreamMedianII {
  2.        
  3.         private int[] nums;
  4.         private int total;
  5.        
  6.         public DataStreamMedianII() {
  7.                 nums = new int[1000];-google 1point3acres
  8.                 total = 0;
  9.         }
  10.         public void add(int num) {
  11.                 nums[num]++;
  12.                 total++;
  13.         }
  14.        
    . 1point3acres.com/bbs
  15.         public int median() {
  16.                 int mid = (total + 1) / 2;
  17.                 int count = 0;
  18.                 for (int i = 0; i < nums.length; i++) {
  19.                         int val = nums[i];
  20.                         count += val;
  21.                         if (count >= mid) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  22.                                 return i;
  23.                         }
  24.                 }
  25.                 . 鍥磋鎴戜滑@1point 3 acres
  26.                 return 0;
  27.         }. Waral 鍗氬鏈夋洿澶氭枃绔,
  28.        
  29.        
  30.         public static void main(String[] args) {
  31.                 DataStreamMedianII dm = new DataStreamMedianII();
  32.                 dm.add(1);
  33.                 System.out.println(dm.median());
  34.                 dm.add(2);
  35.                 System.out.println(dm.median());. 鍥磋鎴戜滑@1point 3 acres
  36.                 dm.add(3);
  37.                 System.out.println(dm.median());
  38.                 dm.add(3);
  39.                 System.out.println(dm.median());.鏈枃鍘熷垱鑷1point3acres璁哄潧
  40.                 dm.add(3);
  41.                 System.out.println(dm.median());
  42.         }
  43.        
  44. }
复制代码

补充内容 (2015-12-2 07:44):. 1point3acres.com/bbs
constant

评分

1

查看全部评分

回复 支持 2 反对 0

使用道具 举报

yingbich 发表于 2015-12-4 03:32:00 | 显示全部楼层
jkingxt 发表于 2015-11-27 06:39
我觉得是这样的。即使是多边形,计算周长的时候也是可以把他看成是矩形的,这个矩形就是这个多边形的最小 ...

我觉得这是不对的吧,只有当岛的形状是凸的时候两者才相等,如果岛是凹的就不对了。
我认为正确应该是DFS的时候 加一句记录有多少踩到海了,每踩到一次 就必然周长加1.
回复 支持 2 反对 0

使用道具 举报

bobzhang2004 发表于 2015-12-1 13:04:39 | 显示全部楼层
写了下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;. Waral 鍗氬鏈夋洿澶氭枃绔,
  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.                 }-google 1point3acres
  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.                 }. From 1point 3acres bbs
  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) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  71.                         return 0;
  72.                 }
  73.                 matrix[i][j] = 2;
  74.                 int size = 1;.1point3acres缃
  75.                 int[] dx = {1, -1, 0, 0};. Waral 鍗氬鏈夋洿澶氭枃绔,
  76.                 int[] dy = {0, 0, 1, -1};
  77.                 for (int k = 0; k < dx.length; k++) {
  78.                         int x = i + dx[k];. 鍥磋鎴戜滑@1point 3 acres
  79.                         int y = j + dy[k];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  80.                         size += helper(matrix, x, y);
  81.                 }
  82.                 . from: 1point3acres.com/bbs
  83.                 return size;
  84.         }
  85. }
复制代码
回复 支持 1 反对 0

使用道具 举报

千骨娜娜 发表于 2015-11-26 10:20:23 | 显示全部楼层
data stream of integer 0-999, write add() and median() function。这题用bucket? 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

用1000个bucket记录每个数字加入的count,add时就忘对应的bucket里面加1,同时记录总共add的个数n,求median时,就去逐个扫描bucket,并且算个accumulated count,等accumulated count刚好大于n/2,就可以找到median。
回复 支持 1 反对 0

使用道具 举报

corn 发表于 2015-11-25 14:02:28 | 显示全部楼层
主动要求加面是什么情况?楼主主动向recruiter要的第三面?
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-11-25 22:48:49 | 显示全部楼层
corn 发表于 2015-11-25 14:02
主动要求加面是什么情况?楼主主动向recruiter要的第三面?

是的,当时面的不好
回复 支持 反对

使用道具 举报

fireisborn 发表于 2015-11-25 23:13:40 | 显示全部楼层
原來可以這樣...早知道就要求加面了,受教...
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-11-25 23:21:33 | 显示全部楼层
fireisborn 发表于 2015-11-25 23:13. Waral 鍗氬鏈夋洿澶氭枃绔,
原來可以這樣...早知道就要求加面了,受教...

也看HR的吧  我不知道其他人怎么样
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-11-26 11:35:35 | 显示全部楼层
千骨娜娜 发表于 2015-11-26 10:20
data stream of integer 0-999, write add() and median() function。这题用bucket?

用1000个bucket记 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对的   面试官提醒了我好多都没做出来  求代码  哪里有原题吗
回复 支持 反对

使用道具 举报

千骨娜娜 发表于 2015-11-27 01:37:21 | 显示全部楼层
wjf1990 发表于 2015-11-26 11:35
对的   面试官提醒了我好多都没做出来  求代码  哪里有原题吗

木有原题。。再请问楼主下,求island的周长是怎么算的呢?
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-11-27 02:03:02 | 显示全部楼层
千骨娜娜 发表于 2015-11-27 01:37
木有原题。。再请问楼主下,求island的周长是怎么算的呢?

DFS啊  提到了对方就满意了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-27 02:14:23 来自手机 | 显示全部楼层
那个data steam的应该是bucket计数吧,请问楼主那个island周长的是怎么做的?
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-11-27 02:19:32 | 显示全部楼层
bobzhang2004 发表于 2015-11-27 02:14
那个data steam的应该是bucket计数吧,请问楼主那个island周长的是怎么做的?
. From 1point 3acres bbs
划完岛了以后DFS
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-11-27 05:14:07 | 显示全部楼层

楼主可以具体说一下吗?因为岛的形状可能出现多边形啊,这样的话不好算吧?
回复 支持 反对

使用道具 举报

jkingxt 发表于 2015-11-27 06:39:17 | 显示全部楼层
bobzhang2004 发表于 2015-11-27 05:14
楼主可以具体说一下吗?因为岛的形状可能出现多边形啊,这样的话不好算吧?

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

使用道具 举报

 楼主| wjf1990 发表于 2015-11-27 15:33:36 | 显示全部楼层
jkingxt 发表于 2015-11-27 06:39
我觉得是这样的。即使是多边形,计算周长的时候也是可以把他看成是矩形的,这个矩形就是这个多边形的最小 ...

duide   jiushizhwyang
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-1 13:02:41 | 显示全部楼层
写了下max island size,欢迎指教
  1. public class IslandMaximumSize {

  2.         public static void main(String[] args) {
  3.                 int[][] matrix =   {{0, 0, 1, 0},
  4.                                                         {0, 1, 0, 1},. 1point3acres.com/bbs
  5.                                                         {0, 1, 0, 1},
  6.                                                         {1, 0, 0, 0},};
  7.                 getIslandMaximumSize(matrix);
  8.         }
  9.         . from: 1point3acres.com/bbs
  10.         public static int getIslandMaximumSize(int[][] matrix) {
  11.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {-google 1point3acres
  12.                         return 0;
  13.                 }
  14.                 int res = 0;
  15.                 for (int i = 0; i < matrix.length; i++) {
  16.                         for (int j = 0; j < matrix[0].length; j++) {
  17.                                 if (matrix[i][j] == 1) {
  18.                                         res = Math.max(res, helper(matrix, i, j));
  19.                                 }. from: 1point3acres.com/bbs
  20.                         }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  21.                 }
  22.                
  23.                 System.out.println(res);
  24.                 return res;
  25.         }
  26.         private static int helper(int[][] matrix, int i, int j) {-google 1point3acres
  27.                 if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] != 1) {
  28.                         return 0;
  29.                 }
  30.                 matrix[i][j] = 2;
  31.                 int size = 1;
  32.                 int[] dx = {1, -1, 0, 0};
  33.                 int[] dy = {0, 0, 1, -1};. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  34.                 for (int k = 0; k < dx.length; k++) {
  35.                         int x = i + dx[k];
  36.                         int y = j + dy[k];
  37.                         size += helper(matrix, x, y);
  38.                 }
  39.                
  40.                 return size;. visit 1point3acres.com for more.
  41.         }
  42. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| wjf1990 发表于 2015-12-1 23:49:17 | 显示全部楼层
bobzhang2004 发表于 2015-12-1 13:04
写了下max island perimeter的代码,电面考这个代码量真多啊。楼主代码中得输出应该是12? 欢迎指教。
.1point3acres缃
应该是没错  我晚上回家看看
回复 支持 反对

使用道具 举报

reality 发表于 2015-12-2 00:34:02 | 显示全部楼层
第二题:merge 2 unsorted array(in-place) 请问这个怎么in place做呢 谢谢
回复 支持 反对

使用道具 举报

reality 发表于 2015-12-2 00:35:37 | 显示全部楼层
千骨娜娜 发表于 2015-11-26 10:20
data stream of integer 0-999, write add() and median() function。这题用bucket?

用1000个bucket记 ...

请问这个解法为什么是o(1)呢?

补充内容 (2015-12-2 00:42):
这个解法再扫一遍求median的时候运行时间难道不是o(n)吗?求指教。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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