脸家电面

两周前电面的，一个印度大哥，看 linkedin 界面上写自己会 Gujarati , Hindi 和巴基斯坦的 Urdu 语，和小伙伴讨论了一

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

了很多年，我就问了好多他以前做过的 project，又聊了聊 memcached，算是愉快结束~

lookbackinanger 发表于 2016-9-10 13:24
迭代的话是要前序遍历时把当前p->right 和path一起压入桟中么? 有没有更好的做法?

比较容易想到和实现但是效率不算特别好的办法，就是 BFS，用一个 Queue<List<Node>> 来存 path 信息，每次遍历的时候 poll 出来的 List 里最后一个 Node 都代表 current node，然后看它的左右子节点就行了~

还有一种比较好玩的 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. 
   
6.         while(!stack.isEmpty()){
   
7.             StackFrame curFrame = stack.peek();
   
8.             TreeNode curNode = curFrame.node;
   
9. 
   
10.             if(curNode == null) {
    
11.                 stack.pop();
    
12.             } else if(curFrame.status == 0){
    
13.                 list.add(curNode);
    
14.                 curFrame.status = 1;
    
15.                 stack.push(new StackFrame(0, curNode.left));
    
16.             } else if(curFrame.status == 1){
    
17.                 curFrame.status = 2;
    
18.                 stack.push(new StackFrame(0, curNode.right));
    
19.             } else {
    
20.                 if(curNode.left == null && curNode.right == null) {
    
21.                     for (TreeNode node : list) System.out.print("" + node.val + ",");
    
22.                     System.out.println();
    
23.                 }
    
24.                 stack.pop();
    
25.                 list.remove(list.size() - 1);
    
26.             }
    
27.         }
    
28.     }

复制代码

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

yiwen_15 发表于 2016-10-13 08:46
求onsite面经！明天facebook onsite求指导

汗，不好意思我今天才看到这个。。一是有 NDA，二是我觉得我 onsite 碰到的题目还没有我在地里回复过的几个 fb 面经有意思，在具体题目上也不是很有参考价值= =

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

这是LC上面那题Binary Tree Paths吗？面试官问时间复杂度了没？网上说时间复杂度不止O(n)?

楼主内推多久收到面试？

这个还要iterative做啊？？

迭代的话是要前序遍历时把当前p->right 和path一起压入桟中么? 有没有更好的做法?

这个楼主很厉害啊

ofdk88 发表于 2016-9-10 15:55
楼主怎么找到内推的，多久收到面试？

可以去内推板块看看

求onsite面经！明天facebook onsite求指导