一亩三分地论坛

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

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

Google 2/25 onsite面经

[复制链接] |试试Instant~ |关注本帖
panlong222 发表于 2016-2-26 08:55:23 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Google - 内推 - Onsite |Otherfresh grad应届毕业生

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

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

x
刚从google回酒店,就把面经写了吧。也许因为不是第一次挂面试了,所以这次比较淡定?


1. 三哥,口音没有那么那么重,勉强听得懂。这轮感觉面的最好。
    给一个List<Iterator>,写一个method next(),每次调用这个method,输出所有iterator里的最小值。. visit 1point3acres.com for more.
    本质就是merge k sorted list。用heap。
.1point3acres缃
2. 老美,从头到尾冷面。只有最后聊他的经历的时候很开心,眉飞色舞。感觉这轮的follow up 有点难。第3)问基本就是他一步一个hint我才答出来的。
    1) encode string: 例如 abbbbbc  -> a5xbc.  我大概花了15分钟写代码。搞定 bugfree。. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷    2) 如果有个string already in an encoded form, we want to decode it.  Find a type of strings that may cause problem when decoding.
         abbbbbc ->(encode) a5xbc -> (decode) abbbbbc, this one is OK
         a5xbc ->(encode)  a5xbc -> (decode) abbbbbc , this one has problem.   
         实际就是 如果原始string里包含“数字 + x + 任意字符”这种格式的就会有问题。
    3) how to modify the way of encoding/decoding to prevent the problem from happening?
         提示:  数字 + x + 任意字符  -> 1x数字1xx
        a5xbc ->(encode) a1x51xxbc -> (decode) a5xbc.鏈枃鍘熷垱鑷1point3acres璁哄潧

       其实第三问我到现在都没搞清楚。请不要问楼主太多关于第三问。。。. from: 1point3acres.com/bbs

3.   美国老头儿,目测至少55岁了,说话声音有点模糊,嗓门略小。 纯OODesgin题!!!纯!纯!纯!重要的事情说三遍!.鐣欏璁哄潧-涓浜-涓夊垎鍦
      楼主这轮被秒成了渣。。。.鐣欏璁哄潧-涓浜-涓夊垎鍦

     给了楼主两个class,互相之间有一定联系。(Ad.java, Account.java,具体的内容楼主不想描述了,不要问楼主,楼主不知道这轮面的啥。让我设计一个elevator都比容易的多啊)。
     让楼主把这两个类读一遍之后,说哪里设计可以优化一下。。。楼主当时的心情是 “我选择死亡”。。。
     于是不停的问hint,因为根本不知道说啥。。。
     老爷子指着一片代码说这里是不是可以有更好的设计,我就跟着想一想,说一说。 . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
     然后再求等他给提示。。。T_T T_T T_T T_T 楼主现在很后悔 在简历上写了对OOD有兴趣,可仅仅是有兴趣而已啊,根本没有experience,也没有系统钻研过- -果断作死了 :(
. from: 1point3acres.com/bbs
4.  白人,但口音听不清。这轮楼主自我感觉也还不错。
     1) 判断一个square matrix是否对称。 (即旋转180度之后是否没变) 10分钟写完代。
     2) 给一个matrix, 每个cell要么0要么1, 判断所有的0是否connected。
            说思路即可,没要写代码。 随便挑一个0,然后对它做dfs,然后遍历matrix,看有没有0没有被visit到。. 鍥磋鎴戜滑@1point 3 acres
     3 )  如果matrix 是堆成的square matrix, 如何优化第2问?
            楼主的回答 : 对matrix拦腰砍一刀,取matrix的上一半,运行2)的algorithm, 然后看cutting edge是否有0连通。
     4) 给定一个matrix起初全是1, 每次把任意一个1变成0.
            每把一个1变一个0, 问这时候所有的0是否connected。. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
           楼主的思路:
           核心思路:对每个由0组成的island编个island号。用一个set存所有的island的编号。
           每次把某个1变成0, 对这个0做DFS。如果这个0上下左右都是1, 那么它自己就是一个新的island,赋予一个新的island号码。如果周围已经有0,那么当它第一次遇到一个0的时候,就把自己的island号码变成那个0的island号码。以后dfs过程中遇到的所有的0,都把其island号变成这个island号码,如果其island号码和这个island号码不一样,将其island号码从set移除。 如果DFS结束之后,set里island的号只有一个,那么return true, otherwise false。
           自我感觉这个算法没问题,面试官觉得我大概是对的,只不过我的思路和他的不一样。时间快到了,他把我的算法思路的草稿拍了照就结束了。

