一亩三分地论坛

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

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

Bloomberg 电面 一道题

[复制链接] |试试Instant~ |关注本帖
zsz1990ustc 发表于 2016-4-9 07:00:59 | 显示全部楼层 |阅读模式

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

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

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

x


3点开始的,像是白人小哥。上来介绍简历的project,然后开始coding.. more info on 1point3acres.com
-google 1point3acres
就一道题:计算每个二叉树的从root到每个叶子的每条path的sum,找sum最小的那个path,输出这个path。


很简单吧。DFS遍历一下,用一个int叫min的来记录一下最小sum,minPath来记录最小的那个path就行了。

当时楼主很晕,居然把 min 放在了 dfs的参数中,明明必须要是全局变量才 work啊。。

然后对方说怎么优化,我说没法优化啊,dfs嘛,O(n)复杂度啊,没法再少了。

结果对方说,可以再遍历中,若发现当前 sum已经大于min了,那么立即停止向下的遍历。恩,有道理啊。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
然后对方说,这样没有问题吧。我说如果没有负数的话,就没问题。

对方又问我怎么保证没有负数,我说在 TreeNode 的 constructor里写上. 鍥磋鎴戜滑@1point 3 acres

public TreeNode(int val){
       this.val = Math.abs(val);
}

对方说能不能写个 throw exception。我当时就懵了,大概意思知道,忘了syntax。。。然后对方帮我写上去了。。. from: 1point3acres.com/bbs

对方带着我一步步走我的程序,哎,时间过得很快。一道题做完就到时间了。。

被这么简单的一道题虐了。。希望能去onsite啊。。求人品~~


评分

5

查看全部评分

陈润鹏 发表于 2016-7-15 22:23:34 | 显示全部楼层
为什么呀 感觉 你们做的好奇怪呀 题目难道不是这样?
  1. package bloomberg;
  2. .鐣欏璁哄潧-涓浜-涓夊垎鍦
  3. import java.util.*;

  4. public class MinuSumPath{. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  5.         public int findMin(TreeNode root) {
  6.                 int left = findMin(root.left);. 1point 3acres 璁哄潧
  7.                 int right  = findMin(root.right);
  8.                 return Math.min(left,right)+root.val;
  9.         }.1point3acres缃
  10. }
复制代码

补充内容 (2016-7-15 22:24):
少了一个空 集判断
回复 支持 0 反对 1

使用道具 举报

gwygw 发表于 2016-4-9 23:31:16 | 显示全部楼层
昨天被BB又放鸽子了!
回复 支持 反对

使用道具 举报

lela900900 发表于 2016-4-10 05:52:23 | 显示全部楼层
谢谢lz 很详细的面经啊 lz好人!
我刚写了遍,跑test也是折腾了好久才想起来min和path要放全局变量啊啊,要不递归返回的时候都被覆盖掉了 T_T
. 1point3acres.com/bbs
感觉bb 考的不难,但都很细
回复 支持 反对

使用道具 举报

jiaozhu200601 发表于 2016-8-28 03:46:58 | 显示全部楼层
感谢楼主分享,请问一下优化的具体想法,如果用DFS的话,如何在遍历的过程中就确定一个min, 并且确保在sum大于min的时候立刻停止遍历,我尝试实现这一细节操作但是发现有难度,谢谢,给你加米!
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-8-30 14:36:19 | 显示全部楼层
jiaozhu200601 发表于 2016-8-28 03:46
感谢楼主分享,请问一下优化的具体想法,如果用DFS的话,如何在遍历的过程中就确定一个min, 并且确保在sum ...

min是全局变量啊,当然就一个min。停止往下遍历node.left,node.right,直接return啊,这不是DFS基本功么。
回复 支持 反对

使用道具 举报

chaosMonkey 发表于 2016-8-30 15:38:38 | 显示全部楼层
dfs中不一定要全局变量,像记录遍历路径的变量以及最后的min结果都可以利用引用的方式放到参数中。也能起到和全局变量类似的效果。
回复 支持 反对

使用道具 举报

jiaozhu200601 发表于 2016-8-31 02:20:34 | 显示全部楼层
zsz1990ustc 发表于 2016-8-30 14:36. from: 1point3acres.com/bbs
min是全局变量啊,当然就一个min。停止往下遍历node.left,node.right,直接return啊,这不是DFS基本功么 ...

是的,我的疑惑是,如果是一左一右两个子树,假如你已经知道了一个目前的min是左子树的sum,如何在不对右子树遍历的情况下知道是否右子树的sum比左子树小,我们应该只能判断右子树根节点大小吧,如果右子树根节点已经大于目前min就停止,而无法比较min和右子树的sum 在不遍历整个右子树的情况下,谢谢。
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-9-2 13:45:38 | 显示全部楼层
jiaozhu200601 发表于 2016-8-31 02:20
是的,我的疑惑是,如果是一左一右两个子树,假如你已经知道了一个目前的min是左子树的sum,如何在不对右 ...

你的sum是描述你 本节点 上面走过的的路径,而不是本节点的子树的路径吧。怎么会知道子树的sum呢。。

if (sum < min) {
  DFS(左子树);
  DFS(右子树);
}
回复 支持 反对

使用道具 举报

 楼主| zsz1990ustc 发表于 2016-9-2 13:46:19 | 显示全部楼层
chaosMonkey 发表于 2016-8-30 15:38
dfs中不一定要全局变量,像记录遍历路径的变量以及最后的min结果都可以利用引用的方式放到参数中。也能起到 ...

赞!是的!
回复 支持 反对

使用道具 举报

BlackPen 发表于 2016-9-7 15:40:56 | 显示全部楼层
非常感谢。那么楼主后来onsite了么?offer了么?真心希望你能得啊!
回复 支持 反对

使用道具 举报

xuqicx23 发表于 2016-9-27 10:46:49 | 显示全部楼层
陈润鹏 发表于 2016-7-15 22:23
为什么呀 感觉 你们做的好奇怪呀 题目难道不是这样?
. 1point 3acres 璁哄潧
补充内容 (2016-7-15 22:24):
.1point3acres缃
你要输出path,不是只找个最小值
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 03:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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