一亩三分地论坛

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

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

代朋友报一个G家电面面经,醉了

[复制链接] |试试Instant~ |关注本帖
liurudahai 发表于 2016-10-8 11:05:27 | 显示全部楼层 |阅读模式

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

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

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

x
我朋友今天面的,真是醉了,题是Given a binary tree, find the path which nodes sum to a given value. The path can start from and end with any nodes
做过CC150的肯定觉得这个是那上面的原题,但你仔细看CC150的解法,它的最后的答案还是从上到下的这种PATH,也就是从某个祖先(虽然不是ROOT),到某个后代节点
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
但这个面试官让我朋友做的是真正的可以从任何点开始和结束,也就是说,可以是一个节点,一直网上爬到某个祖先的然后再拐到另外一个孩子往下爬到某个后代这种路径

我朋友说他完全不会,讨论了45分钟还没讨论出正确算法,估计跪了


补充内容 (2016-10-8 11:06):
发现G家面试真是要看RP,很容易碰到各种难偏怪

评分

1

查看全部评分

本帖被以下淘专辑推荐:

  • · google|主题: 57, 订阅: 5
相位疯脸 发表于 2016-10-8 12:42:59 | 显示全部楼层
如果对复杂度没有特别要求其实写起来还好。。。对任意节点求左子为起点的所有sum,和右子为起点的所有sum,两个与root val做combination,看有没有解,然后合并两个sun的list再加root val返回作为以该点为起点的所有sum和,做一个list返回,递归调用。。。大概这样吧
回复 支持 1 反对 0

使用道具 举报

pushazhiniao 发表于 2016-10-8 11:21:18 | 显示全部楼层
感觉可以在每个节点记录从所有子孙后辈节点到当前的和 看是否有值或者和值为目标值
回复 支持 反对

使用道具 举报

pancymon 发表于 2016-10-8 12:06:25 | 显示全部楼层
这个题也有,这个是hard题 对店面来说过于难了
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-10-8 12:31:12 | 显示全部楼层
pancymon 发表于 2016-10-8 12:06. 鍥磋鎴戜滑@1point 3 acres
这个题也有,这个是hard题 对店面来说过于难了
. 1point3acres.com/bbs
哪有答案?
回复 支持 反对

使用道具 举报

 楼主| liurudahai 发表于 2016-10-8 12:31:35 | 显示全部楼层
pancymon 发表于 2016-10-8 12:06. more info on 1point3acres.com
这个题也有,这个是hard题 对店面来说过于难了

我看LC上有一个任意点起,任意点结束求最大SUM的,但没有说等于特定SUM的
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-10-8 12:39:54 | 显示全部楼层
最优解不会的话,暴力穷举总应该会写吧。
回复 支持 反对

使用道具 举报

zyoppy008 发表于 2016-10-8 12:45:47 | 显示全部楼层
三种情况 左子树有 右子树有 不然就肯定经过当前root 对从左节点的出发所以可能的path找右子树有没有这样的对应的值的path 这样好像复杂度挺高 但是如果有规定都是positive可以提前终止就比较好一点 感觉还是太笨拙了这方法
回复 支持 反对

使用道具 举报

dexter 发表于 2016-10-8 14:00:22 | 显示全部楼层
liurudahai 发表于 2016-10-8 12:31
我看LC上有一个任意点起,任意点结束求最大SUM的,但没有说等于特定SUM的
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
对的.求最大而且没有说打印path...假如只是找存在不存在也差不多.但是要打出来存在的那个路径...怎么存呢?
回复 支持 反对

使用道具 举报

相位疯脸 发表于 2016-10-8 14:19:58 | 显示全部楼层
dexter 发表于 2016-10-8 14:00
对的.求最大而且没有说打印path...假如只是找存在不存在也差不多.但是要打出来存在的那个路径...怎么存呢 ...

能判断存不存在解就能找到解,只不过需要消耗更大的空间复杂度罢了,理论上任何题如果对时间,空间复杂度没要求都能暴力解,只不过写起来麻烦一些,这道题也一样。面试官 出这个题要么就是成心黑人,要么就是不要求bug free 完美解,而更看重思路,但是如果面试时一点思路都没有,那确实差些火候。挂了也说不出什么。
回复 支持 反对

使用道具 举报

