GOOGLE 二面面经

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

电话准时打来，估计是个欧洲小哥，面试流程有点反常，一开始就问我

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

alindrome。求实现返回最大的chunk 数量。

大家有什么想法吗？一起来讨论讨论。

试着写了一下, 双指针, On 时间复杂度. 可能会有conner case, 但是上面大家例子,都可以通过.

   
    public static int chunkedPalindrome(String s) {
        int l = 0, r = s.length() -1;
        int count = 0;
        while (l <= r) {
            if (s.charAt(l) == s.charAt(r)) {
                if (l == r) count+=1;
                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;
    }

写了一个时间复杂度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;
  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;
      prev_j = j-1;
    }   
    i++;
    j--;
  }
  count *= 2;
  // if odd string
  if (i==j)
    count++;
  // even string and still has chunk left
  else if (prev_i<prev_j)
    count++;
  return count;
}

补充内容 (2015-11-24 01:37):
思想比较简单，但是从string的两边开始，用i和j记录当前scan到的位置，用prev_i和prev_j记录上一次找到chunk的i和j的位置的下一个字符。最后扫到中间判断一下有无多余的chunk。

补充内容 (2015-11-24 01:38):
上面提到的测试都过了

我的想法是用DP做

        public static  int chunkNum(String s){
                if(s == null || s.length() == 0){
                        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){
                                        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];
        }

自己也写了一个c的，不知道对不对：

int countChunk(string input){
        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;
                                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;
}

我对这题题意有些疑问，比如voabcvo算不算一个，它也可以分为(vo)(abc)(vo)，如果这也算，我觉得二维的dp还搞不定的感觉。
如果上面不算，那(vo)(l)(vo)(l)呢？ (vo)(l)(vo)(l)(vo)呢？我写不出这些case都能过的程序，跪求大神。。。。

子弋 发表于 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。

宝贝忆彼岸 发表于 2015-11-20 13:40
我的想法是用DP做

        public static  int chunkNum(String s){

好像有点道理，不过能讲解一下在else (i != j)中的那块思路吗？

momo__ 发表于 2015-11-22 00:13
voabcvo的话就是算3个了，分法就是按照你的说的一样：(vo)(abc)(vo)

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

能不能再解释下为何voabcvo是三个？

子弋 发表于 2015-11-22 04:00
能不能再解释下为何voabcvo是三个？

因为最多只能分成这三块，让它“以块为单位”是回文：相当于A=vo，B=abc，原字符串=ABA。

momo__ 发表于 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最大数目是两个问题吧？所以应该是后者？

补充内容 (2015-11-22 06:19):
。。。不好意思我又要补充了。。。
如果求长度，volvol不应该是(vol)(vol)返回2么

子弋 发表于 2015-11-22 06:08
喔喔，我的意思是，那答案是1吧？还是2？（vovo）
其实我就是想问是substring还是subsequence

是的，是要返回chunk的最大数目~所以vovo返回2，voabcvo返回3