我是如何肉身翻墙,从国内直接来美国工作的?

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
查看: 1524|回复: 8
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
我的人缘0
junjunkate 发表于 2015-11-19 09:10:02 | 显示全部楼层 |阅读模式
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】

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

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

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

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


-google 1point3acres
然后给一个value 8,那么paths 有  [5,1,2], [1,5,2], [2,1,5], [2,6]..  就是说path可以从任何地方开始。.本文原创自1point3acres论坛
最初感觉有点像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 {. Waral 博客有更多文章,
  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.                 }
  19.                 for(LinkedList<Integer> rightpath : rightpaths){
  20.                     rightpath.addFirst(root.val);. visit 1point3acres for more.
  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) {. From 1point 3acres bbs
  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);
  35.                                 childpath.addAll(r);. From 1point 3acres bbs
  36.                                 paths.add(childpath);
  37.                             }
  38.                         }
  39.                     }
  40.                 }
  41. . more info on 1point3acres
  42.             }else{
  43.                 //do nothing. 牛人云集,一亩三分地
  44.             }
  45.             path.pollFirst();
  46.         }. 1point3acres
  47.         return childpaths;
  48.     }
  49.     public List<List<Integer>> findPaths(TreeNode root, int target) {-google 1point3acres
  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。。。 大家对这题有什么解法?



上一篇:11/18 Twitter 电面
下一篇:Google onsite
我的人缘0
saklyn 发表于 2015-11-19 12:16:22 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
刚才在书上找到了手打一遍
  1. void findSum(TreeNode node, int sum, int[] path, int level){
  2.      if(node == null) return;
  3.    . from: 1point3acres
  4.     path[level] = node.data;-google 1point3acres

  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;
  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. }

  22. void print(int[] path, int start, int end){.本文原创自1point3acres论坛
  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

使用道具 举报

我的人缘0
saklyn 发表于 2015-11-19 12:07:07 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。
回复 支持 反对

使用道具 举报

我的人缘0
albee_fighting 发表于 2015-11-19 13:27:46 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
saklyn 发表于 2015-11-19 12:16
刚才在书上找到了手打一遍

                 5
              /   \.本文原创自1point3acres论坛
            1       2. from: 1point3acres
It seems that this situation is not covered by the code.
回复 支持 反对

使用道具 举报

我的人缘0
kimi81017 发表于 2015-11-19 13:32:35 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
saklyn 发表于 2015-11-19 12:16
刚才在书上找到了手打一遍
. 1point3acres
跑了一下,好像不是楼主的题的答案啊
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| junjunkate 发表于 2015-11-20 00:31:55 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
saklyn 发表于 2015-11-19 12:07
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。

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

使用道具 举报

我的人缘0
Czon 发表于 2015-11-20 05:44:57 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
junjunkate 发表于 2015-11-20 00:31
请问第4版有这道题吗

树那一章的最后一题
回复 支持 反对

使用道具 举报

我的人缘0
何打发123 发表于 2016-8-20 00:45:01 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
saklyn 发表于 2015-11-19 12:07
这个不是CC150的原题嘛,买了那本书的话可以看第五版的238页。

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

使用道具 举报

我的人缘0
何打发123 发表于 2016-8-20 03:03:28 | 显示全部楼层
  此人很可信:
 
0% (暂未有人投票) 【我投】
  此人瞎逼逼:
 
0% (暂未有人投票) 【我投】
何打发123 发表于 2016-8-20 00:45
书上只是考虑了一侧的情况 这里要两边加起来。。。 不会做  T T 求指点。。。

写了一个。。 跑了一下楼主说的case过了。。 想法就是为每一个node生成一个map 存储这一点和左右两条path可能构成的和以及对应路径(各种组合) 对每个点能构成target的路径加入res... 这要面试写出来真的太不容易了。。bb面试怎么这么难了
  1. import java.util.*;
  2. .1point3acres网
  3. class TreeNode {
  4.          int val;. 牛人云集,一亩三分地
  5.          TreeNode left;
  6.          TreeNode right;
  7.      TreeNode(int x) { val = x; }
  8. }

  9.        
  10. . 牛人云集,一亩三分地

  11. class Solution {.1point3acres网
  12.         public ArrayList<ArrayList<Integer>> find(TreeNode n, int target){
  13.                 ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  14.                
  15.                 if(n == null) return res;
  16.                
  17.                 dfs(n, res, target);
  18.                 return res;
  19.         }
  20.        
  21.        
  22.        
  23.         private HashMap<Integer, ArrayList<ArrayList<Integer>>> dfs(TreeNode n, ArrayList<ArrayList<Integer>> res, int target){
  24.                
  25.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> map = new HashMap<Integer, ArrayList<ArrayList<Integer>>>();
  26.                
  27.                 if(n == null) return map;
  28.                
  29.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> left =
  30.                 dfs(n.left, res, target);. 一亩-三分-地,独家发布
  31.                
  32.                 HashMap<Integer, ArrayList<ArrayList<Integer>>> right =
  33.                 dfs(n.right, res, target);
  34.                
  35.                 //1. 加入这个点本身
  36.                 ArrayList<Integer> a = new ArrayList<Integer>();. 牛人云集,一亩三分地
  37.                 a.add(n.val);
  38.                 ArrayList<ArrayList<Integer>> l = new ArrayList<ArrayList<Integer>>();
  39.                 l.add(a);
  40.                 map.put(n.val, l);
  41.                
  42.                 //2.只和左边搭配
  43.                 if(left.size() != 0){
  44.                         for(Integer k : left.keySet()){
  45.                                 ArrayList<ArrayList<Integer>> list = left.get(k);
  46.                                
  47.                                 for(ArrayList<Integer> arr : list){. visit 1point3acres for more.
  48.                                         ArrayList<ArrayList<Integer>> temp = map.get(k + n.val);. more info on 1point3acres
  49.                                         if(temp == null){
  50.                                                 temp = new ArrayList<ArrayList<Integer>>();
  51.                                                 map.put(k + n.val, temp);
  52.                                         }.本文原创自1point3acres论坛
  53.                                         ArrayList<Integer> newArr = new ArrayList<Integer>();-google 1point3acres
  54.                                         newArr.addAll(arr);
  55.                                         newArr.add(n.val);
  56.                                         temp.add(newArr);
  57.                                        
  58.                                 }
  59.                         }. more info on 1point3acres
  60.                 }
  61.                
  62.                 //3.只和邮编搭配
  63.                 if(right.size() != 0){
  64.                         for(Integer k : right.keySet()){. 1point 3acres 论坛
  65.                                 ArrayList<ArrayList<Integer>> list = right.get(k);
  66.                                 . from: 1point3acres
  67.                                 for(ArrayList<Integer> arr : list){
  68.                                         ArrayList<ArrayList<Integer>> temp = map.get(k + n.val);.1point3acres网
  69.                                         if(temp == null){
    . From 1point 3acres bbs
  70.                                                 temp = new ArrayList<ArrayList<Integer>>();
  71.                                                 map.put(k + n.val, temp);
  72.                                         }
  73.                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  74.                                         newArr.add(n.val);. 留学申请论坛-一亩三分地
  75.                                         newArr.addAll(arr);
  76.                                         temp.add(newArr);
  77.                                 }-google 1point3acres
  78.                         }
  79.                 }
  80.                
  81.                 //4.左右两侧搭配
  82.                 if(right.size() != 0 && left.size() != 0){. 牛人云集,一亩三分地
  83.                         for(Integer p : left.keySet()){
    . From 1point 3acres bbs
  84.                                 ArrayList<ArrayList<Integer>> list1 = left.get(p);
  85.                                 for(ArrayList<Integer> arr1 : list1){
  86.                                        
  87.                                         for(Integer q : right.keySet()){. 一亩-三分-地,独家发布
  88.                                                 ArrayList<ArrayList<Integer>> list2 = right.get(q);
  89.                                                 for(ArrayList<Integer> arr2 : list2){
  90.                                                         ArrayList<ArrayList<Integer>> temp = map.get(p + n.val + q);. more info on 1point3acres
  91.                                                        
  92.                                                         if(temp == null){
  93.                                                                 temp = new ArrayList<ArrayList<Integer>>();
  94.                                                                 map.put(p + n.val + q, temp);
  95.                                                         }       
  96.                                                         ArrayList<Integer> newArr = new ArrayList<Integer>();
  97.                                                        
  98.                                                         newArr.addAll(arr1);
  99.                                                         newArr.add(n.val);
  100.                                                         newArr.addAll(arr2); 来源一亩.三分地论坛.
  101.                                                         temp.add(newArr);
  102.                                                 }
  103.                                         }
  104.                                 }
  105.                                
  106.                         }
  107.                 }. From 1point 3acres bbs
  108.                
  109.             //把包括这个点能够成target的path加入res
  110.                  ArrayList<ArrayList<Integer>> cur = map.get(target);
  111.                 if(cur != null){
  112.                         for(ArrayList<Integer> arrList : cur){
  113.                                 res.add(arrList);. 1point 3acres 论坛
  114.                         }
  115.                 }
  116.                 return map;
  117.                
  118.         }
  119.        
  120.         public static void main(String[] args) {
  121.                 Solution r = new Solution();
  122.                
  123.                 TreeNode n1 = new TreeNode(5);
  124.                 TreeNode n2 = new TreeNode(1);
  125.                 TreeNode n3 = new TreeNode(2);. 留学申请论坛-一亩三分地
  126.                 TreeNode n4 = new TreeNode(2);
  127.                 TreeNode n5 = new TreeNode(5);
  128.                 TreeNode n6 = new TreeNode(6);
  129.                 . 牛人云集,一亩三分地
  130.                
  131.                 n1.left = n2;
  132.                 n1.right = n3;
  133.                
  134.                 n2.left = n4;
  135.                 n2.right = n5;
  136.                 n3.right = n6;
  137.        
    .留学论坛-一亩-三分地
  138.                 ArrayList<ArrayList<Integer>> res = r.find(n1, 8);
  139.                 for(ArrayList<Integer> arr : res){
  140.                         //System.out.println("******");
  141.                         for(Integer k : arr){
  142.                                 System.out.print(k + " ");
  143.                         }
  144.                         System.out.println();. 留学申请论坛-一亩三分地
  145.                 }
  146.                
  147.         }
  148. }
复制代码
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-28 13:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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