一亩三分地论坛

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

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

Google电面面经

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

2015(4-6月) 码农类 博士 全职@Google - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
刚刚电面完,面试官感觉是个欧洲大叔,大叔人很好,我那题回答得是一路磕磕碰碰,
基础问题也回答得不好,大叔还是一直给提示,并且超时了还让我问问题,据说狗家很. 1point 3acres 璁哄潧
多面试官时间一到直接挂电话。。。

题目是leetcode上BinaryTreeMaximumPathSum的变形题,path里不能有直接相接的node。

希望对大家有帮助~

评分

4

查看全部评分

Williamslg 发表于 2015-8-12 07:12:26 | 显示全部楼层
根据23楼的思路 写了一下,不过判断global max的各种情况比较乱,如果node value都是negative的情况会返回0
public class BTMaxPathSum {
    private static class TreeNode {
        private int val;. 1point3acres.com/bbs
        private TreeNode left, right;
        public TreeNode(int value) {
            val = value;
        }
    }
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴   
    private int max = Integer.MIN_VALUE;
    -google 1point3acres
    private class Result {
        private int has;
        private int notHas;
        public Result(int has, int not) {
            this.has = has;
            this.notHas = not;
        }
    }
   
    public int maxPathSum(TreeNode root) {
        this.max = Integer.MIN_VALUE;
        helper(root);
        return max;. 1point 3acres 璁哄潧
    }
    .1point3acres缃
    private Result helper(TreeNode x) {
        if (x == null) return new Result(0, 0);. from: 1point3acres.com/bbs
        Result left = helper(x.left);
        Result right = helper(x.right);
        
        int sum = x.val;
        if (left.notHas > 0) sum += left.notHas;
        if (right.notHas > 0) sum += right.notHas;
        max = Math.max(max, sum);. from: 1point3acres.com/bbs
        
        sum = 0;
        sum += Math.max(0, Math.max(left.has, left.notHas));
        sum += Math.max(0, Math.max(right.has, right.notHas));
        max = Math.max(max, sum);
        
        int has = x.val + Math.max(0, Math.max(left.notHas, right.notHas));
        int notHas = Math.max(left.has, left.notHas);
        notHas = Math.max(notHas, Math.max(right.has, right.notHas));
        notHas = Math.max(0, notHas);
        
        return new Result(has, notHas);
    }
}
回复 支持 4 反对 0

使用道具 举报

小桶 发表于 2015-5-22 04:18:36 | 显示全部楼层
感谢LZ发题!还是不太理解题意。请问在计算path的时候,是不是还是常规的累加,只不过最后返回的时候,是返回这条path上不相邻的所有点的最大组合情况?还是说path自身的值仅包含间隔的元素,这样感觉很复杂啊。。

补充内容 (2015-5-21 15:29):
好像明白题意了,有点儿DP的意思,每个node返回两个值,一个是包含自己的最大path值,一个是不包含自己的最大path值,同时维护一个全局变量,存储以当前结点为根的树的最大path值。
回复 支持 3 反对 0

使用道具 举报

77777777 发表于 2015-6-3 05:15:08 | 显示全部楼层
我的理解是这样的,楼主你看对不对夯
就是这题是binaryTreeMaximumPathSum和 HouseRobber的结合体 找到最大得path,然后得到最大的sum
回复 支持 2 反对 0

使用道具 举报

jasusy 发表于 2015-7-24 11:13:57 | 显示全部楼层
小桶 发表于 2015-5-21 13:33
LZ看我之前那个回复的补充,是不是用类似DP的方法?

不用dp吧,只要把之前helper()函数(返还单一路径最长,left or right 那个)改成返回两个数据int[],一个是算入这个root value的单一路径最大值和不算人root.val max sum, 就可以了。
回复 支持 1 反对 0

使用道具 举报

xdrealmadrid 发表于 2015-5-22 00:01:08 | 显示全部楼层
lz是怎么做的 跟lc那题一样吗 往上传的数据改成int[]?
回复 支持 1 反对 0

使用道具 举报

xanadulord 发表于 2015-5-21 13:09:18 | 显示全部楼层
有点没看懂,lz能再说得详细点吗,多谢啦
回复 支持 反对

使用道具 举报

