一亩三分地论坛

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

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

Google 电面

[复制链接] |试试Instant~ |关注本帖
yzmys000 发表于 2016-7-13 05:01:47 | 显示全部楼层 |阅读模式

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

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

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

x
LZ 刚开始面试,google算正式的第二家,没见过这道题,又是最不擅长的tree,小哥很nice,感觉不是很难,但是LZ实力太弱了,最后也没写出来。
题目是按位与两个binary tree,每个tree都是满的,比如
  rootA       rootB
  /    \        /     \
0      1     / \     / \. 1point 3acres 璁哄潧
             1   0   1  0
然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是  
    newRoot
    /          \
  / \         / \
0   1       1  0
说中间层不用管,只有leaf node有值
LZ想的是把A和B的值都求出来,然后按位补齐,再与,再建一个new tree 然后写了一半时间到了,小哥说万一这个树depth是100怎么办,然后我说会溢出,他就笑了,然后就没有然后了。.鏈枃鍘熷垱鑷1point3acres璁哄潧

. 鍥磋鎴戜滑@1point 3 acres
补充内容 (2016-7-14 06:58):
写错了 结果应该是0010

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 45
poligun 发表于 2016-7-14 04:58:35 | 显示全部楼层
虽然我也没看懂题意是什么,不过感觉是要用 stack 实现一个 Binary Tree In-order Iterator。
回复 支持 0 反对 1

使用道具 举报

edyyy 发表于 2016-7-13 06:12:45 | 显示全部楼层
不懂什麼意思啊
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-13 06:13:00 | 显示全部楼层
这个题目有意思
每一层的node个数是 2^n, 所以假设大的那棵树的leaf那一层有 M 个 node, 小的那棵树的leaf那一层有 N 个 node, M 一定是 N 的 2^k 倍数。
所以先对 小的那棵树 做 bfs, 然后存储Leaf 的 n 个Node。 然后再对 大的那颗树做 bfs, 在 leaf 那一层 进行Update 应该就可以了
回复 支持 反对

使用道具 举报

vancexu 发表于 2016-7-13 06:45:18 | 显示全部楼层
lz能用英文解释一下“然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是”是什么意思吗?
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-7-13 07:04:59 | 显示全部楼层
感觉上题目意思是小树的leaf node和大树对应以相同位置node为根的subtree来做XOR吧。用层遍历或者dfs都可以解决。
回复 支持 反对

使用道具 举报

say543 发表于 2016-7-13 14:31:31 | 显示全部楼层
题目不太清楚 楼主能解释下example 的new root tree 怎么找出来的吗?
回复 支持 反对

使用道具 举报

mkcing 发表于 2016-7-14 01:51:33 | 显示全部楼层
Can you explain the question again?
回复 支持 反对

使用道具 举报

todayand 发表于 2016-7-14 05:08:52 | 显示全部楼层
alexanderzjs 发表于 2016-7-13 07:04.鐣欏璁哄潧-涓浜-涓夊垎鍦
感觉上题目意思是小树的leaf node和大树对应以相同位置node为根的subtree来做XOR吧。用层遍历或者dfs都可以 ...

应该是这个意思,但是是做&吧
回复 支持 反对

使用道具 举报

alexanderzjs 发表于 2016-7-14 05:16:31 | 显示全部楼层
todayand 发表于 2016-7-14 05:08
应该是这个意思,但是是做&吧

看lz给的例子应该是xor,如果是&那左边子树应该是两个0,不过这个不是重点:-)
回复 支持 反对

使用道具 举报

 楼主| yzmys000 发表于 2016-7-14 06:59:20 | 显示全部楼层
vancexu 发表于 2016-7-13 06:45
lz能用英文解释一下“然后输出left child 跟 left child 与 right child 跟right child 与 输出结果是”是 ...

就是左子树跟左子树and 右子树跟右子树and
回复 支持 反对

使用道具 举报

 楼主| yzmys000 发表于 2016-7-14 07:00:00 | 显示全部楼层
alexanderzjs 发表于 2016-7-14 05:16
看lz给的例子应该是xor,如果是&那左边子树应该是两个0,不过这个不是重点:-)

