一亩三分地论坛

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

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

google mtv onsite面经 5/9

[复制链接] |试试Instant~ |关注本帖
Newneo 发表于 2016-5-11 02:14:09 | 显示全部楼层 |阅读模式

2017(4-6月) 码农类 硕士 全职@Google - 内推 - Onsite |Other在职跳槽

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

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

x
整体感觉题不难,非常重视complexity的分析,自己还是有很多地方做的不好,所以报答案的时候也没有底气,

ps: onsite一般每轮都问几个问题啊? 只问了一道题是要挂的表现么?

第一轮: 最简单contains duplicates,注意在没有dup的时候返回值的处理,如果返回类型是int,就不能返回null。要把返回值改成Integer
           加了限制条件:1.所有数字>=1,<=n-1 2.sorted 3.只有一组duplicates
           binary search:分隔条件是,1,2,3,4,5,5
                                     index:     0,1,2,3,4,5 可以看到一个数字如果前面没有dup num=i+1,否则 num=i,以此为比较条件
第二轮:一个string,如何插入数目最少的字符使得它变成panlindrome.     
             two pointers,指向首尾两个字符,如果一样start++,end—, 如果不一样,就要在start前面加char(end),end—或者在end后面加char(start),start++找最小值
                        
              public int function(string s , int start, int end){
                   if(s.length()==0) return 0;
            if(start>=end) return 0;
            if(s.charAt(start) == s.charAt(end)) return f(s,start+1,end-1);
            else
               return Math.min(f(s,start+1,end),f(s,start,end-1))+1;
              }
分析时间复杂度: worst case   “abc” 这种所有字符都不一样的最差,因为往左往右没有区别
                                            level 1:    [ abcd]
                                            level 2:    [bcd]      [abc]
                                            level3:     [bc] [cd] [ab] [bc]
                                            level 4:    [c][c][d][a][c]
  time complexity O(2^n)
   可以看出来level 3[bc] 重复计算了 level4重复计算的更多,简化方法是可以用一张map,然后减少重复计算

