📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 23
跳转到指定楼层
上一主题 下一主题
收起左侧

Google 电面

全局:

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

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
LZ 刚开始面试,google算正式的第二家,没见过这道题,又是最不擅长的tree,小哥很nice,感觉不是很难,但是LZ实力太弱了,最后也没写出来。
题目是按位与两个binary tree,每个tree都是满的,比如
  rootA       root
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
说会溢出,他就笑了,然后就没有然后了。


补充内容 (2016-7-14 06:58):
写错了 结果应该是0010

上一篇:有没有当过面试官的能答个疑
下一篇:Lyft电面和Onsite

本帖被以下淘专辑推荐:

  • · Google|主题: 54, 订阅: 46
推荐
poligun 2016-7-14 04:58:35 | 只看该作者
全局:
虽然我也没看懂题意是什么,不过感觉是要用 stack 实现一个 Binary Tree In-order Iterator。
回复

使用道具 举报

推荐
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) {
  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;">;
  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;
  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.     <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>) {
  16.         ret.<span style="color:#9876aa;">right </span>= <span style="color:#cc7832;">null;
  17. </span><span style="color:#cc7832;">    </span>}
  18.     <span style="color:#cc7832;">else </span>{
  19.         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;">;
  20. </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;">;
  21. </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;">;
  22. </span><span style="color:#cc7832;">    </span>}

  23.     <span style="color:#cc7832;">return </span>ret<span style="color:#cc7832;">;
  24. </span>}
复制代码
回复

使用道具 举报

推荐
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;
  5.         if (t1.left == null && t1.right == null){
  6.             if (t1.val == 0)//0 下面的都是0
  7.                 setToZero(t2);
  8.             return;//1 下面的不用管
  9.         }
  10.         AndTree(t1.left,t2.left);
  11.         AndTree(t1.right,t2.right);
  12.     }

  13.     /**
  14.      * set leafs to zero
  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.         }
  24.         setToZero(node.left);
  25.         setToZero(node.right);
  26.     }

  27.     public static void main(String[] args) {
  28.         TreeNode t1 = new TreeNode(-1);
  29.         t1.left = new TreeNode(0);
  30.         t1.right = new TreeNode(1);
  31.         TreeNode t2 = new TreeNode(-1);
  32.         t2.left = new TreeNode(-1);
  33.         t2.left.left = new TreeNode(1);
  34.         t2.left.right = new TreeNode(0);
  35.         t2.right = new TreeNode(-1);
  36.         t2.right.left = new TreeNode(1);
  37.         t2.right.right = new TreeNode(0);
  38.         new AndTree().AndTree(t1,t2);
  39.         System.out.println(t2);
  40.     }
  41. }
复制代码

补充内容 (2016-7-14 10:49):
就是same tree原题改的, 0的下面都是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
应该是这个意思,但是是做&amp;吧

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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