介绍一下Uber:tech stack和各个大组的情况

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 1731|回复: 13
收起左侧

[CareerCup] 【第三轮】7.14-7.20 CareerCup 4.9

[复制链接] |试试Instant~ |关注本帖
wrj5518 发表于 2014-7-15 08:35:36 | 显示全部楼层 |阅读模式

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

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

x
4.9 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum to a given value. The path does not need to start or end at the root or a leaf.

回复解法可以按照以下格式来
【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------optional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】


Notice:
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子,除了贴解法,欢迎讨论,集思广益
4、任何未尽之处,欢迎回报名帖提问,我会进一步作出修改。

grassgigi 发表于 2014-7-15 10:19:38 | 显示全部楼层
【解题思路】
Find all paths start from root node and ends anywhere
Then recursively call this function on both its left and right subtree

【时间复杂度】
O(N^2) in worst case, O(NlgN) on average

【空间复杂度】
regardless of recursion depth, O(lgN) for node list to represent the path

【gist link】
https://gist.github.com/chrislukkk/be1ffddf2aff327f33a8
回复 支持 反对

使用道具 举报

全球28万学生4.7分推荐
圆梦梦剧场 发表于 2014-7-15 11:29:55 | 显示全部楼层
【解题思路】
Traverse every node by level order
exam all paths which terminate at this node
if the sum of the path equals the target value, add it to the final results or print it out.


【时间复杂度】
O(n * h)

【空间复杂度】
O(h)



【gist link】
https://gist.github.com/happyWinner/da099e6d43cecb258bc2

回复 支持 反对

使用道具 举报

pyemma 发表于 2014-7-15 11:40:11 | 显示全部楼层
【解题思路】Travel the tree as well as save the node that exist on the path from the root to the current node, calculate the sum from the current node to previous nodes to see if there exist a valid path
【时间复杂度】O(n*h)
【空间复杂度】O(h)
【gist link】
https://gist.github.com/pyemma/44fafb573aaca8a1b331
---------------OPTional,如果觉得test case比较好,欢迎写出来分享----------------------
【test case】
回复 支持 反对

使用道具 举报

jyh橘子 发表于 2014-7-18 07:14:33 | 显示全部楼层
【解题思路】For every node, record the path from root to the node. With the path, we need to find all subpaths that end with this node and sum to the target.
【时间复杂度】O(n*logn)
【空间复杂度】O(logn)
【gist link】https://gist.github.com/jyhjuzi/6e9670d8ab016343cc07
回复 支持 反对

使用道具 举报

renli3000 发表于 2014-7-18 11:56:58 | 显示全部楼层
本帖最后由 renli3000 于 2014-7-18 12:29 编辑

【解题思路】这道题一开始我考虑吧所有path输入到list里(leetcode类似方法),然后再逐一分析subpath,结果写了半天代码跑出来一看,找到的subpath有重复难以去除。。。
后来一气之下想出了这个方法,我叫它“sumTree”,即这个tree的每一个node的值都是它path上所有node之和
通过post-order就可以把原来的树变成sumTree,接下来只需从node1的subtree中第归搜索到 所有值为 node1.value + sum 的node3,这样从node2 - node3之间的path就是我们要找的,置于具体值,用后一个sum减前一个sum即可,然后把他们塞进list<E>
【时间复杂度】O(n^2)
【空间复杂度】O(n)
【gist link】https://gist.github.com/Noahsark/6449aa223777978e32eb
补充: 看了楼上各位的思路,果然还是倒着找比较快啊...智商面壁去了
回复 支持 反对

使用道具 举报

donnice 发表于 2014-7-19 04:18:12 | 显示全部楼层
【解题思路】
遍历每个点和其parent,在sum小于规定值n前把值都放心list中,当sum等于n时就打印列表,继续下个点。若sum大于n,则sum归零,表清空,继续下个点。总之就是倒着找,顺便LS的思路其实和我差不多
【时间复杂度】
O(N^2)(worst)
【空间复杂度】
O(n)
【gist link】
https://github.com/donnice/donnice/blob/master/Q4_9
【Test】
                     5                                                               
                 2                  8                              
           1          4       7                                          
                 3         6   
找14
回复 支持 反对

使用道具 举报

ivycheung1208 发表于 2014-7-19 09:25:08 | 显示全部楼层
【解题思路】
keep track of the path from root for each node, search its path to see whether it completes a path with the given sum.
【时间复杂度】
O(NlogN)
【空间复杂度】
O(logN)
【gist link】
https://gist.github.com/c522bed2cfbac56bce1e
【test case】
consider following cases:
no match (including sum = 0)
unique match
multiple match
回复 支持 反对

使用道具 举报

林微熙 发表于 2014-7-19 09:56:00 | 显示全部楼层
【解题思路】recurse each node from root to n, adds the nodes along path in reverse order from n to root.
【时间复杂度】o(nlogn)
【空间复杂度】o(logn)
【gist link】https://gist.github.com/hilda8519/b1c2e0971ddffbaf0597
回复 支持 反对

使用道具 举报

tonygxxx1212 发表于 2014-7-19 23:29:56 | 显示全部楼层
【解题思路】注释比较详尽,start from root 和 start form anywhere 都写了, 区别就是是否把 if condition从 for循环 拿出来。其他递归结构都一样。
【时间复杂度】o(nlogn) for start from anywhere, O(logn) for start from root
【空间复杂度】o(logn) 用数组来记录,subsrcript用的是节点的level
【gist link】https://gist.github.com/xun-gong/cf088833764657b0a7d8
回复 支持 反对

使用道具 举报

bitcpf 发表于 2014-7-22 01:18:59 | 显示全部楼层
【解题思路】recursion, if current node key equals to the remaining sum value, return, else check the left and right subtree
second recursion to check each node as root

【时间复杂度】
O(N^2)
【空间复杂度】
O(lgN) for node list to represent the path

【gist link】
https://gist.github.com/bitcpf/8beb7c1e035c08461596
回复 支持 反对

使用道具 举报

wilbert 发表于 2014-7-23 09:09:29 | 显示全部楼层
【解题思路】
recursively tree traversal, and save the path in the array, calculate the sum from that node, and print the path if equals to target.
【时间复杂度】
O(N*h) h is the height of the tree
【空间复杂度】
O(h)
【gist link】
https://gist.github.com/iwilbert/b42b689943beb2a1d3df
回复 支持 反对

使用道具 举报

兰橘清檬 发表于 2014-8-14 04:26:55 | 显示全部楼层
【解题思路】
DFS recursion, check if the current node is the end of the valid path
【时间复杂度】
   O(nlog(n))
   if balanced tree; or O(n*h)
【空间复杂度】
  O(h)
【gist link】
  https://gist.github.com/JoyceeLee/7a52bbc5937fc1d400c1
回复 支持 反对

使用道具 举报

yyz20002008 发表于 2014-12-16 07:00:31 | 显示全部楼层
请问这道题要不要考虑root作为中间节点的的情况 比如 求sum=21,root=7,root.left=10,root.right=4,返回10,7,4 or 7 10 4作为一个结果。书上只考虑了root左边或右边的从上到下任意点开始,但start anywhere理论上不得包含从左节点到右节点的情况吗?
多谢指教了
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-25 00:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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