一亩三分地论坛

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

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

Google 电话面经

[复制链接] |试试Instant~ |关注本帖
caiqi8877 发表于 2016-4-30 03:08:49 | 显示全部楼层 |阅读模式

2016(4-6月) 码农类 硕士 全职@Google - 网上海投 - 技术电面 |Other其他

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

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

x
刚刚结束的Google电面,在google呆了8年的貌似国人大哥。

1 判断一个树是不是另一个的subTree.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
2 shortest palindrome.. from: 1point3acres.com/bbs

求个onsite

评分

1

查看全部评分

yueliu2366 发表于 2016-4-30 03:41:52 | 显示全部楼层
第一题比较容易,练习下:
public class Solution {
    public boolean isSubTree(Treenode n1, Treenode n2) {
.1point3acres缃        if (n1 == null && n2 == null) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
            return true;
        }
        if (n1 == null || n2 == null) {
            return false;
        }
        if (n1.val == n2.val) {
            return isSubTree(n1.left, n2.left) && isSubTree(n1.right, n2.right);. Waral 鍗氬鏈夋洿澶氭枃绔,
        }.1point3acres缃
        
        return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);
    }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
}

第二题比较难理解但是毕竟是lc原题啊,恭喜楼主,onsite应该没问题,粘粘喜气
回复 支持 1 反对 0

使用道具 举报

EileneLiu 发表于 2016-4-30 03:15:16 | 显示全部楼层
祝楼主好运有onsite.
我有个问题 请问楼主什么时候做的OA? 做完之后多久HR 联系你的呢
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 04:24:49 | 显示全部楼层
EileneLiu 发表于 2016-4-30 03:15
祝楼主好运有onsite.
我有个问题 请问楼主什么时候做的OA? 做完之后多久HR 联系你的呢

