一亩三分地论坛

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

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

请教大神们两道F面试题的folllow up

[复制链接] |试试Instant~ |关注本帖
yuxrose 发表于 2015-4-1 03:41:47 | 显示全部楼层 |阅读模式

2015(1-3月) 码农类 博士 全职@Facebook - 内推 - 技术电面 |Other在职跳槽

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

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

x
第一题是print all path from root to leaf
比如tree是
                A
            B       C

print AB, AC

这题用DFS还蛮好做的,如果用stack怎么做呢?


.鐣欏璁哄潧-涓浜-涓夊垎鍦第二题有点像,给一个tree,返回每个点左右子树的和与自己值的差,用递归做,还问
了不递归怎么做

这题也是dfs好做,如果不递归的难点在于,每个treenode需要记录他的左子树的和,
右子书的和,再减去自己的node val. 一个stack好像不够,我是用了一个hashmap记录. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
每个node对应的左右子树的和,再用一个stack做post order traversal, 感觉挺麻烦
的,不知有什么巧妙的办法吗?. From 1point 3acres bbs


谢谢大家帮忙!

本帖被以下淘专辑推荐:

siren01 发表于 2015-4-2 11:09:51 | 显示全部楼层
  1. //首先是用DFS
  2.         public static void path(TreeNode root, StringBuilder sb){
  3.                 if(root==null)
  4.                         return;
  5.                 sb.append(root.val);. Waral 鍗氬鏈夋洿澶氭枃绔,
  6.                 if(root.left==null && root.right==null){. Waral 鍗氬鏈夋洿澶氭枃绔,
  7.                         System.out.println(sb.toString());
  8.                 }
  9.                 path(root.left, sb);
  10.                 path(root.right, sb);
  11.                 sb.deleteCharAt(sb.length()-1);
  12.         }
  13.         //第二个是可以是用Stack
  14.         public static void path2(TreeNode root, StringBuilder sb){
  15.                 if(root==null)
  16.                         return;
  17.                 Stack<TreeNode> stack = new Stack<TreeNode>();
  18.                 TreeNode visited = null;. 1point3acres.com/bbs
  19.                 while(root!=null || !stack.empty()){.鐣欏璁哄潧-涓浜-涓夊垎鍦
  20.                         if(root!=null){
  21.                                 stack.push(root);
  22.                                 sb.append(root.val);
  23.                                 root = root.left;
  24.                         }
  25.                         else{
  26.                                 root = stack.peek();
  27.                                 if(root.right!=visited && root.right!=null){
    . 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  28.                                         root=root.right;
  29.                                 }
  30.                                 else{
  31.                                         if(root.left==null && root.right==null){. visit 1point3acres.com for more.
  32.                                                 System.out.println(sb.toString());
  33.                                         }
  34.                                         stack.pop();
  35.                                         sb.deleteCharAt(sb.length()-1);
  36.                                         visited = root;
  37.                                         root = null;
  38.                                 }. more info on 1point3acres.com
  39.                         }
    . 1point 3acres 璁哄潧
  40.                 }
  41.         }
复制代码

补充内容 (2015-4-2 11:13):
我楼上层主的代码貌似行不通,不信可以一试
回复 支持 2 反对 0

使用道具 举报

 楼主| yuxrose 发表于 2015-4-1 07:48:21 | 显示全部楼层
自己提一提
回复 支持 反对

使用道具 举报

crazybadboy 发表于 2015-4-1 08:16:13 | 显示全部楼层
请问返回的是个tree还是什么?能把interface具体说下么?
回复 支持 反对

使用道具 举报

mikezc123 发表于 2015-4-1 11:41:02 | 显示全部楼层
  1. public static void path(Node root){
  2.                 List<List<Integer>> res = new ArrayList<List<Integer>>();
  3.                 LinkedList<Node> sta = new LinkedList<Node>();.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.                 List<Integer> path = new ArrayList<Integer>();
  5.                 sta.push(root);
  6.         Node pre = null;
  7.         
  8.                 while(sta.isEmpty()==false){
  9.                         Node cur = sta.peek();
  10.                         if(cur.left==null && cur.right==null){
  11.                                 List<Integer> arr = new ArrayList<Integer>(path);
  12.                                 arr.add(cur.val);
  13.                                 res.add(arr);. 1point 3acres 璁哄潧
  14.                                 sta.pop();
  15.                                 pre = cur;
  16.                                 continue;
  17.                         }
  18.                        
  19.                         if(pre!=null && (cur.left==pre || cur.right==pre)){
  20.                                 pre = sta.pop();
  21.                                 path.remove(path.size()-1);
  22.                         }
  23.                         else{.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                                 path.add(cur.val);
  25.                                 if(cur.right!=null)  sta.push(cur.right);
  26.                                 if(cur.left!=null)  sta.push(cur.left); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  27.                         }
  28.                 }. 1point3acres.com/bbs
  29.         }
