一亩三分地论坛

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

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

Microsoft校园面,2016暑期实习,跪了

[复制链接] |试试Instant~ |关注本帖
chilling 发表于 2015-10-10 04:42:28 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 本科 实习@Microsoft - 校园招聘会 - 校园招聘会 |Other其他

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

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

x
校园面,微软2016暑期实习,职位是software developer。. from: 1point3acres.com/bbs
一个三哥,一上来就让写代码(没有behavior questions),给纸和笔手写。
find minimun weight of a binary tree.
一个节点的weight等于左孩子的weight加右孩子的weight再加节点本身的value.
如果左孩子和右孩子都是叶子的话,这个节点的weight就是左孩子value加右孩子value加自己value。. Waral 鍗氬鏈夋洿澶氭枃绔,
每个节点里都是整数,可正可复。

再三哥的提示下想到了postorder traversal,最后时间到了写的也不一定对。基本是挂了。。。

我去找我们家静静了。我是转码农的EE狗,题还没刷好。
heroic 发表于 2015-10-10 08:33:17 | 显示全部楼层
用两次recursive来解决 避免全局变量
public class Solution {
    public TreeNode findMinimunWeight (TreeNode root) {
        root.val = calculateWeight(root);
        return getNode(root);
    }
    private int calculateWeight(root) //calculate weight of every node
    {
        if (root == null)
            return 0;
        root.val = calculateWeight(root.left) + caculateWeight(root.right);
        return root.val;
    }
    private TreeNode getNode(root) // return node with minimum weight
    {
        if (root == null)
            return null;
        if (root.left == null && root.right == null)
            return root;
        if (root.left == null)
            return root.val < getNode(root.right).val ? root : root.right;
        if (root.right == null)
            return root.val < getNode(root.left).val ? root : root.right;
        else
        {
            TreeNode left = getNode(root.left);
            TreeNode right = getNode(root.right);
            if (left.val <= right.val && left.val <= root.val)
                return left;
            if (right.val <= left.val && right.val <= root.val).1point3acres缃
                return right;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
            else
                return root;
        }
    }. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
}.1point3acres缃
. 1point 3acres 璁哄潧
补充内容 (2015-10-10 08:35):
中间calculateWeight少打了一个加号. visit 1point3acres.com for more.
root.val += calculateWeight(root.left) + caculateWeight(root.right);
回复 支持 1 反对 1

使用道具 举报

xuchen1m3fd 发表于 2015-10-10 13:30:03 | 显示全部楼层
heroic 发表于 2015-10-10 08:33
用两次recursive来解决 避免全局变量
public class Solution {
    public TreeNode findMinimunWeight ( ...
-google 1point3acres
您好层主,我觉得你的两次操作可以放在一次循环里面用bottom up的方式来做,这样代码可以更加简化,因为计算值和比较这两个工作是不会互相冲突的,贴上我的代码,如果有问题麻烦指正,谢谢!
    public TreeNode findMinWeightNode(TreeNode root) {
        return findNode(root);
    }

    // findNode返回以root为根的子树下的minWeightNode
    public TreeNode findNode(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return root;
        TreeNode left = findNode(root.left);
        TreeNode right = findNode(root.right);.1point3acres缃
        root.val = root.left.val + root.right.val + root.val;
        TreeNode result = root;
        if (left.val < result.val) result = left;
        if (right.val < result.val) result = right;
        return result;
    }


补充内容 (2015-10-10 13:30):
错了不是“循环”是“递归”。。。。。打错了

补充内容 (2015-10-12 10:40):
少了关于left和right的null处理,需要增加一下
回复 支持 1 反对 0

使用道具 举报

majiamajia 发表于 2015-10-10 04:45:43 | 显示全部楼层
那如果这个节点是叶子呢。。?他的weight就是他自己?
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-10-10 04:54:50 | 显示全部楼层
请问这道题,如果从叶子节点开始往上遍历,知道root,这样子的weight不是固定的吗?为什么minimum weight?
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 04:56:17 | 显示全部楼层
majiamajia 发表于 2015-10-10 04:45
那如果这个节点是叶子呢。。?他的weight就是他自己?

对 就是他自己的value
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 04:58:10 | 显示全部楼层
cathycat 发表于 2015-10-10 04:54-google 1point3acres
请问这道题,如果从叶子节点开始往上遍历,知道root,这样子的weight不是固定的吗?为什么minimum weight?

要返回weight最小的节点的节点本身
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-10 05:00:08 | 显示全部楼层
为什么是POST ORDER?我想着就RECURSION走好像也行呢?
回复 支持 反对

使用道具 举报

cathycat 发表于 2015-10-10 05:01:24 | 显示全部楼层
chilling 发表于 2015-10-10 04:58
要返回weight最小的节点的节点本身

懂你意思了,谢谢楼主
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 05:03:41 | 显示全部楼层
cathycat 发表于 2015-10-10 05:01
懂你意思了,谢谢楼主

不客气 good luck
回复 支持 反对

使用道具 举报

majiamajia 发表于 2015-10-10 05:15:49 | 显示全部楼层
如果是POST ORDER的话倒是不用重复计算。。但是从上往下算其实也是OK的呀= =
回复 支持 反对

使用道具 举报

yy80884676 发表于 2015-10-10 05:59:22 | 显示全部楼层
三哥是 叫 V**?
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 06:16:57 | 显示全部楼层
majiamajia 发表于 2015-10-10 05:15. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
如果是POST ORDER的话倒是不用重复计算。。但是从上往下算其实也是OK的呀= =

需要用下面的节点算上面的weight,还是得postorder吧
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 06:20:17 | 显示全部楼层
yy80884676 发表于 2015-10-10 05:59
三哥是 叫 V**?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
发音差不多是kashef
回复 支持 反对

使用道具 举报

yy80884676 发表于 2015-10-10 06:58:21 | 显示全部楼层
chilling 发表于 2015-10-10 06:20
发音差不多是kashef
. from: 1point3acres.com/bbs
我也是刚刚拿到MS的面试,上周tech fair 投的……
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
你有和其他一起面的人交流过么? 都没有behavior?
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-10 07:15:57 | 显示全部楼层
问下楼主,这道题面试官有明确要求时间和空间复杂度吗?
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 07:17:06 | 显示全部楼层
jy_121 发表于 2015-10-10 07:15
问下楼主,这道题面试官有明确要求时间和空间复杂度吗?

没有,不过也可能是我做的太慢了他没时间follow up
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 07:17:42 | 显示全部楼层
yy80884676 发表于 2015-10-10 06:58
我也是刚刚拿到MS的面试,上周tech fair 投的……

你有和其他一起面的人交流过么? 都没有behavior?

木有交流
回复 支持 反对

使用道具 举报

yy80884676 发表于 2015-10-10 07:22:40 | 显示全部楼层

能拿到面试,说明已经基本达标了呀。 楼主加油刷题! 祝好运
回复 支持 反对

使用道具 举报

 楼主| chilling 发表于 2015-10-10 07:24:29 | 显示全部楼层
yy80884676 发表于 2015-10-10 07:22
能拿到面试,说明已经基本达标了呀。 楼主加油刷题! 祝好运

good luck
回复 支持 反对

使用道具 举报

jy_121 发表于 2015-10-10 07:28:20 | 显示全部楼层
chilling 发表于 2015-10-10 07:17
没有,不过也可能是我做的太慢了他没时间follow up

遍历的话设置一个全局变量保存最小节点是否可以?要不就放个数组保存所有点的。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 01:14

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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