zhangyanuuuuu 发表于 2016-10-8 14:23:53 | 显示全部楼层
感觉上可以用floyd-warshall去做,tree就相当于graph,每个点到另外点只有一条路径
回复 支持 反对

使用道具 举报

johnjavabean 发表于 2016-10-8 15:11:27 | 显示全部楼层
如果能重构树把树重构成无向图解就行了....dfs....
回复 支持 反对

使用道具 举报

MobileGeek 发表于 2016-10-8 21:29:26 | 显示全部楼层
这个要用Segment tree吧
回复 支持 反对

使用道具 举报

配刀老鼠 发表于 2016-10-8 22:13:13 | 显示全部楼层
楼主 这题跟leetcode 124. Binary Tree Maximum Path Sum很类似啊 貌似还简单了点 但是124是hard 所以没看过思路的估计很困难
回复 支持 反对

使用道具 举报

wzy1991527 发表于 2016-10-8 22:21:08 | 显示全部楼层
原题 wrapper class就能解决的
回复 支持 反对

使用道具 举报

edyyy 发表于 2016-10-8 22:29:45 | 显示全部楼层
这么简单的题,做不好自己好好回去刷题
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-10-8 22:34:22 | 显示全部楼层
配刀老鼠 发表于 2016-10-8 22:13
楼主 这题跟leetcode 124. Binary Tree Maximum Path Sum很类似啊 貌似还简单了点 但是124是hard 所以没看 ...

maximun sum更简单
回复 支持 反对

使用道具 举报

yhatl 发表于 2016-10-9 01:09:40 | 显示全部楼层
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}.鏈枃鍘熷垱鑷1point3acres璁哄潧
};


multimap<int,vector<TreeNode*> > allPath(TreeNode* root,int target,vector<vector<TreeNode*> >& result){
    multimap<int,vector<TreeNode*> > left_sum,right_sum,root_sum;
    if(root->left)left_sum=allPath(root->left,target,result);-google 1point3acres
    if(root->right)right_sum=allPath(root->right,target,result);
   
    if(root->val==target)result.push_back(vector<TreeNode*>(1,root));. from: 1point3acres.com/bbs
    root_sum.emplace(root->val,vector<TreeNode*>({root}));
    auto it_left=left_sum.begin();
    auto it_right=right_sum.rbegin();
   
    while(it_left!=left_sum.end() && it_right!=right_sum.rend()){
        while(it_right!=right_sum.rend() && it_left->first+root->val+it_right->first>target)it_right++;
        if(it_right==right_sum.rend())break;
        if(it_left->first+root->val+it_right->first==target){
            vector<TreeNode*> tmp(it_left->second);
            tmp.push_back(root);. from: 1point3acres.com/bbs
            tmp.insert(tmp.end(),it_right->second.rbegin(),it_right->second.rend());
            result.push_back(tmp);
        }
        it_left++;
    }
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴   
    for(auto p:left_sum){
        p.second.push_back(root);
        root_sum.emplace(root->val+p.first,p.second);
        if(root->val+p.first==target)result.push_back(p.second);
    }
    for(auto p:right_sum){
        p.second.push_back(root);
        root_sum.emplace(root->val+p.first,p.second);
        if(root->val+p.first==target)result.push_back(p.second);
    }. Waral 鍗氬鏈夋洿澶氭枃绔,
    return root_sum;
}

vector<vector<TreeNode*> > pathSum(TreeNode* root,int target){.1point3acres缃
    vector<vector<TreeNode*> > result;
    if(!root)return result;
    multimap<int,vector<TreeNode*> > pathes;. from: 1point3acres.com/bbs
   
    allPath(root,target,result);
    return result;. visit 1point3acres.com for more.
}
回复 支持 反对

使用道具 举报

jy_121 发表于 2016-10-16 11:05:53 | 显示全部楼层
edyyy 发表于 2016-10-8 22:29
这么简单的题,做不好自己好好回去刷题

求大神给个解法
回复 支持 反对

使用道具 举报

