《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1383|回复: 8
收起左侧

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

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

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

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

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

x
谈了10分钟project直接来了这题。。给一个binary tree。。 找到所有的paths that sum to a certain value..比如说:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                 5. 1point3acres.com/bbs
              /   \. From 1point 3acres bbs
            1       2. 1point3acres.com/bbs
           / \        \
         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。。
我的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>>();
  4.         if(root != null){. visit 1point3acres.com for more.
  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());
    -google 1point3acres
  11.             }else if(target>root.val){
  12.                 // this handles the path from current node to a child in either left or right subtree.1point3acres缃
  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.                 }
  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) {. visit 1point3acres.com for more.
  30.                             for(LinkedList<Integer> r : rpaths) {
  31.                                 LinkedList<Integer> childpath = new LinkedList<Integer>();
  32.                                 Collections.reverse(r);
  33.                                 childpath.addAll(l);. from: 1point3acres.com/bbs
  34.                                 childpath.add(root.val);
  35.                                 childpath.addAll(r);
  36.                                 paths.add(childpath);. visit 1point3acres.com for more.
  37.                             }
  38.                         }. more info on 1point3acres.com
  39.                     }
  40.                 }

  41.             }else{. more info on 1point3acres.com
  42.                 //do nothing
    . more info on 1point3acres.com
  43.             }
  44.             path.pollFirst();.1point3acres缃
  45.         }
  46.         return childpaths;
  47.     }
  48.     public List<List<Integer>> findPaths(TreeNode root, int target) {
  49.         ArrayList<List<Integer>> paths = new ArrayList<List<Integer>>();
  50.         LinkedList<Integer> path = new LinkedList<Integer>();
  51.         findPathsToSum(root, paths, path, target, target);-google 1point3acres
  52.         return paths;. visit 1point3acres.com for more.
  53.     }
复制代码
最后越写越糊涂。。最后面试官提示这种方法会有很多重复。。问题在于没有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;
  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); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.

  15.   path[level] = Integer.MIN_VALUE;
    .1point3acres缃
  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. }. 1point3acres.com/bbs
  22. .1point3acres缃
  23. void print(int[] path, int start, int end){
  24.     for(in i = start, i <= end; i++)
  25.         System.out.println(path[i] + "");
  26. }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷

  27. int depth(TreeNode node){
  28.     if(node == null){
  29.        return 0;
  30.    }
  31.    else {
  32.      return 1 + Math.max(depth(node.left), depth(node.right));
  33.    }
  34. }
复制代码
回复 支持 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
刚才在书上找到了手打一遍
. 1point3acres.com/bbs
                 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
刚才在书上找到了手打一遍

跑了一下,好像不是楼主的题的答案啊
回复 支持 反对

使用道具 举报

 楼主| junjunkate 发表于 2015-11-20 00:31:55 | 显示全部楼层
saklyn 发表于 2015-11-19 12:07
这个不是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 求指点。。。
.1point3acres缃
写了一个。。 跑了一下楼主说的case过了。。 想法就是为每一个node生成一个map 存储这一点和左右两条path可能构成的和以及对应路径(各种组合) 对每个点能构成target的路径加入res... 这要面试写出来真的太不容易了。。bb面试怎么这么难了
  1. import java.util.*;

  2. class TreeNode {. 1point3acres.com/bbs
  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;. visit 1point3acres.com for more.
  14.                
  15.                 dfs(n, res, target);
  16.                 return res;
  17.         }
  18.        
  19.         . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  20.        
  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>>>();
    . from: 1point3acres.com/bbs
  24.                
  25.                 if(n == null) return map;. from: 1point3acres.com/bbs
  26.                
  27.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> left =
  28.                 dfs(n.left, res, target);
  29.                
  30.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> right = .1point3acres缃
  31.                 dfs(n.right, res, target);
  32.                
  33.                 //1. 加入这个点本身
  34.                 ArrayList<Integer> a = new ArrayList<Integer>();-google 1point3acres
  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.只和左边搭配. 1point 3acres 璁哄潧
  41.                 if(left.size() != 0){
  42.                         for(Integer k : left.keySet()){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  43.                                 ArrayList<ArrayList<Integer>> list = left.get(k);-google 1point3acres
  44.                                
  45.                                 for(ArrayList<Integer> arr : list){
  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);
  53.                                         newArr.add(n.val);
  54.                                         temp.add(newArr);
  55.                                        
  56.                                 }
  57.                         }. 1point3acres.com/bbs
  58.                 }
  59.                 . 1point3acres.com/bbs
  60.                 //3.只和邮编搭配
  61.                 if(right.size() != 0){. visit 1point3acres.com for more.
  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>>();
  69.                                                 map.put(k + n.val, temp);
  70.                                         }
  71.                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  72.                                         newArr.add(n.val);
  73.                                         newArr.addAll(arr);
  74.                                         temp.add(newArr);
  75.                                 }
  76.                         }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  77.                 }. from: 1point3acres.com/bbs
  78.                
  79.                 //4.左右两侧搭配. Waral 鍗氬鏈夋洿澶氭枃绔,
  80.                 if(right.size() != 0 && left.size() != 0){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  81.                         for(Integer p : left.keySet()){
  82.                                 ArrayList<ArrayList<Integer>> list1 = left.get(p);. Waral 鍗氬鏈夋洿澶氭枃绔,
  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);
  89.                                                        
  90.                                                         if(temp == null){
  91.                                                                 temp = new ArrayList<ArrayList<Integer>>();. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  92.                                                                 map.put(p + n.val + q, temp);
  93.                                                         }       
  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.                                 }
  103.                                 -google 1point3acres
  104.                         }
  105.                 }
  106.                 . Waral 鍗氬鏈夋洿澶氭枃绔,
  107.             //把包括这个点能够成target的path加入res
  108.                  ArrayList<ArrayList<Integer>> cur = map.get(target);
  109.                 if(cur != null){
  110.                         for(ArrayList<Integer> arrList : cur){-google 1point3acres
  111.                                 res.add(arrList);
  112.                         }
  113.                 }. 鍥磋鎴戜滑@1point 3 acres
  114.                 return map;. 1point3acres.com/bbs
  115.                
  116.         }
  117.        
  118.         public static void main(String[] args) {
  119.                 Solution r = new Solution();. 1point 3acres 璁哄潧
  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.                
  128.                
  129.                 n1.left = n2;
  130.                 n1.right = n3;.1point3acres缃
  131.                
  132.                 n2.left = n4;
  133.                 n2.right = n5;
  134.                 n3.right = n6;
  135.        
  136.                 ArrayList<ArrayList<Integer>> res = r.find(n1, 8);
  137.                 for(ArrayList<Integer> arr : res){
  138.                         //System.out.println("******");
  139.                         for(Integer k : arr){
  140.                                 System.out.print(k + " ");
  141.                         }-google 1point3acres
  142.                         System.out.println();
  143.                 }
  144.                
  145.         }
  146. }
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-25 19:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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