近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 1276|回复: 8
收起左侧

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

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

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

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

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

x
谈了10分钟project直接来了这题。。给一个binary tree。。 找到所有的paths that sum to a certain value..比如说:. From 1point 3acres bbs
                 5
              /   \
            1       2 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
           / \        \
         2    5       6



然后给一个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。。 . visit 1point3acres.com for more.
我的code大概是这样。。先考虑不包含root的情况。。那么直接recursively call the function on left/right subtree。。 如果包含root,那么有分两种:1. 从root开始往左或右走 2. 从左边开始,走到root, 在走道右边:
  1. public class PathSumToTarget {.1point3acres缃
  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>>();
  4.         if(root != null){
  5.             // does not include root:
  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);
  17.                     childpaths.add(leftpath);
  18.                 }. 1point 3acres 璁哄潧
  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>();
  32.                                 Collections.reverse(r);
  33.                                 childpath.addAll(l);
  34.                                 childpath.add(root.val);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  35.                                 childpath.addAll(r);
  36.                                 paths.add(childpath);
  37.                             }
  38.                         }
  39.                     }. 1point 3acres 璁哄潧
  40.                 }
  41. . From 1point 3acres bbs
  42.             }else{
  43.                 //do nothing
  44.             }
  45.             path.pollFirst();
  46.         }
  47.         return childpaths;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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>();
  52.         findPathsToSum(root, paths, path, target, target);
  53.         return paths;
  54.     }
复制代码
最后越写越糊涂。。最后面试官提示这种方法会有很多重复。。问题在于没有decouple里面的4个recursive call。。。 大家对这题有什么解法?


saklyn 发表于 2015-11-19 12:16:22 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
刚才在书上找到了手打一遍
  1. void findSum(TreeNode node, int sum, int[] path, int level){
  2.      if(node == null) return;
  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) {
  9.           print(path, i, level);
  10.        }
  11.     }
  12.   
  13.    findSum(node.left, sum, path, level +1 );
  14.    findSum(node.right, sume, path, level +1);. more info on 1point3acres.com
  15. . 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  16.   path[level] = Integer.MIN_VALUE;
  17.   }. more info on 1point3acres.com
  18. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  19. void findSum(TreeNode node, int sum){
  20.     int depth = depth(node);
  21.     int path= new int[depth];
  22.     findSum(node, sum, path, 0);
  23. }

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

  28. int depth(TreeNode node){
  29.     if(node == null){
  30.        return 0;
  31.    }
  32.    else {
  33.      return 1 + Math.max(depth(node.left), depth(node.right));
  34.    }
  35. }
复制代码
回复 支持 0 反对 1

使用道具 举报

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

使用道具 举报

albee_fighting 发表于 2015-11-19 13:27:46 | 显示全部楼层
saklyn 发表于 2015-11-19 12:16
刚才在书上找到了手打一遍
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                 5 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
              /   \
            1       2. 1point 3acres 璁哄潧
It seems that this situation is not covered by the code.
回复 支持 反对

使用道具 举报

kimi81017 发表于 2015-11-19 13:32:35 | 显示全部楼层
saklyn 发表于 2015-11-19 12:16 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
刚才在书上找到了手打一遍
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
跑了一下,好像不是楼主的题的答案啊
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

Czon 发表于 2015-11-20 05:44:57 | 显示全部楼层
junjunkate 发表于 2015-11-20 00:31
请问第4版有这道题吗
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
树那一章的最后一题
回复 支持 反对

使用道具 举报

何打发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 求指点。。。
. 1point 3acres 璁哄潧
写了一个。。 跑了一下楼主说的case过了。。 想法就是为每一个node生成一个map 存储这一点和左右两条path可能构成的和以及对应路径(各种组合) 对每个点能构成target的路径加入res... 这要面试写出来真的太不容易了。。bb面试怎么这么难了
  1. import java.util.*;. 鍥磋鎴戜滑@1point 3 acres

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

  8.        


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

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-26 13:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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