楼主5月毕业,到今天为止面试全挂完了,没有面试了。不知道后面怎么办。(已投了30+家公司了。)
. From 1point 3acres bbs
就这样吧,感觉过的可能性不大,自己的简历作死。谢谢大家,欢迎提问。(不过请尽量不要问楼主第三轮,人生已经如此艰难,有些事情你又何必拆穿?)
.鏈枃鍘熷垱鑷1point3acres璁哄潧
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴


补充内容 (2016-2-26 08:57):
“堆成的square matrix” , 实际是 “对称的square matrix”。 Typo,见谅~

补充内容 (2016-3-10 07:14):
3/7 进hc
3/9 挂了

评分

3

查看全部评分

bobzhang2004 发表于 2016-3-4 06:09:34 | 显示全部楼层
写了下第二轮的代码
  1. public class StringEncodeAndDecode {
  2.        
  3.         public static void main(String[] args) {
  4.                 System.out.println(encodeForQ1("abbbbbbbbbbbbbc"));
  5.                 String enStr = encodeFollowUp("a5xbc");
  6.                 System.out.println(enStr);. visit 1point3acres.com for more.
  7.                 System.out.println(decodeFollowUp(enStr));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  8.         }
  9.        
  10.         public static String encodeForQ1(String str) {
  11.                 if (str == null || str.length() == 0) {
    . 1point 3acres 璁哄潧
  12.                         return "";
  13.                 }
  14.                 int i = 0;
  15.                 StringBuilder sb = new StringBuilder();
  16.                 while (i < str.length()) {
  17.                         int j = i + 1;
  18.                         while (j < str.length() && str.charAt(j) == str.charAt(i)) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  19.                                 j++;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  20.                         }
  21.                         int diff = j - i;
  22.                         String s = String.valueOf(diff) + "x"+ str.charAt(i);
  23.                         if (s.length() < diff) {. From 1point 3acres bbs
  24.                                 sb.append(s);
  25.                         } else {
  26.                                 sb.append(str.substring(i, j));
  27.                         }
  28.                         i = j;
  29.                 }
  30.                 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  31.                 return sb.toString();
  32.         }
  33.        
  34.         public static String encodeFollowUp(String str) {
  35.                 if (str == null || str.length() == 0) {
  36.                         return "";.1point3acres缃
  37.                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  38.                 int i = 0;
  39.                
  40.                 StringBuilder sb = new StringBuilder();
  41.                 while (i < str.length()) {
  42.                         char curChar = str.charAt(i);
  43.                         int j = i + 1;
  44.                         while (j < str.length() && str.charAt(j) == curChar) {
  45.                                 j++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  46.                         }
  47.                         int diff = j - i;
  48.                         String s = String.valueOf(diff) + "x"+ curChar;
  49.                         if (s.length() < diff || curChar == 'x' || Character.isDigit(curChar)) {. From 1point 3acres bbs
  50.                                 sb.append(s);
  51.                         } else {
  52.                                 sb.append(str.substring(i, j));.鐣欏璁哄潧-涓浜-涓夊垎鍦
  53.                         }
  54.                         i = j;
  55.                 }
  56.                
  57.                 return sb.toString();
  58.         }
  59.        
  60.         // a1x51xxbc
  61.         public static String decodeFollowUp(String str) {
  62.                 if (str == null || str.length() == 0) {
  63.                         return "";
  64.                 }
  65.                 int i = 0;
  66.                 StringBuilder sb = new StringBuilder();
  67.                 while (i < str.length()) {
  68.                         int index = str.indexOf('x', i);
  69.                         if (index == -1) {
  70.                                 sb.append(str.substring(i));. From 1point 3acres bbs
  71.                                 break;. 1point 3acres 璁哄潧
  72.                         } else {
  73.                                 int j = index - 1;
  74.                                 while (j >= i && Character.isDigit(str.charAt(j))) {
  75.                                         j--;. 1point3acres.com/bbs
  76.                                 }
  77.                                 if (j >= i) {. more info on 1point3acres.com
  78.                                         sb.append(str.substring(i, j + 1));
  79.                                 }
  80.                                 int count = Integer.valueOf(str.substring(j + 1, index));
  81.                                 for (int k = 0; k < count; k++) {
  82.                                         sb.append(str.charAt(index + 1));
  83.                                 }
  84.                                 i = index + 2;
  85.                         }
  86.                 }
  87.                 .1point3acres缃
  88.                 return sb.toString();
  89.         }
  90.        
  91. }
