May 2009 - May 2017 论坛八周年-你的足迹,我的骄傲


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 4300|回复: 24
收起左侧

Facebook 最新电面

[复制链接] |试试Instant~ |关注本帖
chensheng 发表于 2016-5-13 03:04:35 | 显示全部楼层 |阅读模式

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

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

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

x

还是基础不够牢固。
. more info on 1point3acres.com
题目:
binary tree inorder traversal

class Node {Node left, Node right, Node parent}

Node getNext (Node current) {
}

Fustang 发表于 2016-6-28 00:17:58 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
利用上parent node的一个想法:
if current.right != null, 这种情况最简单,对current.right做in-order traversal找到的第一个就可以了。
if current.right == null, 这时分两种情况:
1. current是其parent的左节点 (current == current.parent.left), 这时current.parent就是要找的
2. current是其parent的右节点 (current == current.parent.right),这时向上搜索ancestor, (current = current.parent), 遇到的第一个current是parent左节点就可以停下返回1的情况了
回复 支持 4 反对 1

使用道具 举报

csehao 发表于 2016-5-13 05:50:14 | 显示全部楼层
关注一亩三分地微博:
Warald
        Node getNext(Node current){

                if(null == current)
                        return null;

                if(null == current.right){. visit 1point3acres.com for more.
                        while(null != current.parent && current = current.parent.right){
                                current = current.parent;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                        }
                        if(null == current.parent){. more info on 1point3acres.com
                                // it must return from the right most node OR it is the root node, and right child is null.
                                return null;
                        }else{
                                // current = current.parent.left left child.
                                return current.parent;
                        }
                       
                }else{
                        Node c = current.right;. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        while(null != c.left){
                                c = c.left;
                        }
                        return c;
                }
        }
回复 支持 3 反对 0

使用道具 举报

blackrose 发表于 2016-5-13 03:39:46 | 显示全部楼层
啥时候投的简历阿
回复 支持 反对

使用道具 举报

 楼主| chensheng 发表于 2016-5-13 03:40:49 | 显示全部楼层
blackrose 发表于 2016-5-13 03:39
啥时候投的简历阿

三月份内推的
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-13 03:42:41 | 显示全部楼层

再加油面别的!加油加油
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 03:51:27 | 显示全部楼层
Nose class里为什么要有一个指针指向parent ?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:00:34 | 显示全部楼层
讨论一下 这个题 用recursive call 肯定不能做. 如果题目的意思是给定某个node找下一个. 那么如果左右child都是null的时候. 只能从root开始重新遍历. 如果有一个child不是null. 那么在其child里面找下一个就可以了.
回复 支持 反对

使用道具 举报

edcent 发表于 2016-5-13 04:10:52 | 显示全部楼层
感觉跟bst iterator有点点像.用stack?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:15:58 | 显示全部楼层
如果题目的意思是做一个inorder的tree iterator.

class Tree{
        Node root;
        Node c;. from: 1point3acres.com/bbs
        Stack<Node> st;
        Tree(){
                // Initializing tree
                st = new Stack<Node>();
                c = self.root;
        }

        Node inOrderGetNext(){
                while(st.isEmpty() && null == c){
.鏈枃鍘熷垱鑷1point3acres璁哄潧                        if(null == c){
                                Node n = st.pop();. more info on 1point3acres.com
                                c = n.right;
                                return n;
                        }else{
                                st.push(c);
                                c = c.left;
                        }. 鍥磋鎴戜滑@1point 3 acres
                }
                return null;. From 1point 3acres bbs
        }

}
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:30:20 | 显示全部楼层
如果是说给定一个node找下一个 其实感觉不是那么容易写

class Tree{. 1point 3acres 璁哄潧
        Node root;
        Tree(){
                //Initializing. visit 1point3acres.com for more.
        }.鏈枃鍘熷垱鑷1point3acres璁哄潧

        Node getNextAux(Node current){
                // get next one including itself.
                if(null == current.left && null == current.right){
                        return current;
                }else{
                        if(null == current.left){
                                return getNextAux(current.right);. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        }else{
                                return getNextAux(current.left);
                        }
                }
        }

        Node getNext(Node current){
                if(null == current){
                        return null;
                }
                if(null == current.left && null == current.right){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                        Node c = root;
                        Stack<Node> st = new Stack<Node>();-google 1point3acres

                        while(!st.isEmpty() || null != c){
                                if( null == c){
                                        if(st.isEmpty()){
                                                return null;.鐣欏璁哄潧-涓浜-涓夊垎鍦
                                        }else{
                                                Node n = st.pop();
                                                c = n.right;
                                        }
                                }else if( c == current){
                                // we already know c.left c.right is null
                                        if(st.isEmpty()){
                                                return null;. 1point3acres.com/bbs
                                        }else{
                                                return st.pop();
                                        }
                                }       
                        }
                        return null;.鏈枃鍘熷垱鑷1point3acres璁哄潧
                }else{
                        if(null == current.left){
                                return getNextAux(current.right);       
                        }else{
                                return getNextAux(current.left);
                        }
                }
        }. 1point3acres.com/bbs
.鏈枃鍘熷垱鑷1point3acres璁哄潧
}
回复 支持 反对

使用道具 举报

blackrose 发表于 2016-5-13 04:32:06 | 显示全部楼层
csehao 发表于 2016-5-13 04:30
如果是说给定一个node找下一个 其实感觉不是那么容易写

class Tree{

有parent node, 不用那么麻烦。
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-5-13 04:32:11 | 显示全部楼层
这个解法没用到parent. 感觉给了parent 是不是让用constant space?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:32:24 | 显示全部楼层
写复杂了 其实设置一个boolean记录是否已经reach current Node. true的话就return当前node就可以了.
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 04:33:59 | 显示全部楼层
https://leetcode.com/problems/inorder-successor-in-bst/

是这道题吗?
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 05:39:51 | 显示全部楼层
blackrose 发表于 2016-5-13 04:32
有parent node, 不用那么麻烦。

果然。。。 有parent node就完全不同了。。。 待我重新写一个...
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 05:41:38 | 显示全部楼层
wtcupup 发表于 2016-5-13 04:33
https://leetcode.com/problems/inorder-successor-in-bst/

是这道题吗?

看不了呢 感觉像是 能帮忙贴一下题目么..
回复 支持 反对

使用道具 举报

ccrjohn8787 发表于 2016-5-13 05:57:40 | 显示全部楼层
www.leetcode.com/problems/binary-search-tree-iterator/
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 06:07:48 | 显示全部楼层
csehao 发表于 2016-5-13 05:41.鐣欏璁哄潧-涓浜-涓夊垎鍦
看不了呢 感觉像是 能帮忙贴一下题目么..
. 1point3acres.com/bbs
http://buttercola.blogspot.com/2 ... ccessor-in-bst.html
回复 支持 反对

使用道具 举报

wtcupup 发表于 2016-5-13 08:16:34 | 显示全部楼层
楼主,所以到底是哪道题啊?
回复 支持 反对

使用道具 举报

 楼主| chensheng 发表于 2016-5-13 23:02:08 | 显示全部楼层
wtcupup 发表于 2016-5-13 08:16
楼主,所以到底是哪道题啊?

都不是一摸一样的,但是类似,我建议leetcode 相关题目都做一下
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-5-29 20:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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