结果写错了 是& 不好意思~
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-7-14 08:47:28 | 显示全部楼层
大概写了下代码,递归做的,跑了几个简单的测试:
  1. <span style="color:#cc7832;">public </span>TreeNode <span style="color:#ffc66d;">bitAnd</span>(TreeNode a<span style="color:#cc7832;">, </span>TreeNode b) {. visit 1point3acres.com for more.
  2.     <span style="color:#cc7832;">if</span>(a==<span style="color:#cc7832;">null </span>&& b == <span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return null;
  3. </span><span style="color:#cc7832;">    else if</span>(a==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>b<span style="color:#cc7832;">;
  4. </span><span style="color:#cc7832;">    else if</span>(b==<span style="color:#cc7832;">null</span>) <span style="color:#cc7832;">return </span>a<span style="color:#cc7832;">;. from: 1point3acres.com/bbs
  5. </span><span style="color:#cc7832;">
  6. </span><span style="color:#cc7832;">    </span>TreeNode ret = <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val </span>& b.<span style="color:#9876aa;">val</span>)<span style="color:#cc7832;">;
  7. </span><span style="color:#cc7832;">    if</span>(a.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">left</span>==<span style="color:#cc7832;">null</span>) {
  8.         ret.<span style="color:#9876aa;">left </span>= <span style="color:#cc7832;">null;. 鍥磋鎴戜滑@1point 3 acres
  9. </span><span style="color:#cc7832;">    </span>}
  10.     <span style="color:#cc7832;">else</span>{
  11.         TreeNode leftA = a.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;
  12. </span><span style="color:#cc7832;">        </span>TreeNode leftB = b.<span style="color:#9876aa;">left </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">left</span><span style="color:#cc7832;">;
  13. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">left </span>= bitAnd(leftA<span style="color:#cc7832;">, </span>leftB)<span style="color:#cc7832;">;
  14. </span><span style="color:#cc7832;">    </span>}
  15. . more info on 1point3acres.com
  16.     <span style="color:#cc7832;">if</span>(a.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null </span>&& b.<span style="color:#9876aa;">right</span>==<span style="color:#cc7832;">null</span>) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  17.         ret.<span style="color:#9876aa;">right </span>= <span style="color:#cc7832;">null;
  18. </span><span style="color:#cc7832;">    </span>}
  19.     <span style="color:#cc7832;">else </span>{
  20.         TreeNode rightA = a.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(a.<span style="color:#9876aa;">val</span>) : a.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  21. </span><span style="color:#cc7832;">        </span>TreeNode rightB = b.<span style="color:#9876aa;">right </span>== <span style="color:#cc7832;">null </span>? <span style="color:#cc7832;">new </span>TreeNode(b.<span style="color:#9876aa;">val</span>) : b.<span style="color:#9876aa;">right</span><span style="color:#cc7832;">;
  22. </span><span style="color:#cc7832;">        </span>ret.<span style="color:#9876aa;">right </span>= bitAnd(rightA<span style="color:#cc7832;">, </span>rightB)<span style="color:#cc7832;">;
  23. </span><span style="color:#cc7832;">    </span>}

  24.     <span style="color:#cc7832;">return </span>ret<span style="color:#cc7832;">;. more info on 1point3acres.com
  25. </span>}
复制代码
回复 支持 反对

使用道具 举报

muybienw 发表于 2016-7-14 08:51:54 | 显示全部楼层
代码贴歪了,再试一下
  1.    
  2. public TreeNode bitAnd(TreeNode a, TreeNode b) {
  3.         if(a==null && b == null) return null;
  4.         else if(a==null) return b;
  5.         else if(b==null) return a;

  6.         TreeNode ret = new TreeNode(a.val & b.val);
  7.         if(a.left==null && b.left==null) {
  8.             ret.left = null;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  9.         }
  10.         else{
  11.             TreeNode leftA = a.left == null ? new TreeNode(a.val) : a.left;
  12.             TreeNode leftB = b.left == null ? new TreeNode(b.val) : b.left;. from: 1point3acres.com/bbs
  13.             ret.left = bitAnd(leftA, leftB);
  14.         }
  15. . more info on 1point3acres.com
  16.         if(a.right==null && b.right==null) {
  17.             ret.right = null;. more info on 1point3acres.com
  18.         }
  19.         else {
  20.             TreeNode rightA = a.right == null ? new TreeNode(a.val) : a.right;
  21.             TreeNode rightB = b.right == null ? new TreeNode(b.val) : b.right; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  22.             ret.right = bitAnd(rightA, rightB);. from: 1point3acres.com/bbs
  23.         }

  24.         return ret;
  25.     }
