一亩三分地论坛

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

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

Google MTV Onsite

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

2015(10-12月) 码农类 硕士 全职@Google - 猎头 - Onsite |Otherfresh grad应届毕业生

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

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

x
今天刚面完的,抱着一贯发面经保平安的原则就来发帖了。. from: 1point3acres.com/bbs
第一轮一个中国小哥,其实就是merge interval, 但是就是要自己从头开始设计一个类,实现是否overlap的方法,然后return一堆interval的overall coverage
比如(2, 4) (3, 5) coverage 就是 3 (2, 5)。其实就是merge后返回total len就可以了. 说了两种解法,不过还是得感谢小哥放水
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
第二是一个中国大哥,问了一个string的plus one,不过和leetcode不同的是,有可能是负数,所以如果负数的话就是minus one了。要haldle各种exception.而且第一次做负数Edge case也不好想。。本来是warmup quesion,结果浪费了好久时间,哎。。。第二题问了一道design,开始没怎么反应过来当成algorithm问题了,所以答得不好。就是 guess 一个 word, 比如 word 是 “heart", 然后player guess “board”, 会返回1,因为‘r' 猜对了。
然后设计一个方案,让尽可能快的猜对。答得很不好。。感觉小哥已经给了不少提示了,不过我还是没开窍,最后也不懂。。哎,怪自己。。
. from: 1point3acres.com/bbs
中午吃饭也是一个中国大哥,面了大半天了全是中国人,心中窃喜。。跟大哥就唠了唠家常,了解了下湾区定居后的生活是什么样的,大哥很热情。
. 鍥磋鎴戜滑@1point 3 acres

下午第三轮是个印度小哥,带了个白人shadow, 第一道给一个two D garden , 每一个slot可以是flower或者Wall. 找一个合适的位置,让游客可以看到最多的flower.可以站在flower上,不能站在墙上。。
如果被墙挡了,就看不到墙后面的花。然后游客只能竖直或者水瓶看,不能看对角线。。比如
[ [f, x, x, w, f],
  [f, f, x ,x ,x],
  [x, x, f, w, f],
  [f, f, x, w, x]]
这样,{3, 0} 和 {1,4}都能看到四朵花。
开始说了个brute force的方法,最后优化到o(n^2)分别水平还竖直的便利整个matrix, 记下这行的flower个数,碰到FLOWER就加一,然后每一行碰到墙了就把之前的全部更新, 然后 flower个数reset 到 0.
然后水平和竖直便利后的相加。最后找最大就可以了。。
第二题问了group a list of string, 比如 ’abbc' 和 ‘bccd'就是一组的。因为平移一位可以得到。楼主傻逼到开始说必须从分别平移量从1试到25才能确定是不是一组的。。最后写完算法忽然发现原来知道string每个字符间的diff就可以了。。感觉三哥哥本来要对我弃疗了。。最后时刻说了想法,小哥终于欣慰的点了点头。。智商真是捉急。。

第四轮一个看着不怎么开心的美国小哥, valid graph tree.跟LEETCODE不同的是,这个图是有向.
Node {
int id;.鐣欏璁哄潧-涓浜-涓夊垎鍦
Set<Node> childern;
}. 鍥磋鎴戜滑@1point 3 acres
public boolean isValid(List<Node> graph) {}. 1point 3acres 璁哄潧
开始用拓扑排序做完,发现不太对。。因为可能两个Parent有相同的Child,但是Tree中这样不合法。 最后改对了。。 然后问了问test case, 问了问优化。。最后临走前也觉得小哥不怎么开心。。.1point3acres缃
总体来说Google的面试体验还是不错的,时间安排的很合理。现在最大的concern是第二轮的design,希望大哥能放我一马。。不过楼主感觉运气已经很好了,碰到好多国人,题目也很简单,感觉跟前一阵猛看的面经比起来明显不是一个难度啊。。而且碰到的三哥哥也很NICE。
如果再过不了就完全是自身的问题了,谁都怪不了。。。
攒RP,求Offer...鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. Waral 鍗氬鏈夋洿澶氭枃绔,


补充内容 (2015-12-31 08:35):
补充一下,今天hr打电话说挂了,不知道为什么。。心情真是差。也只能move on了。。

