亚麻OA求砸,面经神衣护体!


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
天天打游戏、照样领工资、还办H1B
这份工作你要不要?
把贵司招聘信息放这里
查看: 8298|回复: 36
收起左侧

GOOGLE 二面面经

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

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

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

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

x
上次谷歌第一面,HR说还不能确定可不可以进入下一轮,所以加面一场,今天下午才面的。
. more info on 1point3acres.com
电话准时打来,估计是个欧洲小哥,面试流程有点反常,一开始就问我有没有什么问题要问的,我就只好把准备的几个问题给问了。

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

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

正常的palindrome是abccba, chunked palindrome的定义是:比如volvo, 可以把vo划分在一起,(vo) (l) (vo),那么它是个palindrome。求实现返回最大的chunk 数量。

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


评分

3

查看全部评分

本帖被以下淘专辑推荐:

mdyuki1016 发表于 2016-6-19 07:43:58 | 显示全部楼层
试着写了一下, 双指针, On 时间复杂度. 可能会有conner case, 但是上面大家例子,都可以通过.. From 1point 3acres bbs

    . 1point3acres.com/bbs
    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++;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                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;.1point3acres缃
  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);. visit 1point3acres.com for more.
    string chunk2 = str.substr(j, prev_j+1);. 鍥磋鎴戜滑@1point 3 acres
    if (chunk1==chunk2) {
      count++;
      prev_i = i+1;-google 1point3acres
      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。
. From 1point 3acres bbs
补充内容 (2015-11-24 01:38):
上面提到的测试都过了
回复 支持 1 反对 0

使用道具 举报

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

        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--){. more info on 1point3acres.com
                        for(int j=i;j<length;j++){
                                if(i == j){
                                        DP[i][j] = 1;
                                }
                                else{
                                        int sum = 0;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                        int mid = i + (j-i) / 2;
                                        for(int count=i;count<=mid;count++){
                                                String pre = s.substring(i,count+1);-google 1point3acres
                                                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的,不知道对不对:. visit 1point3acres.com for more.

int countChunk(string input){. more info on 1point3acres.com
        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++;
                        }
                }. from: 1point3acres.com/bbs
        }
        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. Waral 鍗氬鏈夋洿澶氭枃绔,
我的想法是用DP做

        public static  int chunkNum(String s){

好像有点道理,不过能讲解一下在else (i != j)中的那块思路吗?
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-22 05:10:49 | 显示全部楼层
子弋 发表于 2015-11-22 04:00. From 1point 3acres bbs
能不能再解释下为何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的最大长度?
. 1point3acres.com/bbs
补充内容 (2015-11-22 06:13):
最多有多少个chunked palindrome和chunk最大数目是两个问题吧?所以应该是后者?

补充内容 (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. 1point3acres.com/bbs
写了一个时间复杂度O(n^2)的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
int countMaxChunks(string str) {
  int count = 0;
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我当时也是这思路写的,最后面试官说it should work
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

 楼主| sunny_920520 发表于 2015-11-24 02:10:20 | 显示全部楼层

不知道,还没收到HR的回复
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

GatorAM 发表于 2015-11-24 11:25:16 | 显示全部楼层
lyudison 发表于 2015-11-24 09:48
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)呢
谢谢!

补充内容 (2015-12-13 23:57):
3 =  = (abab)c(abab)
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-10-21 01:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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