一亩三分地论坛

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

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

Facebook 最新电面

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

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

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

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

x
.鏈枃鍘熷垱鑷1point3acres璁哄潧
还是基础不够牢固。

题目:
binary tree inorder traversal

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

Node getNext (Node current) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
}

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

使用道具 举报

csehao 发表于 2016-5-13 05:50:14 | 显示全部楼层
        Node getNext(Node current){

                if(null == current)
                        return null;
. Waral 鍗氬鏈夋洿澶氭枃绔,
                if(null == current.right){
                        while(null != current.parent && current = current.parent.right){
                                current = current.parent;
                        }
                        if(null == current.parent){-google 1point3acres
                                // 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{
.鏈枃鍘熷垱鑷1point3acres璁哄潧                        Node c = current.right;
. From 1point 3acres bbs                        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{. 1point3acres.com/bbs
        Node root;
        Node c;
        Stack<Node> st;
        Tree(){.1point3acres缃
                // Initializing tree. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                st = new Stack<Node>();
                c = self.root;
        }

        Node inOrderGetNext(){
                while(st.isEmpty() && null == c){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        if(null == c){
                                Node n = st.pop();
                                c = n.right;
                                return n;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                        }else{
                                st.push(c);
                                c = c.left;
                        }
                }
                return null;
        }

}
回复 支持 反对

使用道具 举报

csehao 发表于 2016-5-13 04:30:20 | 显示全部楼层
如果是说给定一个node找下一个 其实感觉不是那么容易写 . from: 1point3acres.com/bbs
. 1point3acres.com/bbs
class Tree{. From 1point 3acres bbs
        Node root;
        Tree(){
                //Initializing
        }

        Node getNextAux(Node current){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                // 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);
                        }
. more info on 1point3acres.com                }
        }
. 1point 3acres 璁哄潧
        Node getNext(Node current){
                if(null == current){
                        return null;
                }
                if(null == current.left && null == current.right){ 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        Node c = root;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                        Stack<Node> st = new Stack<Node>();
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                        while(!st.isEmpty() || null != c){.鏈枃鍘熷垱鑷1point3acres璁哄潧
                                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;
                                        }else{
                                                return st.pop();
                                        }
                                }       
                        }
                        return null;
                }else{
                        if(null == current.left){. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
                                return getNextAux(current.right);       
                        }else{
                                return getNextAux(current.left); 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
                        }
                }
        }

}
回复 支持 反对

使用道具 举报

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.1point3acres缃
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
看不了呢 感觉像是 能帮忙贴一下题目么..

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 相关题目都做一下
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-4 09:59

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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