zzgzzm 发表于 2016-10-23 13:01:43 | 显示全部楼层
这题跟Leetcode 124. Binary Tree Maximum Path Sum很类似,稍有不同。主要思路就是用post-order traversal从leaf node入手来建立从当前node到任意descendent的路径以及总长(sum of value)。因为即使相同总长的路径的nodes也可以不同,所以可以用unordered_multimap<int,vector<Node*>>存储从总长映射到路node的array.
算法概述:
1. 先找出left subtree中所有target sum paths;
2. 再找出right subtree中所有target sum paths;
3. 最后找必须经过root的target sum paths。 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
4. 合并所有结果到vector<vector<Node*>>中。. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
核心部分其实就是“3”:如何计算经过某个node的所有target sum paths. 这个很容易利用post-order traversal中已经计算的node->left和node->right的所有到各自任意descendant不同长度的paths来完成。具体code如下,详细注释(没有debug, 但大体算法如下) 。“allPaths”是主函数
  1. // Tree node
  2. struct Node {. From 1point 3acres bbs
  3.   int val;
  4.   Node* left, *right;
  5.   // paths: all paths from this node to any descendant
  6.   // multimap: path sum -> path nodes (including single this node path)
  7.   unordered_multimap<int,vector<Node*>> paths;. 1point3acres.com/bbs
  8.   Node(int v):val(v),left(NULL),right(NULL){}
  9. };

  10. // result to store all paths with target sum
  11. vector<vector<Node*>> res;

  12. // calculate all paths with target sum
  13. // do post-order traversal
  14. vector<vector<Node*>> allPaths(Node* r, int t) {
  15.   if (!r) return res;
  16.   // calculate target paths in left trees. Waral 鍗氬鏈夋洿澶氭枃绔,
  17.   auto lres = allPaths(r->left, t);
  18.   // calculate target paths in right trees
  19.   auto rres = allPaths(r->right, t);
  20.   // calculate target paths passing root
  21.   pathsThroughRoot(r, t);
  22.   // combine all paths into result
  23.   res.insert(lres.begin(), lres.end());. 1point 3acres 璁哄潧
  24.   res.insert(rres.begin(), rres.end());
  25.   return res;
  26. }. from: 1point3acres.com/bbs

  27. // calculate all paths with target sum that pass through node "r"
  28. void pathsThroughRoot(Node* r, int t) {
  29.   if (!r) return;
  30.   auto rl = r->left, rr = r->right; int rv = r->val;
  31.   // if "r" is a leaf, set the only trivial path
  32.   // and push to result if matching target sum
  33.   if (!rl && !rr) {
  34.     r->paths = {{rv, {r}}};
  35.     if (rv == t) res.push_back({r});-google 1point3acres
  36.     return;
  37.   }
  38.   // lpaths: all paths from node "r" to any left descendent (including self)
  39.   unordered_multimap<int,vector<Node*>> lpaths = {{rv, {r}}},
  40.     rpaths = {{rv, {r}}};
  41.   if (rl). 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  42.     for (auto& p:rl->paths) {
  43.       vector<Node*> path = {r};. 鍥磋鎴戜滑@1point 3 acres
  44.       path.insert(path.end(),p.second.begin(),p.second.end());. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  45.       lpath.emplace(rv+p.first,path);
  46.     }  . more info on 1point3acres.com
  47.   // rpaths: all paths from node "r" to any right descendent (including self)   
  48.   if (rr)
  49.     for (auto& p:rr->paths) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  50.       vector<Node*> path = {r};
  51.       path.insert(path.end(),p.second.begin(),p.second.end());
  52.       rpath.emplace(rv+p.first,path);
  53.     }  
  54.   // combine lpaths and rpath to get r->paths (remove duplicated {r})
  55.   r->paths = lpaths;
  56.   r->paths.insert(r->paths.end(),rpath.begin()+1,rpath.end());
  57.   
  58.   // push paths with target sum to result if there is any
  59.   for (auto& lp:lpaths) {
  60.     for (auto& rp:rpaths) {
  61.       if (lp.first+rp.first == t+rv) { // node "r" is duplicated
  62.         // build path from left tree going through "r" to right tree
  63.         vector<Node*> path = lp.second;
  64.         reverse(path.begin(), path.end());
  65.         path.insert(path.end(), rp.begin()+1, rp.end());. 鍥磋鎴戜滑@1point 3 acres
  66.         res.push_back(path);
  67.       }      
  68.     }  
  69.   }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  70. }
复制代码

补充内容 (2016-10-23 13:15):. visit 1point3acres.com for more.
"如何计算经过某个node的所有target sum paths"是指这个node一定是该路径所有nodes的ancestor。这样路径就以该node分成了3部分,使总和match到target sum.
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 08:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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