一亩三分地论坛

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

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

gg面经

[复制链接] |试试Instant~ |关注本帖
EmilyMMMM 发表于 2016-2-12 14:11:51 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 实习@Google - 内推 - 技术电面 |Pass其他

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

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

x
今天收到了gg的结果,过了,接下来等host match,虽然不是很抱希望。写一下面经攒攒人品。

楼主是2.8号面的,back to back,一轮中国小哥一轮美国小哥。

第一轮:
maximum subarray的变种,把一维数组变成二维矩阵,求矩阵中和最大的子矩阵,然后返回最大的和就可以了。

第二轮:
莫尔斯电码encode和decode. more info on 1point3acres.com
. more info on 1point3acres.com
第二轮没什么好说的,面经题。说说第一轮吧,楼主本来是抱着必挂的心态面的gg,所以面试的时候就抱着体验生活的态度去的,初看这道题直觉应该是dp,但是具体怎么做还是不是很有思路,开始只给了一个暴力解。但是面试官真的是太好了!然后我们俩就一直在讨论这道题应该怎么做。我实在是没啥思路就问他可不可以给我一点提示,他说你可以试试想一想可不可以把二维问题转化成一维问题来做,一维问题你会吗,我想这个简单,lc原题嘛,然后很快给出了方法。小哥说对了,然后就给出了压缩行+two pointers+一维dp的解法,基本写完就到时间了,小哥真的是太好了,说你不用问我问题了,好好准备下一轮吧~因为楼主本身就抱着一种跟同学讨论题目的心态再加上小哥本身超nice超有耐心,这一轮气氛特别棒~

所以楼主觉得面试的时候没有给出最好的办法也不一定不会过,最少要有一种“这道题我不会做但是我会学”的态度吧,毕竟面试是个互动交流的过程,要让面试官看到你解决问题的过程也是很重要的。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

求match!求offer!
求match!求offer!. visit 1point3acres.com for more.
求match!求offer!. 1point 3acres 璁哄潧




补充内容 (2016-2-19 07:52):
第二轮的题的补充在16楼

评分

5

查看全部评分

bobzhang2004 发表于 2016-3-5 03:44:26 | 显示全部楼层
第一轮
  1. public class MaximumSumRectangleInA2DMatrix {
  2.         public static void main(String[] args) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  3.                 int[][] M = { { 1, 2, -1, -4, -20 }, { -8, -3, 4, 2, 1 },
  4.                                 { 3, 8, 10, 1, 3 }, { -4, -1, 1, 0, -6 } };

  5.                 int res = findMaxSum(M);
  6.                 System.out.println(res);. 1point3acres.com/bbs
  7.         }

  8.         static int helper(int[] arr) {
  9.                 // initialize sum, maxSum and. From 1point 3acres bbs
  10.                 int sum = 0, maxSum = Integer.MIN_VALUE;
  11.                 int n = arr.length; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  12.                 // Just some initial value to check for all negative values case
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  13.                 // local variable
  14.                 for (int i = 0; i < n; ++i) {-google 1point3acres
  15.                         sum += arr[i];
  16.                         if (sum < 0) {
  17.                                 sum = 0;
  18.                         } else if (sum > maxSum) {
  19.                                 maxSum = sum;. visit 1point3acres.com for more.
  20.                         }. from: 1point3acres.com/bbs
  21.                 }

  22.                 return maxSum;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.         }

  24.         static int findMaxSum(int M[][]) {
  25.                 // Variables to store the final output
  26.                 int COL = M[0].length;
  27.                 int maxSum = Integer.MIN_VALUE;
  28.                 int ROW = M.length;-google 1point3acres
  29.                 int[] temp = new int[COL];
  30.                 int sum = 0;

  31.                 for (int i = 0; i < ROW; i++) {
  32.                         Arrays.fill(temp, 0);
  33.                         for (int j = i; j < ROW; j++) {
    .鐣欏璁哄潧-涓浜-涓夊垎鍦
  34.                                 for (int k = 0; k < COL; k++) {
  35.                                         temp[k] += M[j][k];
  36.                                 }
  37.                                 sum = helper(temp);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38.                                 if (sum > maxSum) {
  39.                                         maxSum = sum;
  40.                                 }
  41.                         }
  42.                 }

  43.                 return maxSum;. visit 1point3acres.com for more.
  44.         }
  45. }
复制代码
回复 支持 1 反对 0

使用道具 举报

garnett2148 发表于 2016-2-17 14:45:44 | 显示全部楼层
EmilyMMMM 发表于 2016-2-13 04:37
增加space complexity,用一个n*n的矩阵保存和

按照楼主说的按一维 DP 保存的话是不是可以这样, 遍历矩阵,然后在每一行的时候都用DP保存每一列累加的值,
[[-1,2,-3,1], ==> DP = [-1,2,-3,1]
[2,1,-1,3],  ==> DP = [1,3,-4,4]
[1,-2,4,-1], ==> DP = [2,1,0,3]
[1,1,1,1]]   ==> DP = [3,2,1,4]
然后在每一行遍历完, 在用一个size等于行数的 window 来遍历DP数组, 比如第三行就用window size = 3来找,意思3*3的最大和在DP[1..3] = [1,0,3]找到. 如上例最大和为4*4的矩阵,和为10.鏈枃鍘熷垱鑷1point3acres璁哄潧