第三轮: 判断两个binary tree 是不是similar:similar的要求是经过一定数目的交换左右子树,两个树是identical的
       public Boolean isSimilar(root1, root2){
            if(root1 == null && root2 == null) return true;
            if(root1!=null && root2==null) return false;
            if(root1==null && root2!=null) return false
            if(root1.val!=root2.val) return false;
            Boolean ll = isSimilar(root1.left, root2.left);
            if(ll)
               return isSimilar(root1.right, root2.right);
           else{
                  Boolean lr =  isSimilar(root1.left, root2.right);
                  if(!lr)
                     return false;      
                  else
                    return isSimilar((root1.right, root2.left);
)
           }
时间复杂度 O(n^log3)——据说这个特别复杂,面试官告诉我了答案,他说是homwork。。正在google中
优化:没答上来,给的提示有点忘了,方向是去看如何switch,然后看两个树是不是identical


第四轮: input: 数组
              output是input右边一个比它大的数字的坐标
              例如     10 8 6 8 11 9
              index    0  1 2 3 4   5
              output  4  4 3 4 -1  -1 没有是-1
用栈里维护所有递减的数字,每来一个新的数字就与栈顶元素比较,并且赋值
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
找popular element in sorted array,频率n/4  这种数只可能出现在四分之一,二分之一,四分之三的位置

第五轮: double sqrt(double x) 要求误差小于epslon
             1:注意binary search的范围 end=(num>1) num: 1
             2:  while(end-start>epslon)
时间复杂度: num/(2^n)<epslon           O(n)是log(num/epslon)         

评分

1

查看全部评分

caiqi8877 发表于 2016-5-11 02:27:12 | 显示全部楼层
第二题好像是lc原题吧
回复 支持 反对

使用道具 举报

 楼主| Newneo 发表于 2016-5-11 02:32:27 | 显示全部楼层
不是完全一样,这个可以往任何地方插入字符,不是非常插到前面
回复 支持 反对

使用道具 举报

GavinM 发表于 2016-5-11 03:38:33 | 显示全部楼层
第二题用dp? dp[i][j] = Min(dp[i][j - 1], dp[i - 1][j]) + 1?如果i和j不同的话。
第三题是不是和LC上面scramble string类似。
回复 支持 反对

使用道具 举报

lll_2013 发表于 2016-5-11 04:18:10 | 显示全部楼层
楼主,你能不能解释下第三题complexity是不是T(n) = T(n/2) + T(n/2) + T(n /2)。
所以O(3^logn) ?

补充内容 (2016-5-10 15:19):
底数是2

补充内容 (2016-5-10 15:24):
还有可不可以同层比较,那就省略了交换,因为条件允许子树交换。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-5-11 07:41:59 | 显示全部楼层
GavinM 发表于 2016-5-11 03:38
第二题用dp? dp[j] = Min(dp[j - 1], dp[j]) + 1?如果i和j不同的话。
第三题是不是和LC上面scramble strin ...

我觉得第二题也是dp。有点类似edit distance
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-5-12 02:57:24 | 显示全部楼层
第一题二分条件不对吧, 按照例子,如果duplicate出现在前面的话,你这样就往后搜索了。。。
回复 支持 反对

使用道具 举报

weijinchuan10 发表于 2016-10-30 04:07:32 | 显示全部楼层
insert min characters to form palindrome

#include <stdio.h>.1point3acres缃
#include <limits.h>
#include <string.h>

int min(int a, int b){
    return a <= b ? a : b;
}

int findMinInsertions(char str[]).鐣欏璁哄潧-涓浜-涓夊垎鍦
{
    if(strlen(str) == 0) return 0;
    int dp[strlen(str)][strlen(str)];
    for(int i=0; i<strlen(str); i++){
        for(int j=0; j<strlen(str); j++){
            dp[i][j] = 0;
        }
    }
    for(int l = 1; l<=strlen(str); l++){
        for(int i=0; i<=strlen(str)-l; i++){-google 1point3acres
            int start = i, end = i+l-1;.1point3acres缃
            if(str[start] == str[end]){
                dp[start][end] = dp[start+1][end-1];
            }else{
                dp[start][end] = min(1+dp[start+1][end], 1+dp[start][end-1]);
            }
        }   
    }
    return dp[0][strlen(str)-1];. Waral 鍗氬鏈夋洿澶氭枃绔,
   
}. Waral 鍗氬鏈夋洿澶氭枃绔,

// Driver program to test above functions
int main()
{. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
        char str[] = "abcde";
        printf("%d", findMinInsertions(str));
        return 0;
}
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-10-30 10:35:12 | 显示全部楼层
lll_2013 发表于 2016-5-11 04:18
楼主,你能不能解释下第三题complexity是不是T(n) = T(n/2) + T(n/2) + T(n /2)。
所以O(3^logn) ?

请问到底是O(3^logn)还是 O(n^log3)呀?谢谢
回复 支持 反对

使用道具 举报

weijinchuan10 发表于 2016-10-31 04:20:34 | 显示全部楼层
knight0clk 发表于 2016-10-30 10:35
请问到底是O(3^logn)还是 O(n^log3)呀?谢谢

it should be O(n^log3), just applying master thm T(n) = 3*T(n/2) + O(1). Do you have ideas how to optimize it? thx!
回复 支持 反对

使用道具 举报

knight0clk 发表于 2016-10-31 04:39:04 | 显示全部楼层
weijinchuan10 发表于 2016-10-31 04:20
it should be O(n^log3), just applying master thm T(n) = 3*T(n/2) + O(1). Do you have ideas how to  ...

Haha, I just found that n^log3 equals 3^logn. It is easy, you could have a try. I think this is the fastest way, right?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 04:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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