一亩三分地论坛

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

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

谷歌 Onsite 面筋

[复制链接] |试试Instant~ |关注本帖
richardwxn 发表于 2016-11-4 07:39:15 | 显示全部楼层 |阅读模式

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

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

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

x
刚在MTV面完的onsite,发个面经攒攒rp,顺带求点积分。。为什么我一个国人大哥大姐都遇不到,加上lunch三个三哥lol。。
第一轮,感觉像东欧大叔。第一题plus one,不用写,说思路。第二题,shortest palindrome, 以前在leetcode见过,但没做过,写了个recursive的做法,面试官说ok。但后来看了下leetcode discussion才知道有kmp的做法。

第二轮,印度三哥,超级凶,一来直接做题,招呼都不打。然后题目是lc394,秒了,然后其中一直在质疑我,然后我就告诉它是ok的。。follow up跪了,问我怎么找到最短的encode的方法,没想到,在他提示下想了个greedy的做法,没写代码,然后问时间复杂度,感觉答错了。。然后一直态度非常不好,感觉可能跪在这一轮了。

午饭google play组三哥。。今天三个三哥,醉了。。

第三轮白人小哥,lc302, 说了dfs和binary search两种解法,要求implement binary search那个。。但原来没写过binary search那个,所以一开始撸得有点bug,后来改了,但感觉还是有小bug,请面试官评价。。但是白人小哥一直不评价,从头到尾没说几句话,只是在奸笑,让我感觉有点虚。follow up矩阵非常大咋办。。

第四轮又是三哥,醉了,但这个三哥比较nice。。题目是第一道,three sum的变形,不难,秒了。第二LC308, 一开始说了prefix sum的方法。。然后就说了binary indexed tree的做法,本来准备开始写了。。然后三哥说不用这么复杂的数据结构,你知道就好了。。然后就implement第一种方法,搞定了。。然后聊得还可以。比第二轮三哥好太多。

总的来说这次rp其实还好,虽然有三道hard,但都是原题。其他medium也是原题。有个经验教训就是一定要动手写,我之前很多hard题都懒得写,看了下思路就跳过了,但是真正写的时候还是有问题的。所以还是得动手!

啊啊啊希望能过啊,不想再刷题了,希望三哥手下留情不要黑我,求rp啊啊啊啊


补充内容 (2016-11-7 05:17):. 鍥磋鎴戜滑@1point 3 acres
因为同一个string有好多种encode方法所以要求找到包括【】符号的最短的长度。。我的想法就是每一步都尽量使encode覆盖更长。长度一样的话考虑使repeat的部分更短次数更多。。但感觉不一定能保证找到最优解

评分

1

查看全部评分

本帖被以下淘专辑推荐:

zyoppy008 发表于 2016-11-4 09:35:51 | 显示全部楼层
全是原题 你这人品 简直爆表啊
回复 支持 反对

使用道具 举报

 楼主| richardwxn 发表于 2016-11-4 09:50:49 | 显示全部楼层
zyoppy008 发表于 2016-11-4 09:35
全是原题 你这人品 简直爆表啊

是啊觉得rp挺好的。。只是自己好多hard题都只想了思路没动手写过。。所以还是担心写出来有问题。。
回复 支持 反对

使用道具 举报

alyssum14 发表于 2016-11-4 10:07:21 | 显示全部楼层
楼主不要担心,即使第二轮被黑其他的几轮不错,就还是有很大胜算的,下周一就要面了,沾沾运气求原题~
回复 支持 反对

使用道具 举报

 楼主| richardwxn 发表于 2016-11-4 10:11:07 | 显示全部楼层
alyssum14 发表于 2016-11-4 10:07
楼主不要担心,即使第二轮被黑其他的几轮不错,就还是有很大胜算的,下周一就要面了,沾沾运气求原题~

嗯嗯希望如此把。。你加油加油!
回复 支持 反对

使用道具 举报

zhan1612 发表于 2016-11-4 10:38:22 | 显示全部楼层
楼主RP爆表了。。 顺便问下楼主encode的思路以及第三轮矩阵非常大的时候怎么搞的
回复 支持 反对

使用道具 举报

oily 发表于 2016-11-4 10:45:51 | 显示全部楼层
第二轮里面最短的decode方法是啥概念啊
回复 支持 反对

使用道具 举报

slarkzz 发表于 2016-11-4 10:50:09 | 显示全部楼层
这人品简直碉堡了
回复 支持 反对

使用道具 举报

pawprinter 发表于 2016-11-5 00:36:06 | 显示全部楼层
求问第二题的encode思路
回复 支持 反对

使用道具 举报

warriorbrant 发表于 2016-11-5 04:28:31 | 显示全部楼层
同问encode的方法
回复 支持 反对

