i**********e
发帖数: 1145 | 1 至于怎么把 BTR 转化成 GT 这个过程可以很简单，就看你怎么定义 GT 的 data
structure.
只要把传统二叉树的 left node 定义为 GT 的 first child node，然后 right node
定义为当前 node 的 nextSibling node，就搞定了。这样还省了转化过程。
直接 binary tree preorder 和 inorder 实现一遍就搞定了。 |
|
g***i
发帖数: 4272 | 2 两个电话面试，紧挨着，两小时完成的，还挺简单的
1. 两个array 的intersection
（用了个set,直接七八行写完，说了个ok就过了）
2. BST inorder next node
（careercup原题，可惜忘了，写了好久。还有一处有个bug，问我&&逻辑先后，short
circuit问题）
---
1. 10^9个star，亮度为double类型，找出前一千个最亮的
（我一开始说用heap，后来发现不好用，就改了bst，size 1000的，超了就比较最小的
，删除最小的，再插入）
2. 一个动态规划的题目，好像是intro to design & analysis of algorithm上的课后题
3. monochrome bitmap，找出最大的白色矩形。
（卡这了，brutal force也不太会），求教这个咋做 |
|
s******n
发帖数: 3946 | 3 有些不难的题目还是需要记忆，比如inorder下个，容易忘掉。 |
|
m*******m
发帖数: 82 | 4 The first question, I guess it is a binary search tree? And does each node
have a parent pointer?
for BST : get the node and find the inorder successor
if(n->right) : find minimum in n->right
else
find parent of n in loop, till n is parent->right :
(n = parent, find parent(n) |
|
|
|
p****n
发帖数: 148 | 7 有虫吧
有输入错
＋1＋2也不对巴
要不要在楼主的例子上跑一跑？
int |
|
z*********8
发帖数: 2070 | 8 请问怎么做？
我想的作弊方法就是在constructor里面直接inorder recursion走一遍把所有node存到
stack里面。。。 |
|
z*********8
发帖数: 2070 | 9 意思是每次调用next， 打印出来的节点顺序应该和inorder traversal一样 |
|
g*********e
发帖数: 14401 | 10 iterative inorder traversal without visited flag
void in_order_traversal_iterative(BinaryTree *root) {
stack s;
BinaryTree *current = root;
while (!s.empty() || current) {
if (current) {
s.push(current);
current = current->left;
} else {
current = s.top();
s.pop();
cout << current->data << " ";
current = current->right;
}
}
} |
|
s******n
发帖数: 3946 | 11 inorder网上有，另外两个找不到现成答案，帮看看对不对?
Node* preOrderNext(Node* n)
{
if (n->left) return n->left;
if (n->right) return n->right;
Node* p = n->parent;
while (p && p->right==n) {
n = p;
p = n->parent;
}
if (!p) return p;
if (p->right) return p->right;
return p;
}
Node* left_most(Node* n) {
assert(n);
while(n->left) {
n=n->left;
}
return n;
}
Node* postOrderNext(Node* n)
{
Node* p = n->parent;
if (!p) reutrn p;
if (n==p->right) return p;
if (p->right) return left_most(p->right);
return p... 阅读全帖 |
|
y**********u
发帖数: 6366 | 12 2. merge 2颗bst是不是第一个问题的后续？
第一个问题隐含inorder traversal
所以merge 2颗bst可以转换成2个linklist的merge 。。。
3. 文件名去重复，难道就用md5/sha1这样的hash?
4. os的调度，太复杂了，以前做个berkeley schedular就爆了 |
|
l*********8
发帖数: 4642 | 13 void InOrder(Node * root)
{
for(Node *p = root, *prev = root; p; ) {
if (prev != p->left && prev != p->right && p->left) {
prev = p; p = p->left;
continue;
} else if (prev != p->right) {
Print(p->data);
if (p->right) {
prev = p; p = p->right;
continue;
}
}
prev = p; p = p->father;
}
} |
|
t**********h
发帖数: 2273 | 14 上次被某个牛人教育了下，知道了morris traversal，inorder的，不用stack，不递归
，不需要父亲指针。。。 |
|
|
p*****2
发帖数: 21240 | 16 BST inorder两头来，O(n)
这题咋搞。 |
|
i*********7
发帖数: 348 | 17 =.= 为啥那个方法不行。那个方法明显最优啊。否则就是inorder-dfs比较前一个遍历
的数字和当前数字的大小了。 |
|
h*********n
发帖数: 46 | 18 第三轮你是把inorder 和preorder写进文件吗？
另外，德州8万多的工作很牛逼了啊。楼主你面的哪个组，system infrastructure? |
|
h*********n
发帖数: 46 | 19 第三轮你是把inorder 和preorder写进文件吗？
另外，德州8万多的工作很牛逼了啊。楼主你面的哪个组，system infrastructure? |
|
S*******e
发帖数: 379 | 20 glassdoor上看到的，这题如果有parent point还比较简单，
如果没有的话怎么整？ |
|
h*******n
发帖数: 614 | 21 iterative in order traversal. |
|
|
S*******e
发帖数: 379 | 23 多谢两位，大概写了一下，能帮们确认一下吗?
Node *findInOrderSuccessor(Node *root, Node *target){
Stack s;
Node *cur = root;
Node *prev = NULL;
while(true){
while(cur) {
s.push(cur);
cur = cur->left;
}
if (s.empty()){
break;
} else {
cur = s.pop();
}
if (prev == target) {
return cur;
}
prev = cur;
cur = cur->right;
}
return NULL;
} |
|
y****g
发帖数: 5 | 24 Isn't the answer leftmost node of target node's right child tree?? |
|
y***1
发帖数: 450 | 25 I think that's the answer, but you have to handle the case when the node
does not have right node. In that case, use breadth-first traversal. |
|
t********3
发帖数: 567 | 26 if this node has right subtree, get the min node from that.
if not, travel from root node to current node, store the path in some kind
of list/or stack etc. iterate back according to the list/stack, the
successor is the first right parent node |
|
|
|
p*****2
发帖数: 21240 | 29 写了一个练练手
def first(root):
if root!=None:
l=first(root.left)
if l: return l
return root
def dfs(root,node):
if root==None: return root
if root==node:
r=first(root.right)
return r if r else root
else:
l=dfs(root.left,node)
if l: return l if l!=node else root
else: return dfs(root.right,node)
def next(root,node):
ret=dfs(root,node)
return ret if ret!=node else None |
|
|
p*****2
发帖数: 21240 | 31
当node 是subtree的最右边值，我会返回node的。告诉上边我找到node了，但是没找到
next。
如果这个subtree恰好是上一层的左数，那就返回上一层的node，不然继续返回node往
上走。 |
|
i**********e
发帖数: 1145 | 32 呵呵，少看了一个条件。没事，你是考虑了这个条件的。
另外，这个dfs 不好写吧，很容易出错，你代码太多隐含条件。还有一个担心的是效率
问题。例如，一个 node 如果有 left node，直接返回 left-most node 即可，但你的
程序
每次要从root 开始.
只有在 node 是 leaf node 的情况之下 才需要从 root 开始。这个可以递归或者用
stack，没必要搞得那么复杂。 |
|
Z*****Z
发帖数: 723 | 33 响应大侠号召。写了个直白板的，求拍。
static >Node next(Node tree, Node node) {
if(tree == null){
return null;
}
if(node.right != null){
Node tmp = node.right;
while(tmp.left != null){
tmp = tmp.left;
}
return tmp;
}
Stack> stk = new Stack>();
if(!searchNode(tree, node, stk)){
return null;
... 阅读全帖 |
|
|
|
p*****2
发帖数: 21240 | 36
stack是正确的解法。leetcode已经总结了。不过我看到这题的第一感觉就是dfs，所以
就写出来了。这个跟个人的思维习惯有关系，我做dfs比较熟。 |
|
p*****2
发帖数: 21240 | 37
嗯。leetcode总结的很好。这个优化应该有。 |
|
|
i**********e
发帖数: 1145 | 39 小心别把面试官给震经了。
２爷：
“这么简单的题我一向来都是直接上ｄｆｓ的！”
面试官直接跪了。。。 |
|
w****x
发帖数: 2483 | 40 5 minutes
struct NODE
{
int nVal;
NODE* pLft;
NODE* pRgt;
NODE(int n) : nVal(n), pLft(NULL), pRgt(NULL) {}
};
class BTIterator
{
public:
void Init(NODE* pRoot)
{ PushLefts(pRoot); }
NODE* Next()
{
if (m_stk.empty())
return NULL;
NODE* pRet = m_stk.top();
m_stk.pop();
PushLefts(pRet->pRgt);
return pRet;
}
private:
void PushLefts(NODE* pNode)
{
while (NULL != pNode)
{
m_stk.p... 阅读全帖 |
|
p*****2
发帖数: 21240 | 41
刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。 |
|
p*****2
发帖数: 21240 | 42
刚开始我以为写个class，像你这样。后来觉得写给定一个node找下一个更难一些。 |
|
w****x
发帖数: 2483 | 43
滔滔江水连绵不绝，黄河泛滥一发不可收拾啊~~ |
|
|
|
l****i
发帖数: 230 | 46 这周周二的onsite，一共五轮面试。安排比较混乱，其中一个interviewer，我干等了
半个小时，no show。联系HR，才知道这个interviewer已经休假5个月。所以后来又加
了一个interviewer。
感觉google的面试根本不考虑candidate的背景和经历，只考coding。我有朋友做到了
CS Top-4的正教授，去google面试仍然是一样的流程。这个确实让人非常frustrated。
1. Thesis discussion：老印，data base出身，鸡同鸭讲，面得很费劲，互相感觉都
不是很好。
2. 老中，coding：给一个N个node的BST，给一个Key，返回与key最接近的m个node(m
).
我开始说可以做inorder traverse，用一个priority queue保存跟key最近的m个value
，复杂度O(n)；存在average O(log n)的算法，但不好写。结果还是被要求写O(log n)
的code。
这个算法不是很难(不确定是不是最优)，但是在30分钟写出来确实不容易。
我的基本思路还是用priority... 阅读全帖 |
|
e****e
发帖数: 418 | 47 For Q2, implement 2 methods, goToNextNode(Node node), goToPrevNode(Node node
). Mehtod goToNextNode(Node curNode) returns the node on the right subTree
of curNode and this node has the closest key to the curKey among the subTree
. It's like the next node in inorder traversal.
Then go to the node containing the input key, from there, call goToNextNode(
)/goToPrevNode recursively and compare its key the input key. You can think
of those two methods as two pointers in between which input key node.
... 阅读全帖 |
|
a*******y
发帖数: 1040 | 48 不太明白这个“找到结点后继续遍历，直到和队列头的误差
小于队列尾的误差”
继续便利是指以这个节点为根节点在inorder吗？
那下一次遍历以那个节点那?还有“队列头的误差
小于队列尾的误差”是什么道理？ |
|
a*******y
发帖数: 1040 | 49 哦，明白了，是再遍历这个inorder 数组，最多2k个iteration
不过你这个队列头应该是和对列尾的后面一个比，而不是和队列尾比 |
|
g*******y
发帖数: 1930 | 50 这个思路很好，但是可惜不work（不敢肯定一定不work，至少狠不efficient），因为
要递归的话，你得知道［child_i_root］这个集合里的node的个数
要给提示么？还是再想想？我说个不算提示的提示吧，就是这个题目里面真正有用的
input只有bool is_leaf，那个string node_value完全是迷惑人的
inorde
postLis
rootNode
出来
递归 |
|