复制代码
回复 支持 1 反对 0

使用道具 举报

superbeet 发表于 2016-4-15 02:15:39 | 显示全部楼层
判断一个square matrix是否对称。 这应该是个warm up题。其实不需要旋转矩阵,横纵坐标交换比较一下即可,10行内搞定。
回复 支持 1 反对 0

使用道具 举报

duduhaha 发表于 2016-2-26 14:20:50 | 显示全部楼层
楼主的的encode那题需要始终对x 和数字编码。例如:
aa51x -> aa1x51x11xx
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
为了保证编码长度最短,当一个字符重复次数小于3时,不要编码,aa不用变成2xa

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

yayayouknow 发表于 2016-2-26 09:50:12 | 显示全部楼层
所以说补充的“对称”是指旋转180度对称?
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-2-26 09:52:18 | 显示全部楼层
yayayouknow 发表于 2016-2-26 09:50
所以说补充的“对称”是指旋转180度对称?

yes                                          
回复 支持 反对

使用道具 举报

yayayouknow 发表于 2016-2-26 09:54:45 | 显示全部楼层

哦,thanks~~祝楼主好运~
回复 支持 反对

使用道具 举报

kinggarden2001 发表于 2016-2-26 11:29:44 | 显示全部楼层
encoding第三个follow up就是像你说的那样啊
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-2-26 14:28:42 | 显示全部楼层
duduhaha 发表于 2016-2-26 14:20
楼主的的encode那题需要始终对x 和数字编码。例如:
aa51x -> aa1x51x11xx

厉害,大神受我一拜....
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-2-26 14:33:03 | 显示全部楼层
panlong222 发表于 2016-2-26 14:28
厉害,大神受我一拜....

哪里。。这题我也是因为见过,第一次见很难搞明白。。
回复 支持 反对

使用道具 举报

lefttree 发表于 2016-2-26 16:05:42 | 显示全部楼层
其实lz答的挺好的,祝好运!
回复 支持 反对

使用道具 举报

lotustree86 发表于 2016-2-26 17:44:23 | 显示全部楼层
最后一题Union find比较好吧
回复 支持 反对

使用道具 举报

malc 发表于 2016-2-26 22:31:40 | 显示全部楼层
哎 我投了十几二十个才拿到一个面试而且还挂了。。。祝好
回复 支持 反对

使用道具 举报

lookbackinanger 发表于 2016-2-26 23:01:04 | 显示全部楼层
那个0,1的是不是直接上Union Find更好一些?
回复 支持 反对

使用道具 举报

学渣找工作 发表于 2016-2-27 01:05:30 | 显示全部楼层
多谢LZ!
今天面,一大早醒了上来看看没想到有这么新鲜的面筋。
祝LZ好运!
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-2-27 01:27:11 | 显示全部楼层
lookbackinanger 发表于 2016-2-26 23:01
那个0,1的是不是直接上Union Find更好一些?

楼主浅陋,刚百度了下Union Find,长知识了,谢谢各位。
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-2-27 01:29:37 | 显示全部楼层
学渣找工作 发表于 2016-2-27 01:05
多谢LZ!
今天面,一大早醒了上来看看没想到有这么新鲜的面筋。
祝LZ好运!

Good luck!
回复 支持 反对

使用道具 举报

ninacc 发表于 2016-2-27 18:01:52 | 显示全部楼层
和楼主同一天面的!!!祝我们都好运!
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-2-28 01:38:34 | 显示全部楼层
除第三面以外都是原题啊,第四题就是count island2的简单变形,如果是count大于1就是没有链接,否则是链接的
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-2-28 01:50:50 | 显示全部楼层
bobzhang2004 发表于 2016-2-28 01:38-google 1point3acres
除第三面以外都是原题啊,第四题就是count island2的简单变形,如果是count大于1就是没有链接,否则是链接 ...

恩 我也觉得第四题在哪见过
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
另外 请问第二题的两个follow up , leetcode里有吗?
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2016-3-4 04:50:56 | 显示全部楼层
panlong222 发表于 2016-2-28 01:50. 1point3acres.com/bbs
恩 我也觉得第四题在哪见过
. 1point3acres.com/bbs
另外 请问第二题的两个follow up , leetcode里有吗?

没有,是常考面经题,祝好运
回复 支持 反对

使用道具 举报

 楼主| panlong222 发表于 2016-3-4 05:48:56 | 显示全部楼层
bobzhang2004 发表于 2016-3-4 04:50
没有,是常考面经题,祝好运
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
多谢 !                                          
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 18:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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