一亩三分地论坛

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

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

Bloomberg phone interview

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

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

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

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

x
1. longest increasing subaray
2. find the max sum on the tree. contraint is if a treenode A is selected, A.left and A.right cannot be selected.3.鏈枃鍘熷垱鑷1point3acres璁哄潧
3. class design, find top5 movers, updateprice, getprice. using a maxHeap, since we are dealing with dynamic data rather than static data.
 楼主| lianlu 发表于 2015-10-21 11:22:56 | 显示全部楼层
aiweiwei 发表于 2015-10-21 09:06
ok
get it, 终于想出来,感觉bottom up好做,类似强盗抢劫vilage,不能抢劫相邻的房子那道题目

这样可以嘛?
  1.         static int getSum(Tree t).鐣欏璁哄潧-涓浜-涓夊垎鍦
  2.         {
  3.             if (t == null) return 0;
  4.             return Math.max(helper(t), getSum(t.left) + getSum(t.right));
  5.         }
  6. . 鍥磋鎴戜滑@1point 3 acres
  7.         private static int helper(Tree root) // the max sum must include the root node
  8.         {   . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  9.             if (root == null) return 0;
  10.             int leftleft = (root.left != null ) ? getSum(root.left.left) : 0;
  11.             int leftright = (root.left != null ) ? getSum(root.left.right) : 0;
  12.             int rightleft = (root.right != null ) ? getSum(root.right.left) : 0;
  13.             int rightright = (root.right != null ) ? getSum(root.right.right) : 0;   
  14.             
  15.             return root.nodeVal + leftleft + leftright + rightleft + rightright;
  16.         }
复制代码
回复 支持 1 反对 0

使用道具 举报

pixel 发表于 2015-10-20 04:52:58 | 显示全部楼层
Thank for sharing.
Not quite understand problem 2.
1. max sum of what? all nodes in the tree? nodes in the path from root to leaf? . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
2. is possible that the value of node is negative?
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

 楼主| lianlu 发表于 2015-10-20 04:57:46 | 显示全部楼层
pixel 发表于 2015-10-20 04:52
Thank for sharing.
Not quite understand problem 2.
1. max sum of what? all nodes in the tree? nod ...

. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴not the path sum. you can add up any node you want, as long as the constraint is met.
Problem formulation:
obj: pick a set of treenodes, such that the node sum of the set is maximized.
s.t., if node a is picked in the target set, a.left and a.right can not be in the set.. Waral 鍗氬鏈夋洿澶氭枃绔,

all node are positive.
回复 支持 反对

使用道具 举报

royal_916 发表于 2015-10-21 04:06:04 | 显示全部楼层
第二题还是没太懂啊楼主  是类似于level order traversal的意思?
回复 支持 反对

使用道具 举报

 楼主| lianlu 发表于 2015-10-21 04:31:40 | 显示全部楼层
royal_916 发表于 2015-10-21 04:06. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
第二题还是没太懂啊楼主  是类似于level order traversal的意思?

大概意思就是给一Tree(所有节点都是正数),然后在tree上选取一些tree node加起来。但是一旦选择了某个点,他的left child and right child就不能选择了。
比如:
    1
2   3. From 1point 3acres bbs
4 5 6 7
一旦选择了1,就不能再选择2和3了,但是可以选择4,5,6,7 (也可能不选择,因为更下面一层可能有更大的child)。
就这个树来说,返回1+4+5+6+7..1point3acres缃

求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-21 08:19:39 | 显示全部楼层
楼主,第二题没思路,请问楼主是什么思路作的呀
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-21 08:21:20 | 显示全部楼层
不是BST,就是一般的tree,也不一定full对吧,可以是各种形状
回复 支持 反对

使用道具 举报

aiweiwei 发表于 2015-10-21 09:06:58 | 显示全部楼层
ok
get it, 终于想出来,感觉bottom up好做,类似强盗抢劫vilage,不能抢劫相邻的房子那道题目
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-1-25 07:56

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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