google phone interview - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

google phone interview

google phone interview# JobHunting - 待字闺中

i*n2012-01-27 08:01

1 楼

The interviewer mentioned if given a perfect balanced BST, if we have the
min node and continuously call the successor function n times.(n is the
number of nodes)So that we could have the in order traverse of the BST. Then
what's the complexity of this algorithms? He said the complexity is O(N),
could anybody help me with this? I am a little bit confused.

p*22012-01-27 08:01

2 楼

Then
有到parent的指针吗？

【在 i******n 的大作中提到】

: The interviewer mentioned if given a perfect balanced BST, if we have the
: min node and continuously call the successor function n times.(n is the
: number of nodes)So that we could have the in order traverse of the BST. Then
: what's the complexity of this algorithms? He said the complexity is O(N),
: could anybody help me with this? I am a little bit confused.

f*t2012-01-27 08:01

3 楼

就是个中序遍历的iterator

i*n2012-01-27 08:01

4 楼

shot! I got what you mean!

【在 f*******t 的大作中提到】

: 就是个中序遍历的iterator

z*92012-01-27 08:01

5 楼

因为是balanced，所以找下一个最多两步就可以了，所以是n的

b*c2012-01-27 08:01

6 楼

PointerType Next()
{
if (m_stack.empty())
return NULL;
PointerType temp = m_stack.top();
m_stack.pop();
return FetchMin(temp->right);
}
PointerType FetchMin(PointerType pushPoint)
{
while (pushPoint)
{
m_stack.push(pushPoint);
pushPoint = pushPoint->left;
}
return m_stack.empty() ? NULL : m_stack.top();
}

Then

【在 i******n 的大作中提到】

w*e2012-01-27 08:01

7 楼

可以解释一下吗谢谢

【在 f*******t 的大作中提到】

: 就是个中序遍历的iterator

f*t2012-01-27 08:01

8 楼

http://en.wikipedia.org/wiki/Tree_traversal
用迭代的方式中序遍历，wiki上有代码。
把stack等状态封装在一个iterator里，就可以实现一步步的输出。时间复杂度是O(N)。

【在 w******e 的大作中提到】

: 可以解释一下吗谢谢

N*82012-01-27 08:01

9 楼

那为什么必须是perfect balanced BST，任何的BST不是都可以？

)。

【在 f*******t 的大作中提到】

: http://en.wikipedia.org/wiki/Tree_traversal
: 用迭代的方式中序遍历，wiki上有代码。
: 把stack等状态封装在一个iterator里，就可以实现一步步的输出。时间复杂度是O(N)。

f*t2012-01-27 08:01

10 楼

不是必须

【在 N*****8 的大作中提到】

: 那为什么必须是perfect balanced BST，任何的BST不是都可以？
:
: )。

N*82012-01-27 08:01

11 楼

我觉得面试官的思路不是这样的，他说的是如果给个perfect balanced BST，然后给你
个min node，然后呼叫n次的findSuccesor() method，那么你能得到一个sorted
traversal(这个非常trivial)。但是他说时间复杂度是O(N)，这个我想不通，我推算了
一下应该要O(nlogn)，因为worst case findSuccesor()需要O(logn)。

【在 f*******t 的大作中提到】

: 不是必须