评分

4

查看全部评分

本帖被以下淘专辑推荐:

 楼主| tianshaobo47 发表于 2015-12-16 11:38:20 | 显示全部楼层
xiaoniuona 发表于 2015-12-16 02:22
第三轮第一题不是很明白诶,如果统计每行每列的flower数的话,那行统计完的矩阵就是:
1 1 1 0 1
2 2 2 2 ...

忽然发现我写的有BUG,如果站在花上面,上下扫和左右扫会重复一次。。最后相加的时候应该判断下。。跪了。。
复杂度应该是O(m * n)
回复 支持 2 反对 0

使用道具 举报

bunnyNova 发表于 2015-12-15 18:25:15 | 显示全部楼层
谢谢LZ分享,第三轮第二题应该是LEETCODE Group Shifted Strings
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 02:04:42 | 显示全部楼层
bless~请问楼主最后一题不用拓扑排序的话你最后是改用什么做的哈?
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 02:22:30 | 显示全部楼层
第三轮第一题不是很明白诶,如果统计每行每列的flower数的话,那行统计完的矩阵就是:
1 1 1 0 1
2 2 2 2 2
1 1 1 0 1. 鍥磋鎴戜滑@1point 3 acres
2 2 2 0 0. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
列遍历完的矩阵是:
3 2 1 0 2
3 2 1 0 2.鏈枃鍘熷垱鑷1point3acres璁哄潧
3 2 1 0 2
3 2 1 0 2. more info on 1point3acres.com
然后两个矩阵相加得到(1,0)和(3,0)的和最大,所以就是那2个spot?

补充内容 (2015-12-16 08:44):. more info on 1point3acres.com
这样的时间是O(m+n)嚒?
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-12-16 07:13:55 | 显示全部楼层
bunnyNova 发表于 2015-12-15 18:25
谢谢LZ分享,第三轮第二题应该是LEETCODE Group Shifted Strings

还真是。。简单题好久没做了。。好可惜。。
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-12-16 10:33:10 | 显示全部楼层
请问lz merge interval的两种方法都是什么,祝lz好运
回复 支持 反对

使用道具 举报

xiaoniuona 发表于 2015-12-16 12:30:39 | 显示全部楼层
楼主最后一题是怎么判断2个parent有木有相同child的呢?
回复 支持 反对

使用道具 举报

 楼主| tianshaobo47 发表于 2015-12-18 08:42:15 | 显示全部楼层
xiaoniuona 发表于 2015-12-16 12:30
楼主最后一题是怎么判断2个parent有木有相同child的呢?

每个node的入度不能超过1就好了啊
回复 支持 反对

使用道具 举报

silenceleaf 发表于 2015-12-30 07:55:33 | 显示全部楼层
楼主请问第二轮 design题目,返回值是自己设计吗?我不太明白返回1是什么意思。
回复 支持 反对

使用道具 举报

lzyfriday 发表于 2015-12-31 08:24:57 | 显示全部楼层
lz最近有消息吗
回复 支持 反对

使用道具 举报

ivana 发表于 2016-1-4 05:57:14 | 显示全部楼层
第二题第二问知不知道word的长度呢,如果知道的话,可不可以这么做呀,. Waral 鍗氬鏈夋洿澶氭枃绔,

第一步, 先确定word包含的字母。遍历长度为n的a-z序列,比如:长度为5的话,aaaaa, bbbbb, ..., zzzzz. 每次返回的值即为该字母在word中出现的次数。这样就得到了word里面包含的字母及对应数量,遍历中若得到了n个值即可终止跳出循环。

第二步,有了字母和数量之后确定相对顺序。可以对每一个已知的字母,遍历每一个可能的位置,其余位置用不存在的字母填充。比如从第一步中已知包含:a-1, b-1, c-2, 那么为了确定a的位置,可以尝试azzzz, zazzz, zzazz, zzzaz, zzzza。返回1的那个序列对应的a的位置即是正确位置。依次列推得到其余的位置。

