一亩三分地论坛

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

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

脸家电面

[复制链接] |试试Instant~ |关注本帖
mnmunknown 发表于 2016-9-6 00:18:17 | 显示全部楼层 |阅读模式

2016(7-9月) 码农类 硕士 全职@Facebook - 内推 - 技术电面 |Passfresh grad应届毕业生

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

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

x
两周前电面的,一个印度大哥,看 linkedin 界面上写自己会 Gujarati , Hindi 和巴基斯坦的 Urdu 语,和小伙伴讨论了一下这哥们可能是印度北部地区的锡克人。。

已约 onsite,过几天面,发个电面面经就当回馈地里,攒攒人品了。onsite的内容因为 NDA 估计不好直接发,争取换个形式。

题就一道,给一个二叉树,输出所有 root - leaf 的路径,递归做完了让迭代。这位大哥惜字如金,做题中间很少插话,一度弄的有点紧张。。做完之后时间还剩不少,想多要点题这哥们居然拒绝了,剩下了十几二十分钟里都在聊天。。。他在 fb 工作了很多年,我就问了好多他以前做过的 project,又聊了聊 memcached,算是愉快结束~
 楼主| mnmunknown 发表于 2016-9-11 23:54:20 | 显示全部楼层
lookbackinanger 发表于 2016-9-10 13:24.鏈枃鍘熷垱鑷1point3acres璁哄潧
迭代的话是要前序遍历时把当前p->right 和path一起压入桟中么? 有没有更好的做法?

比较容易想到和实现但是效率不算特别好的办法,就是 BFS,用一个 Queue<List<Node>> 来存 path 信息,每次遍历的时候 poll 出来的 List 里最后一个 Node 都代表 current node,然后看它的左右子节点就行了~. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
. 1point3acres.com/bbs
还有一种比较好玩的 DFS 递归转迭代的方式是自己定义可能出现的几种状态,然后写个 stack frame 模拟搜索你写递归时候的 dfs stack 过程,代码大概是下面这样,你可以参考下看看是不是有 bug
  1. public static void printPaths(TreeNode root){
  2.         Stack<StackFrame> stack = new Stack<>();
  3.         List<TreeNode> list = new ArrayList<>();
  4.         if(root != null) stack.push(new StackFrame(0, root));

  5.         while(!stack.isEmpty()){
  6.             StackFrame curFrame = stack.peek();
  7.             TreeNode curNode = curFrame.node;

  8.             if(curNode == null) {
  9.                 stack.pop();. From 1point 3acres bbs
  10.             } else if(curFrame.status == 0){
  11.                 list.add(curNode);
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  12.                 curFrame.status = 1;
  13.                 stack.push(new StackFrame(0, curNode.left));
  14.             } else if(curFrame.status == 1){
  15.                 curFrame.status = 2;
  16.                 stack.push(new StackFrame(0, curNode.right));
  17.             } else {. more info on 1point3acres.com
  18.                 if(curNode.left == null && curNode.right == null) {
  19.                     for (TreeNode node : list) System.out.print("" + node.val + ",");. more info on 1point3acres.com
  20.                     System.out.println();
  21.                 }
  22.                 stack.pop();
  23.                 list.remove(list.size() - 1);. visit 1point3acres.com for more.
  24.             }. from: 1point3acres.com/bbs
  25.         }. more info on 1point3acres.com
  26.     }
复制代码

补充内容 (2016-9-11 23:57):
0 - 当前 stack frame 还未访问子树;
1 - 当前 stack frame 正在访问其左子树;
2 - 当前 stack frame 正在访问其右子树。
回复 支持 2 反对 0

使用道具 举报

iPhD 发表于 2016-9-6 01:45:11 | 显示全部楼层
这是LC上面那题Binary Tree Paths吗?面试官问时间复杂度了没?网上说时间复杂度不止O(n)?
回复 支持 反对

使用道具 举报

pu0211 发表于 2016-9-6 01:56:02 | 显示全部楼层
楼主内推多久收到面试?
回复 支持 反对

使用道具 举报

houqingniao 发表于 2016-9-7 10:44:23 | 显示全部楼层
这个还要iterative做啊??
回复 支持 反对

使用道具 举报

lookbackinanger 发表于 2016-9-10 13:24:37 | 显示全部楼层
迭代的话是要前序遍历时把当前p->right 和path一起压入桟中么? 有没有更好的做法?
回复 支持 反对

使用道具 举报

hanabeast 发表于 2016-9-10 15:06:14 | 显示全部楼层
这个楼主很厉害啊
回复 支持 反对

使用道具 举报

hanabeast 发表于 2016-9-12 04:01:25 | 显示全部楼层
ofdk88 发表于 2016-9-10 15:55. from: 1point3acres.com/bbs
楼主怎么找到内推的,多久收到面试?

可以去内推板块看看
回复 支持 反对

使用道具 举报

yiwen_15 发表于 2016-10-13 08:46:17 | 显示全部楼层
求onsite面经!明天facebook onsite求指导
回复 支持 反对

使用道具 举报

 楼主| mnmunknown 发表于 2016-10-15 01:11:35 | 显示全部楼层
yiwen_15 发表于 2016-10-13 08:46
求onsite面经!明天facebook onsite求指导
. more info on 1point3acres.com
汗,不好意思我今天才看到这个。。一是有 NDA,二是我觉得我 onsite 碰到的题目还没有我在地里回复过的几个 fb 面经有意思,在具体题目上也不是很有参考价值= =. 1point3acres.com/bbs

马上要 onsite 的建议就是把已经会的再看一看,最后一天就别突击了影响心情,放松点不要方就行。。 good luck ~
回复 支持 反对

使用道具 举报

yiwen_15 发表于 2016-10-15 02:04:48 | 显示全部楼层
mnmunknown 发表于 2016-10-15 01:11
汗,不好意思我今天才看到这个。。一是有 NDA,二是我觉得我 onsite 碰到的题目还没有我在地里回复过的几 ...

. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷多谢啦!
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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