使用道具 举报

 楼主| richardwxn 发表于 2016-11-7 05:17:59 | 显示全部楼层
oily 发表于 2016-11-4 10:45
第二轮里面最短的decode方法是啥概念啊
. from: 1point3acres.com/bbs
请看补充部分呗。。
回复 支持 反对

使用道具 举报

 楼主| richardwxn 发表于 2016-11-7 05:19:09 | 显示全部楼层
pawprinter 发表于 2016-11-5 00:36
求问第二题的encode思路

请看补充部分。。不过这只是我当时想的。感觉不太对。。
回复 支持 反对

使用道具 举报

zneofrost 发表于 2016-11-15 08:51:32 | 显示全部楼层
问一下第三轮矩阵非常大的情况楼主如何回答的
回复 支持 反对

使用道具 举报

gabrielzhuyun 发表于 2016-11-16 23:12:49 | 显示全部楼层
请问楼主第二轮follow up 的时间复杂度是多少啊
回复 支持 反对

使用道具 举报

Frankluo 发表于 2016-11-25 18:25:27 | 显示全部楼层

可以先看这篇帖子了解DP的思路
http://115.28.164.3/blogs/45

然后下面这段代码就能懂了。
shortest encoded string,代码来自一篇地里我找不回来的帖子,不能give credit给大神了
  1. public static boolean checkRepeating(String s, int l, int r, int start, int end){
  2.     if( (end-start) % (r-l) != 0 ){
  3.     return false;
  4.     }
  5.     int len = r-l;
  6.     String pattern = s.substring(l, r);
  7.     for(int i = start; i +len <= end; i+=len){. 鍥磋鎴戜滑@1point 3 acres
  8.         if(!pattern.equals(s.substring(i, i+len))){
复制代码
回复 支持 反对

使用道具 举报

Frankluo 发表于 2016-11-25 18:26:13 | 显示全部楼层

  1. class Solution{
  2.         public static boolean checkRepeating(String s, int l, int r, int start, int end){
  3.                 if( (end-start) % (r-l) != 0 ){
  4.                         return false;
  5.                 }
  6.                 int len = r-l;
  7.                 String pattern = s.substring(l, r);
  8.                 for(int i = start; i +len <= end; i+=len){
  9.                         if(!pattern.equals(s.substring(i, i+len))){
  10.                                 return false;. 1point 3acres 璁哄潧
  11.                         }
  12.                 }
  13.                 return true;
  14.         }

  15.         public static int getLength(int plen, int slen){
  16.                 return (int)(Math.log10(slen/plen)+1);
  17.         }

  18.         public static String shortestEncodeString(String s){
  19.                 int len = s.length();
  20.                 int[][] dp = new int[len+1][len+1];
  21.                 for(int i = 1; i <= len; ++i){
  22.                         for(int j = 0; j < i; ++j){
  23.                                 dp[j][i] = i-j;
  24.                         }
  25.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,

  26.                 Map<String, String> dpMap = new HashMap<>();

  27.                 for(int i = 1; i <= len; ++i){
  28.                         for(int j = i-1; j >= 0; --j){
  29.                                 String temp = s.substring(j, i);
  30.                                 if(dpMap.containsKey(temp)){
  31.                                         dp[j][i] = dpMap.get(temp).length();. more info on 1point3acres.com
  32.                                         continue;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  33.                                 }
  34.                                 String ans = temp;
  35.                                 for(int k = j+1; k <= i; ++k){
  36.                                         String leftStr = s.substring(j, k);
  37.                                         String rightStr = s.substring(k, i);
  38.                                         if(dp[j][i] > dp[j][k] + dp[k][i]){. visit 1point3acres.com for more.
  39.                                                 dp[j][i] = dp[j][k] + dp[k][i];
  40.                                                 ans = dpMap.get(leftStr) + dpMap.get(rightStr);
  41.                                         }
  42.                                         if( checkRepeating(s, j, k, k, i)
  43.                                                 && ( 2 + getLength(k-j, i-j) + dp[j][k] < dp[j][i]) ){
  44.                                                 dp[j][i] = 2 + getLength(k-j, i-j) + dp[j][k];. more info on 1point3acres.com
  45.                                                 ans = String.valueOf((i-j)/(k-j)) +"["+ dpMap.get(leftStr) +"]";
  46.                                         }
  47.                                 }
  48.                                 dpMap.put(temp,ans);
  49.                         }
  50.                 }. from: 1point3acres.com/bbs
  51.                 return dpMap.get(s);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  52.         }

  53.         public static void main(String[] arg){. From 1point 3acres bbs
  54.                 System.out.println( sortestEncodeString(arg[0]) );
  55.         }
  56. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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