聊聊在私立文理读cs的两年感受

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 5086|回复: 21
收起左侧

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

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

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

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

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

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

print AB, AC. 牛人云集,一亩三分地

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

. 1point3acres
第二题有点像,给一个tree,返回每个点左右子树的和与自己值的差,用递归做,还问
了不递归怎么做

这题也是dfs好做,如果不递归的难点在于,每个treenode需要记录他的左子树的和,
右子书的和,再减去自己的node val. 一个stack好像不够,我是用了一个hashmap记录
每个node对应的左右子树的和,再用一个stack做post order traversal, 感觉挺麻烦
的,不知有什么巧妙的办法吗?


谢谢大家帮忙!
. 留学申请论坛-一亩三分地

本帖被以下淘专辑推荐:

siren01 发表于 2015-4-2 11:09:51 | 显示全部楼层
  1. //首先是用DFS
  2.         public static void path(TreeNode root, StringBuilder sb){
  3.                 if(root==null)
    . 一亩-三分-地,独家发布
  4.                         return;. more info on 1point3acres
  5.                 sb.append(root.val);
  6.                 if(root.left==null && root.right==null){.本文原创自1point3acres论坛
  7.                         System.out.println(sb.toString());
  8.                 }
  9.                 path(root.left, sb);. more info on 1point3acres
  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;
  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){. 1point3acres
  32.                                                 System.out.println(sb.toString());
  33.                                         }
  34.                                         stack.pop();
  35.                                         sb.deleteCharAt(sb.length()-1);
  36.                                         visited = root;
  37.                                         root = null;.留学论坛-一亩-三分地
  38.                                 }
  39.                         }
  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>>();. 1point3acres
  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){.本文原创自1point3acres论坛
  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);.1point3acres网
  13.                                 res.add(arr);
  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{
  24.                                 path.add(cur.val);
  25.                                 if(cur.right!=null)  sta.push(cur.right);. 1point3acres
  26.                                 if(cur.left!=null)  sta.push(cur.left);
  27.                         }
  28.                 }
  29.         }
复制代码

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

使用道具 举报

siren01 发表于 2015-4-2 11:12:44 | 显示全部楼层
. from: 1point3acres
这题递归stack空间是O(log n),stringbuilder是O(log n),. more info on 1point3acres
时间是O(n), 每个节点都要遍历
.1point3acres网
用stack也是一样

补充内容 (2015-4-2 12:20):
非递归做第二题,还没想到,求大神
回复 支持 反对

使用道具 举报

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

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

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

使用道具 举报

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

补充内容 (2015- ...

are u sure? 我亲测无误才发的...你给个case我跑一下,StringBuilder做这题才对,我记得有人提过面试的时候要即时打印,不用存起来

补充内容 (2015-4-2 12:26):
你看看楼主发的帖子,最后是. 1point 3acres 论坛
print !!! AB AC
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

 楼主| 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
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转, ...
. 留学申请论坛-一亩三分地
你想到第二题的非递归解法没?
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

pro 发表于 2015-4-2 12:48:32 | 显示全部楼层
yuxrose 发表于 2015-4-2 12:32. 1point 3acres 论坛
亲们,你们不觉得FB很魔怔吗,什么题都得把recursive换成iterative!看到一个帖子combination sum也要转, ...

快用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
感觉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里面是么?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2018-5-21 09:54

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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