复制代码
回复 支持 反对

使用道具 举报

hyj143 发表于 2016-7-14 08:57:24 | 显示全部楼层
muybienw 发表于 2016-7-14 08:51
代码贴歪了,再试一下

觉得有点 overkill 了, 因为题目说明, 中间层的Node不需要考虑 &  的
回复 支持 反对

使用道具 举报

hxtang 发表于 2016-7-14 09:44:22 | 显示全部楼层
yzmys000 发表于 2016-7-14 07:00
结果写错了 是& 不好意思~

lz你能解释一下如果两棵树不一样高的时候按位补齐是怎么补的吗?
比如你例子里:0 1是补成0 0 1 1再跟root B叶节点&,还是补成0 0 0 1再跟叶节点&?  

以及这个题似乎in place比较方便,小哥规定你输出一定要建一棵新树吗?
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-14 10:16:51 | 显示全部楼层
这题跟旁边的那个题...剪枝天壤之别的难度....
回复 支持 反对

使用道具 举报

readman 发表于 2016-7-14 10:48:23 | 显示全部楼层
  1. public class AndTree {
  2.     public void AndTree(TreeNode t1, TreeNode t2) {
  3.         if (t1 == null && t2 == null)
  4.                 return;. more info on 1point3acres.com
  5.         if (t1.left == null && t1.right == null){
  6.             if (t1.val == 0)//0 下面的都是0
  7.                 setToZero(t2);
  8.             return;//1 下面的不用管
  9.         }. From 1point 3acres bbs
  10.         AndTree(t1.left,t2.left);
  11.         AndTree(t1.right,t2.right);
  12.     }

  13.     /**
  14.      * set leafs to zero.1point3acres缃
  15.      * @param node  root
  16.      */
  17.     public void setToZero(TreeNode node) {
  18.         if (node == null)
  19.             return;
  20.         if (node.left == null && node.right == null){
  21.             node.val = 0;
  22.             return;
  23.         }
    . 1point3acres.com/bbs
  24.         setToZero(node.left);
  25.         setToZero(node.right);
  26.     }

  27. . 1point3acres.com/bbs
  28.     public static void main(String[] args) {
  29.         TreeNode t1 = new TreeNode(-1);
  30.         t1.left = new TreeNode(0);
  31.         t1.right = new TreeNode(1);
  32.         TreeNode t2 = new TreeNode(-1);
  33.         t2.left = new TreeNode(-1);. visit 1point3acres.com for more.
  34.         t2.left.left = new TreeNode(1);
  35.         t2.left.right = new TreeNode(0);
  36.         t2.right = new TreeNode(-1);
  37.         t2.right.left = new TreeNode(1);
  38.         t2.right.right = new TreeNode(0);
  39.         new AndTree().AndTree(t1,t2);
  40.         System.out.println(t2);
  41.     }
  42. }
复制代码
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接跳出
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-7-15 04:39:53 | 显示全部楼层
readman 发表于 2016-7-14 10:48-google 1point3acres
补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是0, 需要改一下, 1 的下面不用管, 直接 ...
. 鍥磋鎴戜滑@1point 3 acres
请问follow up怎么做呢?
回复 支持 反对

使用道具 举报

greentrail 发表于 2016-7-15 04:42:21 | 显示全部楼层
根据楼主的例子,题目要求是这样做and. roota (01) and rootb (1010), 注意是左对齐,结果是0010. 两个树可能高度不同。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
在前面的帖子中,hyj143已经把思路说的很清楚了。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 10:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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