额,我是海投的,并没有做OA
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 04:27:09 | 显示全部楼层
yueliu2366 发表于 2016-4-30 03:41
第一题比较容易,练习下:
public class Solution {
    public boolean isSubTree(Treenode n1, Treenod ...
. From 1point 3acres bbs
额,你做的并不对,当n1和n2的val相同时,你需要判断子树完全相同,而不是继续递归。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-30 04:37:15 | 显示全部楼层
yueliu2366 发表于 2016-4-30 03:41
第一题比较容易,练习下:
public class Solution {
    public boolean isSubTree(Treenode n1, Treenod ...

  应该是:
        if (n1.val == n2.val) {
             if isSubTree(n1.left, n2.left) && isSubTree(n1.right, n2.right):
                  return true;
        }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        return isSubTree(n1.left, n2) || isSubTree(n1.right, n2);
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-30 04:45:15 | 显示全部楼层
caiqi8877 发表于 2016-4-30 04:27
额,你做的并不对,当n1和n2的val相同时,你需要判断子树完全相同,而不是继续递归。
-google 1point3acres
哦对。。多谢指正
回复 支持 反对

使用道具 举报

wangmengcathy 发表于 2016-4-30 06:18:09 | 显示全部楼层
LZ第一题是~O(n^2)还是O(n)的复杂度做的
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 06:19:10 | 显示全部楼层
wangmengcathy 发表于 2016-4-30 06:18
LZ第一题是~O(n^2)还是O(n)的复杂度做的

你说的是第二题吧,两个都写了。
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-4-30 07:25:21 | 显示全部楼层
多谢lz。 Bless第二题是啥意思?
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 07:52:17 | 显示全部楼层
houqingniao 发表于 2016-4-30 07:25
多谢lz。 Bless第二题是啥意思?

LC 214基本原题
回复 支持 反对

使用道具 举报

duduhaha 发表于 2016-4-30 09:00:23 | 显示全部楼层
楼主第一题就是先写个isSameTree(node1, node2)的函数,然后对第一棵树的每个节点都调用这个函数吧?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 11:07:13 | 显示全部楼层
yueliu2366 发表于 2016-4-30 03:41
第一题比较容易,练习下:
public class Solution {
    public boolean isSubTree(Treenode n1, Treenod ...

我看你经常回复Google的帖子,你什么时候面啊?我暑假就去面了...
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 11:15:31 | 显示全部楼层
楼主第二题面试官要求写KMP优化到O(N)? ?电面都问的这么难
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-30 11:38:11 | 显示全部楼层
adiggo 发表于 2016-4-30 04:37-google 1point3acres
应该是:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
        if (n1.val == n2.val) {
             if isSubTree(n1.left, n2.left) && isSubT ...

这个做法好像也不行。楼主问的意思应该是要从跟节点到所有叶子节点完全相同的,才能叫做subtree。想了下,有个O(mn)的做法就是对每个节点都判断两个树是不是identical。但是有个O(n)的做法,就是每次判断是不是subtree的递归过程中,同时记录两个树的size,如果n2是n1的"subtree"(不是题意那个subtree,这里指的是只要n2被包括在n1内就可以,不一定要到叶子节点), 同时n2的size和n1的size一样大,那么这两个条件限制,就可以保证n2是n1的subtree(题目要求的那种)。
public class Solution {
    public boolean isSubTree(Treenode n1, Treenode n2) {
. Waral 鍗氬鏈夋洿澶氭枃绔,       int []tree1Size = new int[1];
       int []tree2Size = new int[1];
       return isSubTreeHelper(n1, n2, tree1Size, tree2Size);
    }
   
    //该函数返回以n2根节点的树是否为以n1为根节点的数的一部分(不一定是subtree),并且返回两个树分别的节点个数
    boolean isSubTreeHelper(Treenode n1, Treenode n2, int []tree1Size, int []tree2Size) {
        if (n1 == null && n2 == null) {
            return true;
        }
        if (n1 == null) {
            tree2Size[0] = 1;
            return false;
        }
.鐣欏璁哄潧-涓浜-涓夊垎鍦        if (n2 == null) {
            tree1Size[0] = 1;
            return false;
        }
        if (n1.val == n2.val) {
          int ret1 = 1;
          int ret2 = 1;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
          boolean ret = isSubTreeHelper(n1.left, n2.left, tree1Size, tree2Size);
          ret1 += tree1Size[0];. from: 1point3acres.com/bbs
          ret2 += tree2Size[0];
          ret = ret && (tree1Size[0] == tree2Size[0]);. 1point 3acres 璁哄潧
         
          tree1Size[0] = 0;. 1point3acres.com/bbs
          tree2Size[0] = 0;
          ret = ret && isSubTreeHelper(n1.right, n2.right, tree1Size, tree2Size);
          ret1 += tree1Size[0];. From 1point 3acres bbs
          ret2 += tree2Size[0];
          ret = ret && (tree1Size[0] == tree2Size[0]);
.1point3acres缃          . 1point3acres.com/bbs
          tree1Size[0] = ret1;
          tree2Size[0] = ret2;
         
          return ret;
        }
        
  return isSubTreeHelper(n1.left, n2, tree1Size, tree2Size) || isSubTreeHelper(n1.right, n2, tree1Size,tree2Size);
    }
}
鏉ユ簮涓浜.涓夊垎鍦拌鍧.

想请问下楼主,当时面试的时候要求的是O(mn)的解法,还是要优化到O(n)的呢?
回复 支持 反对

使用道具 举报

yueliu2366 发表于 2016-4-30 11:39:37 | 显示全部楼层
hidden_track 发表于 2016-4-30 11:07. 鍥磋鎴戜滑@1point 3 acres
我看你经常回复Google的帖子,你什么时候面啊?我暑假就去面了...

你好,我还没面呢,大概3周后才电面,现在lc一遍都还没刷完,好慌啊。你面的怎么样呢?
回复 支持 反对

使用道具 举报

hidden_track 发表于 2016-4-30 11:46:51 | 显示全部楼层
我正在约一周后的电面,请问你是本科还是研究生?准备情况是把lc刷完2遍然后地里狗家的面筋也刷完一遍所以觉得可以去试试了,哈哈,剩下的看天
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 12:24:38 | 显示全部楼层
hidden_track 发表于 2016-4-30 11:15
楼主第二题面试官要求写KMP优化到O(N)? ?电面都问的这么难
. 1point3acres.com/bbs
恩,我觉得我的电面比起好多人已经简单很多了。。。
回复 支持 反对

使用道具 举报

adiggo 发表于 2016-4-30 12:25:53 | 显示全部楼层
yueliu2366 发表于 2016-4-30 11:38.鐣欏璁哄潧-涓浜-涓夊垎鍦
这个做法好像也不行。楼主问的意思应该是要从跟节点到所有叶子节点完全相同的,才能叫做subtree。想了下 ...

谢谢指正。 这里的确该用个idendital的function。  但是没看懂你的答案。。。 在网上找到一个o(n)答案, 说是generate 两个node 的preorder 和inorder, 证明另外一个是前一个preorder, inorder的substring 即可。。
回复 支持 反对

使用道具 举报

 楼主| caiqi8877 发表于 2016-4-30 12:26:17 | 显示全部楼层
yueliu2366 发表于 2016-4-30 11:38
这个做法好像也不行。楼主问的意思应该是要从跟节点到所有叶子节点完全相同的,才能叫做subtree。想了下 ...

没有那么复杂 http://www.geeksforgeeks.org/che ... nother-binary-tree/
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 11:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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