大家看看这解法有问题么?
   
回复 支持 1 反对 0

使用道具 举报

kinggarden2001 发表于 2016-2-12 14:43:37 | 显示全部楼层
请问第一题压缩行的时候是不是要把上面所有行都要试一下? 复杂度是 m*m*n
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-13 02:43:28 | 显示全部楼层
kinggarden2001 发表于 2016-2-12 14:43. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
请问第一题压缩行的时候是不是要把上面所有行都要试一下? 复杂度是 m*m*n

对的,matrix是个正方形,只用边长n就可以

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

phph17 发表于 2016-2-13 03:10:57 | 显示全部楼层
请问下楼主,第二轮的面经题是哪两道
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-2-13 03:11:59 | 显示全部楼层
EmilyMMMM 发表于 2016-2-13 02:43
对的,matrix是个正方形,只用边长n就可以

没有很懂第一题的解法....是把二维转换成一维做吗?我怎么感觉光枚举所有子矩阵就要n^4,请问楼主如何n^3做出来的?
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-13 03:33:42 | 显示全部楼层
phph17 发表于 2016-2-13 03:10
请问下楼主,第二轮的面经题是哪两道

我写了呀,摩尔斯电码
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-13 04:37:53 | 显示全部楼层
johnjavabean 发表于 2016-2-13 03:11
没有很懂第一题的解法....是把二维转换成一维做吗?我怎么感觉光枚举所有子矩阵就要n^4,请问楼主如何n^3 ...

增加space complexity,用一个n*n的矩阵保存和
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-17 23:17:34 | 显示全部楼层
garnett2148 发表于 2016-2-17 14:45
按照楼主说的按一维 DP 保存的话是不是可以这样, 遍历矩阵,然后在每一行的时候都用DP保存每一列累加的值 ...

嗯对的就是这样,我最后就写到这个n^3的方法,然后优化一下一维的DP,就结束了
回复 支持 反对

使用道具 举报

guixi107 发表于 2016-2-18 04:05:22 | 显示全部楼层
EmilyMMMM 发表于 2016-2-13 02:43
对的,matrix是个正方形,只用边长n就可以
. Waral 鍗氬鏈夋洿澶氭枃绔,
double check一下楼主 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

子矩阵的长和宽是一样的吗?
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-18 04:06:52 | 显示全部楼层
guixi107 发表于 2016-2-18 04:05
double check一下楼主. From 1point 3acres bbs

子矩阵的长和宽是一样的吗?

这是我问他的,面试官跟我说可以当做square就是长宽一样,我觉得如果他没说明还是当做m*n比较好
回复 支持 反对

使用道具 举报

phph17 发表于 2016-2-19 05:11:37 | 显示全部楼层
楼主有消息了吗
回复 支持 反对

使用道具 举报

Ulu2005 发表于 2016-2-19 06:13:51 | 显示全部楼层
第一题的详细解法可以看这里: http://www.geeksforgeeks.org/dyn ... gle-in-a-2d-matrix/
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-19 06:17:27 | 显示全部楼层
phph17 发表于 2016-2-19 05:11
楼主有消息了吗

host match没有呢,只有hr打过一个电话,例行公事的那种。。估计悬了
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-19 07:41:34 | 显示全部楼层
楼主可以详细说说第二题吗?我看面经里面很多做这题都出错了
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-19 07:52:22 | 显示全部楼层
bobzhang2004 发表于 2016-2-19 07:41. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
楼主可以详细说说第二题吗?我看面经里面很多做这题都出错了

我觉得这道题的要求可能不一样。
.1point3acres缃
我当时面的时候encode要求不加空格,比如说SOS就是...---...

decode比较麻烦,要求输出所有可能的形式,而且在输出的所有可能中,只保留有意义的序列。比如说两个解码,一个是AABB,一个是WORD(举例子),那么只保留WORD,AABB不保留。

我是用了两步backtracking做的,第一步先解码,第二步检查是否是有意义的词。dictionary是给出的。
. more info on 1point3acres.com

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 07:55:43 | 显示全部楼层
lz match有信吗?match两周多了没消息。。
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-19 07:56:25 | 显示全部楼层
iwofr 发表于 2016-2-19 07:55
lz match有信吗?match两周多了没消息。。

并没有,我基本已经放弃了。。。
回复 支持 反对

使用道具 举报

iwofr 发表于 2016-2-19 08:42:04 | 显示全部楼层
EmilyMMMM 发表于 2016-2-19 07:56
并没有,我基本已经放弃了。。。

可惜还没有别的offer。。。
回复 支持 反对

使用道具 举报

 楼主| EmilyMMMM 发表于 2016-2-19 09:23:38 | 显示全部楼层
iwofr 发表于 2016-2-19 08:42. 鍥磋鎴戜滑@1point 3 acres
可惜还没有别的offer。。。

加油加油!坑应该还是有的,我问hr她说会帮忙找6个周。。不知道是不是安慰我
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 16:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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