复制代码

补充内容 (2015-4-1 11:41):
第一题可以用栈,纪录下路径并维护
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 11:12:44 | 显示全部楼层

这题递归stack空间是O(log n),stringbuilder是O(log n),
时间是O(n), 每个节点都要遍历-google 1point3acres

用stack也是一样 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. 1point3acres.com/bbs
补充内容 (2015-4-2 12:20):
非递归做第二题,还没想到,求大神
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-2 11:38:00 | 显示全部楼层
siren01 发表于 2015-4-2 11:09
补充内容 (2015-4-2 11:13):
我楼上层主的代码貌似行不通,不信可以一试

层主的第二种解法貌似不大对。具体说就是pop和deletechar的次数不够。会出现错误的path-google 1point3acres

补充内容 (2015-4-2 11:45):
不好意思 算法是对的 是StringBuilder的问题 换成arraylist就好了
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 12:23:14 | 显示全部楼层
ppips 发表于 2015-4-2 11:38
层主的第二种解法貌似不大对。具体说就是pop和deletechar的次数不够。会出现错误的path

补充内容 (2015- ...
.鐣欏璁哄潧-涓浜-涓夊垎鍦
are u sure? 我亲测无误才发的...你给个case我跑一下,StringBuilder做这题才对,我记得有人提过面试的时候要即时打印,不用存起来

补充内容 (2015-4-2 12:26):. 鍥磋鎴戜滑@1point 3 acres
你看看楼主发的帖子,最后是
print !!! AB AC
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-2 12:31:57 | 显示全部楼层
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转,觉得不会再爱了。。。。
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-2 12:32:28 | 显示全部楼层
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转,觉得不会再爱了。。。。
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 12:34:44 | 显示全部楼层
yuxrose 发表于 2015-4-2 12:32. more info on 1point3acres.com
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转, ...

你想到第二题的非递归解法没?
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-2 12:44:03 | 显示全部楼层
siren01 发表于 2015-4-2 12:34. more info on 1point3acres.com
你想到第二题的非递归解法没?

感觉hashmap+postOrder这方法...复杂度略高,希望有大神指导
回复 支持 反对

使用道具 举报

pro 发表于 2015-4-2 12:48:32 | 显示全部楼层
yuxrose 发表于 2015-4-2 12:32. 1point3acres.com/bbs
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转, ...
. From 1point 3acres bbs
快用continuation-passing style跟他们谈笑风生
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-2 13:00:51 | 显示全部楼层
siren01 发表于 2015-4-2 12:44
感觉hashmap+postOrder这方法...复杂度略高,希望有大神指导

在不能修改TreeNode结构的情况下 不觉得还有更好的solution了
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-2 13:21:49 | 显示全部楼层
siren01 发表于 2015-4-2 12:44. more info on 1point3acres.com
感觉hashmap+postOrder这方法...复杂度略高,希望有大神指导

想到还发帖子干嘛。。好顽皮的层主。。。
回复 支持 反对

使用道具 举报

 楼主| yuxrose 发表于 2015-4-2 13:22:36 | 显示全部楼层
pro 发表于 2015-4-2 12:48
快用continuation-passing style跟他们谈笑风生

我不想面了,面了也是丢人。。。。。
回复 支持 反对

使用道具 举报

pro 发表于 2015-4-2 13:24:02 | 显示全部楼层
yuxrose 发表于 2015-4-2 13:22
我不想面了,面了也是丢人。。。。。

我毕业找工作的时候参加各种公司onsite的主要目的向来是旅游+蹭饭(
回复 支持 反对

使用道具 举报

sonicgu 发表于 2015-4-3 05:10:04 | 显示全部楼层
第二题用三个stack,一个维护后续遍历,一个维护每个节点为根的字数和,另一个维护你要的结果
回复 支持 反对

使用道具 举报

siren01 发表于 2015-4-3 05:13:32 | 显示全部楼层
sonicgu 发表于 2015-4-3 05:10.鐣欏璁哄潧-涓浜-涓夊垎鍦
第二题用三个stack,一个维护后续遍历,一个维护每个节点为根的字数和,另一个维护你要的结果
.鐣欏璁哄潧-涓浜-涓夊垎鍦
求上代码呀,攒RP
回复 支持 反对

使用道具 举报

ppips 发表于 2015-4-3 12:58:52 | 显示全部楼层
请问楼主第二题的返回值是什么
每个点的差值结果存储在一个list里面是么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-10 11:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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