奔跑小子2099 发表于 2015-5-21 15:05:37 | 显示全部楼层
都有什么基础问题?
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-5-21 21:08:43 | 显示全部楼层
xanadulord 发表于 2015-5-21 13:09
有点没看懂,lz能再说得详细点吗,多谢啦

呃,看来我描述得确实不太清楚,罪过罪过。。。
不好意思,感觉说得很不清楚,晕倒一片人。。。
这么想吧,你还是找pathsum,但是这个用来求和的node不能相邻。例如说

            1  . more info on 1point3acres.com
           / \
          2  3
         / \
        1  8. from: 1point3acres.com/bbs

你就可以选择8-2-1-3这条path,求和用8+3=11最大。
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-5-21 21:09:53 | 显示全部楼层
奔跑小子2099 发表于 2015-5-21 15:05
都有什么基础问题?
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
没有专门问基础问题,是在写code的过程中问题有关code里面的一些数据结构的问题,果然数据结构还是要好好准备啊~~
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-5-22 04:23:36 | 显示全部楼层
xdrealmadrid 发表于 2015-5-22 00:01
lz是怎么做的 跟lc那题一样吗 往上传的数据改成int[]?
.1point3acres缃
我当时给的解法是不断往下传,用一个全局变量纪录最大和,然后判断选择的路径。
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-5-22 04:24:43 | 显示全部楼层
小桶 发表于 2015-5-22 04:18
感谢LZ发题!还是不太理解题意。请问在计算path的时候,是不是还是常规的累加,只不过最后返回的时候,是返 ...

不用返回path本身,只要返回最大和就行~
回复 支持 反对

使用道具 举报

小桶 发表于 2015-5-22 05:33:31 | 显示全部楼层
dreamcloud 发表于 2015-5-21 14:24. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
不用返回path本身,只要返回最大和就行~

LZ看我之前那个回复的补充,是不是用类似DP的方法?
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-5-22 05:40:31 | 显示全部楼层
小桶 发表于 2015-5-22 05:33
LZ看我之前那个回复的补充,是不是用类似DP的方法?
. from: 1point3acres.com/bbs
对的对的,我就是这么想的~
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-1 01:29:13 | 显示全部楼层
不太理解题意? 根据提供的例子  是任一条path的头尾和(去除掉path只有两个node的情形) , 找出path头尾和是最大的状况?
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-6-1 02:53:04 | 显示全部楼层
到底是在说什么啊?
给别人讲问题的时候能不能站在一个小白的视角去叙述一个事情?
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-6-1 03:32:37 | 显示全部楼层
jiebour 发表于 2015-6-1 02:53
到底是在说什么啊?
给别人讲问题的时候能不能站在一个小白的视角去叙述一个事情?

不好意思啊,我第一次发面经,不太清楚规矩,先假定了大家刷过题或者至少知道leetcode。。。
题目大意是在二叉树中找出一条路径使得这条路径中不相邻的node的总和最大,只需要返回最大总和即可。
不知道这个题目阐述得合不合您意?
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-6-1 03:33:15 | 显示全部楼层
say543 发表于 2015-6-1 01:29
不太理解题意? 根据提供的例子  是任一条path的头尾和(去除掉path只有两个node的情形) , 找出path头尾和是 ...

我在楼下下答复了~~
回复 支持 反对

使用道具 举报

say543 发表于 2015-6-1 12:09:55 | 显示全部楼层
感谢LZ回复   问一下   假设有一条path 是8 3 4 3 1 最大的sum 是8+4 or 8+1 or 8+4+1? 中间的node path sum有算吗?
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-6-2 22:18:00 | 显示全部楼层
嗯,如果是一条path上的点,中间的node是算的,只要不相邻就行~~
回复 支持 反对

使用道具 举报

 楼主| dreamcloud 发表于 2015-6-3 05:22:48 | 显示全部楼层
77777777 发表于 2015-6-3 05:15 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
我的理解是这样的,楼主你看对不对夯
就是这题是binaryTreeMaximumPathSum和 HouseRobber的结合体 找到最 ...

嗯呐,我觉得是这样的~~
回复 支持 反对

使用道具 举报

aliciaru 发表于 2015-6-3 10:51:40 | 显示全部楼层
初来乍到! 赞经验中。。。多谢分享。。。攒大米。。。
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-8 14:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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