一亩三分地论坛

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

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

bloomberg 面经。。另外想请教下大家这题解法

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

2015(10-12月) 码农类 本科 实习@Bloomberg - 校园招聘会 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
谈了10分钟project直接来了这题。。给一个binary tree。。 找到所有的paths that sum to a certain value..比如说:-google 1point3acres
                 5
              /   \
            1       2
           / \        \
         2    5       6


.1point3acres缃
然后给一个value 8,那么paths 有  [5,1,2], [1,5,2], [2,1,5], [2,6]..  就是说path可以从任何地方开始。
最初感觉有点像leetcode 那个binary tree maximum path sum。。。做着做着感觉麻烦在于有些paths 可以不包含root。。怎样获得这些不包含root的path。。
我的code大概是这样。。先考虑不包含root的情况。。那么直接recursively call the function on left/right subtree。。 如果包含root,那么有分两种:1. 从root开始往左或右走 2. 从左边开始,走到root, 在走道右边:
  1. public class PathSumToTarget {
  2.     private List<LinkedList<Integer>> findPathsToSum(TreeNode root, List<List<Integer>> paths,  LinkedList<Integer> path, int target, int totalsum) {
  3.         List<LinkedList<Integer>> childpaths = new ArrayList<LinkedList<Integer>>();. visit 1point3acres.com for more.
  4.         if(root != null){
  5.             // does not include root:. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.             findPathsToSum(root.left, paths, path, target, totalsum);
  7.             findPathsToSum(root.right, paths, path, target, totalsum);
  8.             path.addFirst(root.val);
  9.             if(target == root.val){
  10.                 paths.add((LinkedList<Integer>)path.clone());. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  11.             }else if(target>root.val){
  12.                 // this handles the path from current node to a child in either left or right subtree
  13.                 List<LinkedList<Integer>> leftpaths = findPathsToSum(root.left, paths, path, target-root.val, totalsum);
  14.                 List<LinkedList<Integer>> rightpaths = findPathsToSum(root.right, paths, path, target-root.val, totalsum);
  15.                 for(LinkedList<Integer> leftpath : leftpaths){
  16.                     leftpath.addFirst(root.val);. visit 1point3acres.com for more.
  17.                     childpaths.add(leftpath);
  18.                 }
  19.                 for(LinkedList<Integer> rightpath : rightpaths){. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  20.                     rightpath.addFirst(root.val);
  21.                     childpaths.add(rightpath);
  22.                 }
  23.                 // this handles the path from a node in left subtree to root, and to right subtree
  24.                 if(target!=totalsum){
  25.                     int childrenSum = totalsum - root.val;
  26.                     for(int i=0; i<=childrenSum; i++){
  27.                         List<LinkedList<Integer>> lpaths = findPathsToSum(root.left, paths, path, i, totalsum);
  28.                         List<LinkedList<Integer>> rpaths = findPathsToSum(root.right, paths, path, childrenSum-i, totalsum);
  29.                         for(LinkedList<Integer> l : lpaths) {
  30.                             for(LinkedList<Integer> r : rpaths) {
  31.                                 LinkedList<Integer> childpath = new LinkedList<Integer>();. visit 1point3acres.com for more.
  32.                                 Collections.reverse(r);
  33.                                 childpath.addAll(l);
  34.                                 childpath.add(root.val);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                                 childpath.addAll(r);
  36.                                 paths.add(childpath);. 1point 3acres 璁哄潧
  37.                             }
  38.                         }-google 1point3acres
  39.                     }. from: 1point3acres.com/bbs
  40.                 }
  41. . visit 1point3acres.com for more.
  42.             }else{. 1point 3acres 璁哄潧
  43.                 //do nothing
  44.             }
  45.             path.pollFirst();
  46.         }
  47.         return childpaths;
  48.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  49.     public List<List<Integer>> findPaths(TreeNode root, int target) {
  50.         ArrayList<List<Integer>> paths = new ArrayList<List<Integer>>();
  51.         LinkedList<Integer> path = new LinkedList<Integer>();. 1point3acres.com/bbs
  52.         findPathsToSum(root, paths, path, target, target);
  53.         return paths;
  54.     }
复制代码
最后越写越糊涂。。最后面试官提示这种方法会有很多重复。。问题在于没有decouple里面的4个recursive call。。。 大家对这题有什么解法?


saklyn 发表于 2015-11-19 12:16:22 | 显示全部楼层
刚才在书上找到了手打一遍
  1. void findSum(TreeNode node, int sum, int[] path, int level){
  2.      if(node == null) return;. from: 1point3acres.com/bbs
  3.    
  4.     path[level] = node.data;

  5.     int i = 0;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  6.     for(int i = level; i >= 0;i--){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  7.        t += path[i];
  8.        if (t == sum) {.1point3acres缃
  9.           print(path, i, level);
  10.        }
  11.     }
  12.   
  13.    findSum(node.left, sum, path, level +1 );
  14.    findSum(node.right, sume, path, level +1);

  15.   path[level] = Integer.MIN_VALUE;
  16.   }

  17. void findSum(TreeNode node, int sum){
  18.     int depth = depth(node);
  19.     int path= new int[depth];. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.     findSum(node, sum, path, 0);
  21. }. more info on 1point3acres.com

  22. void print(int[] path, int start, int end){
  23.     for(in i = start, i <= end; i++)
  24.         System.out.println(path[i] + "");
  25. }

  26. int depth(TreeNode node){
  27.     if(node == null){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  28.        return 0;
  29.    }
  30.    else {
  31.      return 1 + Math.max(depth(node.left), depth(node.right));
  32.    }
  33. }
复制代码
回复 支持 0 反对 1

使用道具 举报

saklyn 发表于 2015-11-19 12:07:07 | 显示全部楼层
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。
回复 支持 反对

使用道具 举报

albee_fighting 发表于 2015-11-19 13:27:46 | 显示全部楼层
saklyn 发表于 2015-11-19 12:16-google 1point3acres
刚才在书上找到了手打一遍

                 5
              /   \
            1       2
It seems that this situation is not covered by the code.
回复 支持 反对

使用道具 举报

kimi81017 发表于 2015-11-19 13:32:35 | 显示全部楼层
saklyn 发表于 2015-11-19 12:16
刚才在书上找到了手打一遍
. 1point3acres.com/bbs
跑了一下,好像不是楼主的题的答案啊
回复 支持 反对

使用道具 举报

 楼主| junjunkate 发表于 2015-11-20 00:31:55 | 显示全部楼层
saklyn 发表于 2015-11-19 12:07. From 1point 3acres bbs
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。

请问第4版有这道题吗
回复 支持 反对

使用道具 举报

Czon 发表于 2015-11-20 05:44:57 | 显示全部楼层
junjunkate 发表于 2015-11-20 00:31.1point3acres缃
请问第4版有这道题吗
. from: 1point3acres.com/bbs
树那一章的最后一题
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-20 00:45:01 | 显示全部楼层
saklyn 发表于 2015-11-19 12:07
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。

书上只是考虑了一侧的情况 这里要两边加起来。。。 不会做  T T 求指点。。。
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-8-20 03:03:28 | 显示全部楼层
何打发123 发表于 2016-8-20 00:45
书上只是考虑了一侧的情况 这里要两边加起来。。。 不会做  T T 求指点。。。

写了一个。。 跑了一下楼主说的case过了。。 想法就是为每一个node生成一个map 存储这一点和左右两条path可能构成的和以及对应路径(各种组合) 对每个点能构成target的路径加入res... 这要面试写出来真的太不容易了。。bb面试怎么这么难了
  1. import java.util.*;

  2. class TreeNode {
  3.          int val;
  4.          TreeNode left;
  5.          TreeNode right;
  6.      TreeNode(int x) { val = x; }
  7. }

  8.        
  9. . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  10. class Solution {
  11.         public ArrayList<ArrayList<Integer>> find(TreeNode n, int target){
  12.                 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  13.                
  14.                 if(n == null) return res;
  15.                
  16.                 dfs(n, res, target);. more info on 1point3acres.com
  17.                 return res;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  18.         }
  19.        
  20.         . 1point 3acres 璁哄潧
  21.        
  22.         private HashMap<Integer, ArrayList<ArrayList<Integer>>> dfs(TreeNode n, ArrayList<ArrayList<Integer>> res, int target){
  23.                
  24.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> map = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();.1point3acres缃
  25.                
  26.                 if(n == null) return map;
  27.                
  28.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> left =
  29.                 dfs(n.left, res, target);
  30.                
  31.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> right =
  32.                 dfs(n.right, res, target);
  33.                 -google 1point3acres
  34.                 //1. 加入这个点本身
  35.                 ArrayList<Integer> a = new ArrayList<Integer>();
  36.                 a.add(n.val);
  37.                 ArrayList<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>();
  38.                 l.add(a);
  39.                 map.put(n.val, l);
  40.                
  41.                 //2.只和左边搭配. from: 1point3acres.com/bbs
  42.                 if(left.size() != 0){
  43.                         for(Integer k : left.keySet()){. From 1point 3acres bbs
  44.                                 ArrayList<ArrayList<Integer>> list = left.get(k);.1point3acres缃
  45.                                
  46.                                 for(ArrayList<Integer> arr : list){
  47.                                         ArrayList<ArrayList<Integer>> temp = map.get(k + n.val);
  48.                                         if(temp == null){
  49.                                                 temp = new ArrayList<ArrayList<Integer>>();
  50.                                                 map.put(k + n.val, temp);
  51.                                         }
  52.                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  53.                                         newArr.addAll(arr);
  54.                                         newArr.add(n.val);
  55.                                         temp.add(newArr);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  56.                                        
  57.                                 }. 1point 3acres 璁哄潧
  58.                         }
  59.                 }
    . Waral 鍗氬鏈夋洿澶氭枃绔,
  60.                
  61.                 //3.只和邮编搭配
  62.                 if(right.size() != 0){
  63.                         for(Integer k : right.keySet()){
  64.                                 ArrayList<ArrayList<Integer>> list = right.get(k);
  65.                                
  66.                                 for(ArrayList<Integer> arr : list){
  67.                                         ArrayList<ArrayList<Integer>> temp = map.get(k + n.val);
  68.                                         if(temp == null){
  69.                                                 temp = new ArrayList<ArrayList<Integer>>();. 鍥磋鎴戜滑@1point 3 acres
  70.                                                 map.put(k + n.val, temp);
  71.                                         }
  72.                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  73.                                         newArr.add(n.val);.鏈枃鍘熷垱鑷1point3acres璁哄潧
  74.                                         newArr.addAll(arr);
  75.                                         temp.add(newArr);
  76.                                 }
  77.                         }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  78.                 }
  79.                
  80.                 //4.左右两侧搭配
  81.                 if(right.size() != 0 && left.size() != 0){
  82.                         for(Integer p : left.keySet()){
  83.                                 ArrayList<ArrayList<Integer>> list1 = left.get(p);. more info on 1point3acres.com
  84.                                 for(ArrayList<Integer> arr1 : list1){. visit 1point3acres.com for more.
  85.                                        
  86.                                         for(Integer q : right.keySet()){
  87.                                                 ArrayList<ArrayList<Integer>> list2 = right.get(q);
  88.                                                 for(ArrayList<Integer> arr2 : list2){. From 1point 3acres bbs
  89.                                                         ArrayList<ArrayList<Integer>> temp = map.get(p + n.val + q);
  90.                                                        
  91.                                                         if(temp == null){
  92.                                                                 temp = new ArrayList<ArrayList<Integer>>();
  93.                                                                 map.put(p + n.val + q, temp);
  94.                                                         }       
  95.                                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  96.                                                        
  97.                                                         newArr.addAll(arr1);
  98.                                                         newArr.add(n.val);
  99.                                                         newArr.addAll(arr2);. visit 1point3acres.com for more.
  100.                                                         temp.add(newArr);
  101.                                                 }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  102.                                         }
  103.                                 }.1point3acres缃
  104.                                
  105.                         }
  106.                 }
  107.                
  108.             //把包括这个点能够成target的path加入res
  109.                  ArrayList<ArrayList<Integer>> cur = map.get(target);
  110.                 if(cur != null){
  111.                         for(ArrayList<Integer> arrList : cur){
  112.                                 res.add(arrList);. 1point3acres.com/bbs
  113.                         }
  114.                 }
  115.                 return map;
  116.                
  117.         }
  118.        
  119.         public static void main(String[] args) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  120.                 Solution r = new Solution();
  121.                
  122.                 TreeNode n1 = new TreeNode(5);
  123.                 TreeNode n2 = new TreeNode(1); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  124.                 TreeNode n3 = new TreeNode(2);
  125.                 TreeNode n4 = new TreeNode(2);
  126.                 TreeNode n5 = new TreeNode(5);
  127.                 TreeNode n6 = new TreeNode(6);
  128.                 . more info on 1point3acres.com
  129.                
  130.                 n1.left = n2;
  131.                 n1.right = n3;
  132.                
  133.                 n2.left = n4;
  134.                 n2.right = n5;
  135.                 n3.right = n6;
  136.        
  137.                 ArrayList<ArrayList<Integer>> res = r.find(n1, 8);
  138.                 for(ArrayList<Integer> arr : res){
  139.                         //System.out.println("******");. From 1point 3acres bbs
  140.                         for(Integer k : arr){
  141.                                 System.out.print(k + " ");. 1point3acres.com/bbs
  142.                         }
  143.                         System.out.println();. Waral 鍗氬鏈夋洿澶氭枃绔,
  144.                 }
  145.                
  146.         }
  147. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-7 20:55

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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