这样的话时间复杂度应该是O(26*n*n)=O(n^2)了,感觉有点慢,不知道有没有更好的方法呢。
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-27 11:07:56 | 显示全部楼层
写了下flower的代码
  1. public class FlowersInGarden {
    . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

  2.         public static void main(String[] args) {
  3.                 char[][] matrix = {{'f', 'x', 'x', 'w', 'f'},
  4.                                      {'f', 'f', 'x' ,'x' ,'x'},
  5.                                      {'x', 'x', 'f', 'w', 'f'},
  6.                                      {'f', 'f', 'x', 'w', 'x'}};
  7.                 maxFlowersInGarden(matrix);
  8.         }
  9.        
  10.         public static int maxFlowersInGarden(char[][] matrix) {
  11.                 if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
  12.                         return 0;
  13.                 }. 1point 3acres 璁哄潧
  14.                 int m = matrix.length;
  15.                 int n = matrix[0].length;.1point3acres缃
  16.                 . From 1point 3acres bbs
  17.                 int[][] res = new int[m][n];
    . 1point 3acres 璁哄潧
  18.                 for (int i = 0; i < m; i++) {
  19.                         int count = 0;
  20.                         int j = 0;
  21.                         int start = 0;. more info on 1point3acres.com
  22.                         while (j < n) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  23.                                 if (matrix[i][j] == 'f') {
  24.                                         count++;
  25.                                 } else if (matrix[i][j] == 'w') {
  26.                                         for (int k = start; k < j; k++) {
  27.                                                 res[i][k] = count;. 1point 3acres 璁哄潧
  28.                                         }
  29.                                         start = j + 1;
  30.                                         count = 0;
  31.                                 }
  32.                                 j++;
  33.                         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  34.                         for (int k = start; k < j; k++) {
  35.                                 res[i][k] = count;
  36.                         }
  37.                 }
  38.                 for (int j = 0; j < n; j++) {
  39.                         int count = 0;
  40.                         int i = 0;
  41.                         int start = 0;
  42.                         while (i < m) {
  43.                                 if (matrix[i][j] == 'f') {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.                                         count++;
  45.                                 } else if (matrix[i][j] == 'w') {
  46.                                         for (int k = start; k < i; k++) {. 1point3acres.com/bbs
  47.                                                 res[k][j] += count;. more info on 1point3acres.com
  48.                                         }
  49.                                         start = i + 1;-google 1point3acres
  50.                                         count = 0;
  51.                                 }
  52.                                 i++;
  53.                         }
  54.                         for (int k = start; k < i; k++) {
  55.                                 res[k][j] += count;
  56.                         }. more info on 1point3acres.com
  57.                 }
  58.                 for (int i = 0; i < m; i++) {
  59.                         for (int j = 0; j < n; j++) {
  60.                                 if (matrix[i][j] == 'f') {
  61.                                         res[i][j] -= 1;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  62.                                 }
  63.                         }
  64.                 }
  65.                 int max = 0;
  66.                 for (int i = 0; i < m; i++) {
  67.                         for (int j = 0; j < n; j++) {
  68.                                 System.out.print(res[i][j] + " ");
  69.                                 max = Math.max(max, res[i][j]);
  70.                         }
  71.                         System.out.println();. 1point3acres.com/bbs
  72.                 }
  73.                
  74.                
  75.                 return max;
  76.         }
  77. }
复制代码
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-1-27 11:45:04 | 显示全部楼层
请问楼主plus one一定是-1, 1吗?会出现-133, 133等的情况吗?
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-6-23 13:29:12 | 显示全部楼层
{3, 0} 和 {1,4}都能看到四朵花。
应该是{2,0}, {1,4} 都能看到三朵花吧?
回复 支持 反对

使用道具 举报

asdasdliu 发表于 2016-10-8 00:16:26 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

asdasdliu 发表于 2016-10-8 00:17:05 | 显示全部楼层
谢谢楼主分享
回复 支持 反对

使用道具 举报

qiuxuxing007 发表于 2016-10-27 08:19:38 | 显示全部楼层
第四轮 思路用bfs level order traversal 来做 对不?
回复 支持 反对

使用道具 举报

kevindx1120 发表于 2016-11-27 07:01:26 | 显示全部楼层
请问楼主, 第二轮第二题 
比如 word 是 “heart", 然后player guess “board”, 会返回1,因为‘r' 猜对了
 意思是说,只要某一对应位的字母猜对了就是猜对了,是吗?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 20:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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