一亩三分地论坛

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

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

GOOGLE 二面面经

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

2016(4-6月) 码农类 硕士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
上次谷歌第一面,HR说还不能确定可不可以进入下一轮,所以加面一场,今天下午才面的。

电话准时打来,估计是个欧洲小哥,面试流程有点反常,一开始就问我有没有什么问题要问的,我就只好把准备的几个问题给问了。. 鍥磋鎴戜滑@1point 3 acres

然后进入coding环节,貌似是一道新题啊,我还没有在面经或者哪里看到过。

函数签名为 int countChunk(String input), 给定一个字符串,找出最多有多少个chunked palindrome,

正常的palindrome是abccba, chunked palindrome的定义是:比如volvo, 可以把vo划分在一起,(vo) (l) (vo),那么它是个palindrome。求实现返回最大的chunk 数量。. Waral 鍗氬鏈夋洿澶氭枃绔,

大家有什么想法吗?一起来讨论讨论。. 1point3acres.com/bbs


评分

3

查看全部评分

本帖被以下淘专辑推荐:

mdyuki1016 发表于 2016-6-19 07:43:58 | 显示全部楼层
试着写了一下, 双指针, On 时间复杂度. 可能会有conner case, 但是上面大家例子,都可以通过.. Waral 鍗氬鏈夋洿澶氭枃绔,

    . From 1point 3acres bbs
    public static int chunkedPalindrome(String s) {
        int l = 0, r = s.length() -1;.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int count = 0;
        while (l <= r) {. 1point 3acres 璁哄潧
            if (s.charAt(l) == s.charAt(r)) {
                if (l == r) count+=1;. from: 1point3acres.com/bbs
                else count +=2;
                l++;
                r--;
            } else {
                int pl = l, pr = r;
                while (l < r && !s.substring(pl,l+1).equals(s.substring(r,pr+1))) {
                    l++;
                    r--;
                }
                if (l < r) count+=2;
                else count+=1;
                l++;r--;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        }
        return count;
    }
回复 支持 2 反对 0

使用道具 举报

lyudison 发表于 2015-11-24 01:34:25 | 显示全部楼层
写了一个时间复杂度O(n^2)的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
int countMaxChunks(string str) {
  int count = 0;
  int i = 0, j = str.size()-1; // scan from the two sides. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  int prev_i = i, prev_j = j;. Waral 鍗氬鏈夋洿澶氭枃绔,
  while(i<j) {
    string chunk1 = str.substr(prev_i, i+1);
    string chunk2 = str.substr(j, prev_j+1);
    if (chunk1==chunk2) {
      count++;
      prev_i = i+1;. from: 1point3acres.com/bbs
      prev_j = j-1;
    }   
    i++; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
    j--;. more info on 1point3acres.com
  }
  count *= 2;
  // if odd string
  if (i==j).鏈枃鍘熷垱鑷1point3acres璁哄潧
    count++;
  // even string and still has chunk left
  else if (prev_i<prev_j)
    count++;. visit 1point3acres.com for more.
  return count;
}

补充内容 (2015-11-24 01:37):
思想比较简单,但是从string的两边开始,用i和j记录当前scan到的位置,用prev_i和prev_j记录上一次找到chunk的i和j的位置的下一个字符。最后扫到中间判断一下有无多余的chunk。. more info on 1point3acres.com
.鏈枃鍘熷垱鑷1point3acres璁哄潧
补充内容 (2015-11-24 01:38):
上面提到的测试都过了
回复 支持 1 反对 0

使用道具 举报

宝贝忆彼岸 发表于 2015-11-20 13:40:33 | 显示全部楼层
我的想法是用DP做. 1point 3acres 璁哄潧

        public static  int chunkNum(String s){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                if(s == null || s.length() == 0){. from: 1point3acres.com/bbs
                        return 0;
                }
                int length = s.length();
                int[][] DP = new int[length][length];
                for(int i=length-1;i>=0;i--){
                        for(int j=i;j<length;j++){
                                if(i == j){. 鍥磋鎴戜滑@1point 3 acres
                                        DP[i][j] = 1;
                                }
                                else{
                                        int sum = 0;
                                        int mid = i + (j-i) / 2;
                                        for(int count=i;count<=mid;count++){
                                                String pre = s.substring(i,count+1);
                                                String post = s.substring(j-count+i,j+1);
                                                if(pre.equals(post)){
                                                        sum += DP[count+1][j-count+i-1];
                                                }.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        }
                                        DP[i][j] = sum;
                                }
                        }
                }
                return DP[0][length-1];
        }

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

gabrielzhuyun 发表于 2015-11-21 04:03:20 | 显示全部楼层
自己也写了一个c的,不知道对不对:

int countChunk(string input){.鏈枃鍘熷垱鑷1point3acres璁哄潧
        int n = input. size();
        vector<vector<bool>> palin(n, vector<bool> (n , false));
        int res = 0;
        for(int i = n - 1; i >=0; i--){
                for(int j = i; j < n; j++){
                        if( j - i < 2 && input[i] == input[j]){
                                palin[i][j] = true;
                                res++;
                        }
                        else{
                                int k = i;
                                int mid = (i + j) / 2;. Waral 鍗氬鏈夋洿澶氭枃绔,
                                while(k <= mid){
                                        int len = k - i + 1;
                                        int sestart = j + 1 - len;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        if(input.substr(i, len) == input.substr(sestart, len) && ((k + 1) > (sestart - 1) || palin[k + 1][sestart - 1])){
                                                palin[i][j] = true;
                                                break;
                                        }
                                        k++;
                                }       
                                if(palin[i][j]) res++;
                        }
                }
        }
        return res;
}
回复 支持 反对

使用道具 举报

子弋 发表于 2015-11-21 14:25:10 | 显示全部楼层
我对这题题意有些疑问,比如voabcvo算不算一个,它也可以分为(vo)(abc)(vo),如果这也算,我觉得二维的dp还搞不定的感觉。
如果上面不算,那(vo)(l)(vo)(l)呢? (vo)(l)(vo)(l)(vo)呢?我写不出这些case都能过的程序,跪求大神。。。。


回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-22 00:13:52 | 显示全部楼层
子弋 发表于 2015-11-21 14:25
我对这题题意有些疑问,比如voabcvo算不算一个,它也可以分为(vo)(abc)(vo),如果这也算,我觉得二维的dp还 ...

voabcvo的话就是算3个了,分法就是按照你的说的一样:(vo)(abc)(vo)

(vo)(l)(vo)(l)的话就不能这么分了,因为他不是回文,正确的划分为(volvol),函数返回1.
(vo)(l)(vo)(l)(vo) 就是这么分的,函数返回5。
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-22 00:17:56 | 显示全部楼层
宝贝忆彼岸 发表于 2015-11-20 13:40
我的想法是用DP做

        public static  int chunkNum(String s){
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
好像有点道理,不过能讲解一下在else (i != j)中的那块思路吗?
回复 支持 反对

使用道具 举报

子弋 发表于 2015-11-22 04:00:36 | 显示全部楼层
sunny_920520 发表于 2015-11-22 00:13
voabcvo的话就是算3个了,分法就是按照你的说的一样:(vo)(abc)(vo)

(vo)(l)(vo)(l)的话就不能这么分 ...

能不能再解释下为何voabcvo是三个?
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-22 05:10:49 | 显示全部楼层
子弋 发表于 2015-11-22 04:00
能不能再解释下为何voabcvo是三个?

因为最多只能分成这三块,让它“以块为单位”是回文:相当于A=vo,B=abc,原字符串=ABA。
回复 支持 反对

使用道具 举报

子弋 发表于 2015-11-22 06:08:42 | 显示全部楼层
sunny_920520 发表于 2015-11-22 05:10
因为最多只能分成这三块,让它“以块为单位”是回文:相当于A=vo,B=abc,原字符串=ABA。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
喔喔,我的意思是,那答案是1吧?还是2?(vovo)
其实我就是想问是substring还是subsequence

补充内容 (2015-11-22 06:10):
囧!忽略我我把题目理解错了!忽略上面的问题= = 我以为是返回最多有多少个chunked palindrome。。。
其实是说返回最大chunk数目类似于找chunked palindrome的最大长度?

补充内容 (2015-11-22 06:13):
最多有多少个chunked palindrome和chunk最大数目是两个问题吧?所以应该是后者?
. 1point3acres.com/bbs
补充内容 (2015-11-22 06:19):
。。。不好意思我又要补充了。。。
如果求长度,volvol不应该是(vol)(vol)返回2么
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-22 06:21:48 | 显示全部楼层
子弋 发表于 2015-11-22 06:08
喔喔,我的意思是,那答案是1吧?还是2?(vovo)
其实我就是想问是substring还是subsequence

是的,是要返回chunk的最大数目~所以vovo返回2,voabcvo返回3
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-24 01:39:39 | 显示全部楼层
lyudison 发表于 2015-11-24 01:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {. more info on 1point3acres.com
  int count = 0;

我当时也是这思路写的,最后面试官说it should work
回复 支持 反对

使用道具 举报

lyudison 发表于 2015-11-24 02:07:35 | 显示全部楼层
sunny_920520 发表于 2015-11-24 01:39. 1point 3acres 璁哄潧
我当时也是这思路写的,最后面试官说it should work

意思是太渣了吗
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-24 02:10:20 | 显示全部楼层
lyudison 发表于 2015-11-24 02:07. 1point3acres.com/bbs
意思是太渣了吗
.鐣欏璁哄潧-涓浜-涓夊垎鍦
不知道,还没收到HR的回复
回复 支持 反对

使用道具 举报

GatorAM 发表于 2015-11-24 05:33:59 | 显示全部楼层
lyudison 发表于 2015-11-24 01:34
写了一个时间复杂度O(n^2)的
int countMaxChunks(string str) {-google 1point3acres
  int count = 0;

为啥复杂度是O(n^2). 我觉得是O(n)
回复 支持 反对

使用道具 举报

lyudison 发表于 2015-11-24 09:48:10 | 显示全部楼层
GatorAM 发表于 2015-11-24 05:33
为啥复杂度是O(n^2). 我觉得是O(n)
-google 1point3acres
while一层循环,string比较是否相等又是一层。
回复 支持 反对

使用道具 举报

GatorAM 发表于 2015-11-24 11:25:16 | 显示全部楼层
lyudison 发表于 2015-11-24 09:48. 1point3acres.com/bbs
while一层循环,string比较是否相等又是一层。

哦,酱紫
回复 支持 反对

使用道具 举报

bobzhang2004 发表于 2015-12-4 12:51:28 | 显示全部楼层
请问面试官有给hint吗?他期望的时间复杂度是多少呢?
回复 支持 反对

使用道具 举报

peter_jun 发表于 2015-12-13 23:56:42 | 显示全部楼层
楼主我也有几个问题。
1。输入一定是palindrome吗?abcbad 这总输入是不是不考虑
2.  输出是最大的chunk数量,对于  ababcabab, 返回一定是5 = (ab)(ab)c(ab)(ab) 还是 = (abab)c(abab)呢
谢谢!
.1point3acres缃
补充内容 (2015-12-13 23:57):
3 =  = (abab)c(abab)
回复 支持 反对

使用道具 举报

 楼主| sunny_920520 发表于 2015-12-14 00:30:42 | 显示全部楼层
peter_jun 发表于 2015-12-13 23:56
楼主我也有几个问题。
1。输入一定是palindrome吗?abcbad 这总输入是不是不考虑
2.  输出是最大的chunk ...

你好, abcbad的话只能把它本身划分为一个大的chunk,所以chunk数量就是1.
ababcabab的话就是返回5.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

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

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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