问两道google面试题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

问两道google面试题

问两道google面试题# JobHunting - 待字闺中

a*22011-07-06 07:07

1 楼

1.Convert a min heap to BST without changing its structure and of course no
extra space .
2.Convert a BST to max heap without using extra memory and in as optimum
time as possible

s*n2011-07-06 07:07

2 楼

1. heap sort, then you are done.
2. recursive call,
fin max in bst,
swap root the most right one
do it for left bst, do it for right bst.

no

【在 a**********2 的大作中提到】

: 1.Convert a min heap to BST without changing its structure and of course no
: extra space .
: 2.Convert a BST to max heap without using extra memory and in as optimum
: time as possible

g*y2011-07-06 07:07

3 楼

heap sort result is sorted array, to convert it to an BST in heap structure
seems not trival, especially inplace. For example, an array
1, 2, 3, 4, 7, 8, 9, 10, 14, 16
it's corresponding bst in heap structure should be
9, 4, 14, 2, 8, 10, 16, 1, 3, 7

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

: 1. heap sort, then you are done.
: 2. recursive call,
: fin max in bst,
: swap root the most right one
: do it for left bst, do it for right bst.
:
: no

a*22011-07-06 07:07

4 楼

1. heap sort 是不是要用到额外空间？
假设转化为balanced bst
2. swap完了以后是不是要把right most child siftup到 right child level？因为它
的right most现在是最小值了

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

: 1. heap sort, then you are done.
: 2. recursive call,
: fin max in bst,
: swap root the most right one
: do it for left bst, do it for right bst.
:
: no

g*y2011-07-06 07:07

5 楼

heap sort用的额外变量应该可以，问题是转化成按heap结构排的BST, 那个要inplace
的话，好象很难。
balanced bst没法存在指定的数组空间里。

【在 a**********2 的大作中提到】

: 1. heap sort 是不是要用到额外空间？
: 假设转化为balanced bst
: 2. swap完了以后是不是要把right most child siftup到 right child level？因为它
: 的right most现在是最小值了

d*d2011-07-06 07:07

6 楼

structure

【在 g**********y 的大作中提到】

: heap sort result is sorted array, to convert it to an BST in heap structure
: seems not trival, especially inplace. For example, an array
: 1, 2, 3, 4, 7, 8, 9, 10, 14, 16
: it's corresponding bst in heap structure should be
: 9, 4, 14, 2, 8, 10, 16, 1, 3, 7

d*d2011-07-06 07:07

7 楼

en,也许可以把array也当作bst,不过不是balanced的.

inplace

【在 g**********y 的大作中提到】

: heap sort用的额外变量应该可以，问题是转化成按heap结构排的BST, 那个要inplace
: 的话，好象很难。
: balanced bst没法存在指定的数组空间里。

d*d2011-07-06 07:07

8 楼

2,原地build heap不就完了,不过你那个比较次数可以少一点.

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

: 1. heap sort, then you are done.
: 2. recursive call,
: fin max in bst,
: swap root the most right one
: do it for left bst, do it for right bst.
:
: no

a*22011-07-06 07:07

9 楼

想了一下可不可以这样做：
用sorted double linked list作为两个结构转化的过渡结构
1.1) min heap --> sorted double linked list
2) sorted double linked list --> balanced BST
2.同理，BST 按inorder 转成sorted double linked list，再转成min heap

g*y2011-07-06 07:07

10 楼

写了个要用辅助数组转化min-heap到BST的，原理就是从最小数开始，依次找successor
填空，
public void heap2Bst(int[] a) {
int N = a.length;
Arrays.sort(a);
int[] b = new int[N];

int i = leftest(0, N);
int j = 0;
while (j < N) {
b[i] = a[j];
i = successor(i, N);
j++;
}

for (i=0; i}

private int successor(int i, int N) {
int next = right(i, N);
if (next >= 0) return leftest(next, N);

int parent = parent(i);
while (parent >= 0 && 2*parent+2 == i) {
i = parent;
parent = parent(i);
}
return parent;
}

private int leftest(int i, int N) {
while (left(i, N) >= 0) i = left(i, N);
return i;
}

private int parent(int i) {
return i==0? -1 : (i-1)/2;
}

private int left(int i, int N) {
return 2*i+1 < N? 2*i+1 : -1;
}

private int right(int i, int N) {
return 2*i+2 < N? 2*i+2 : -1;
}

d*d2011-07-06 07:07

11 楼

既然已经用了辅助数组了,为什么不先原地heap sort,再直接用那个array到bst的算法.

successor

【在 g**********y 的大作中提到】

: 写了个要用辅助数组转化min-heap到BST的，原理就是从最小数开始，依次找successor
: 填空，
: public void heap2Bst(int[] a) {
: int N = a.length;
: Arrays.sort(a);
: int[] b = new int[N];
:
: int i = leftest(0, N);
: int j = 0;
: while (j < N) {

g*y2011-07-06 07:07

12 楼

你说的是array到balanced BST算法吧？Balanced BST怎么保存在原数组里，满足堆条
件和BST条件：
parent(i) = (i-1)/2
left(i) = 2*i + 1
right(i) = 2*i + 2
a[left(i)] < a[i] < a[right(i)]

法.

【在 d*******d 的大作中提到】

: 既然已经用了辅助数组了,为什么不先原地heap sort,再直接用那个array到bst的算法.
:
: successor

d*d2011-07-06 07:07

13 楼

对就是这样,和heap一样.不过取root的时候有点tricky,不能直接取n/2那个,而是取头
上(2^k-1)/2那个,k是logn,这样tree就和heap一样朝左对齐了.

【在 g**********y 的大作中提到】

: 你说的是array到balanced BST算法吧？Balanced BST怎么保存在原数组里，满足堆条
: 件和BST条件：
: parent(i) = (i-1)/2
: left(i) = 2*i + 1
: right(i) = 2*i + 2
: a[left(i)] < a[i] < a[right(i)]
:
: 法.

g*y2011-07-06 07:07

14 楼

这个算法有问题吧：对于k层的BST, Root的值比左边子树都大，比右边子树都小，这个
值是个变量，取决于n结束的位置。头上固定取(2^k-1)/2，没法保证左对齐。

【在 d*******d 的大作中提到】

: 对就是这样,和heap一样.不过取root的时候有点tricky,不能直接取n/2那个,而是取头
: 上(2^k-1)/2那个,k是logn,这样tree就和heap一样朝左对齐了.

d*d2011-07-06 07:07

15 楼

那个值是index,是中间那个。

【在 g**********y 的大作中提到】

: 这个算法有问题吧：对于k层的BST, Root的值比左边子树都大，比右边子树都小，这个
: 值是个变量，取决于n结束的位置。头上固定取(2^k-1)/2，没法保证左对齐。

g*y2011-07-06 07:07

16 楼

堆是一层一层都从左到右放，所以可以连续存放在数组里。你那样做出来的是平衡二叉
树，不满足堆结构，没法直接用数组存。

【在 d*******d 的大作中提到】

: 那个值是index,是中间那个。

t*r2011-07-06 07:07

17 楼

MARK

k*n2011-07-06 07:07

18 楼

no
This is a very interesting problem, also very chanllenging.
Worked on it for 10 mins, and finally worked it out.
For a min heap, what we can first think of is doing heap sort.
Then we have a sorted array.
How to convert it to a BST (in array)?
lets first check an example, but in extreme case:
For the sorted array 1 through 7.
The form of BST is
4
2 6
1 3 5 7
So what is it for 1 through 15?
easily to guess:
8
4 12
2 6 10 14
1 3 5 7 9 11 13 15
So it is not very hard to change an array of length 2^k-1 to a BST, though
it should be a little tricky to do it in-place.
THe first way I can think of is to do it recursively. That is,
copy the 1, 3, 5, 7, ...15 into the second half, then this is a half sized
problem. Since we reduce the problem size by 1/2 each time, the time
complexity should be acceptable. Done.
So the next thing is, how to deal with non-full heap/array.
Check array of 1 through 12.
We can get the root element, but it will turn out that you don't want to
bother with this.
Suppose we have 12 elements. Then the final form should look like
X
X X
X X X X
X X X X X
Where 1 goes? 1 should be at the left bottom corner. What is next?
THrough observation, we can see at the bottom level, every element's order
is still strictly bigger than its left side sibling. It is reasonable.
Consider the least common ancester between them: it is the smallest element
in the lca's right subtree, and the left neighbor is the largest of the left
subtree. So the observation still holds for the non-full BST.
So we can merge the two cases into one recursive call.
The next question is: why bother from heap? The above analys has nothing to
do with a heap, right?
I'm really confused. Can anyone give an answer?
void heap2bst(int a[], int n) {
if (n == 1) return;
heapsort(a, n);
int start = 1;
while (start < n) start <<= 1;
start >> = 1;
start --;
int end = 2 * (n-start) - 1;
int i = n-1;
while (end > 0) {
swap(a, i, end);
i--; end -= 2;
}
heap2bst(a, start);
}

【在 a**********2 的大作中提到】

: 1.Convert a min heap to BST without changing its structure and of course no
: extra space .
: 2.Convert a BST to max heap without using extra memory and in as optimum
: time as possible

k*n2011-07-06 07:07

19 楼

no
2> The first thing I can think of is to still use siftdown method, the only
benifit is we don't need to do comparison, just use the right child. This
has been O(N), can it be faster? Let's see what is happening in the
heapifying process:
In a BST:
X
X4 | X
X X1 | X X
X X X2 X3 | X X
At first, X3 will swap with X1, then for X4, it will swap with X3 and then
X1.
So because of the feature of BST, an element is always swapped at the right
hand side, and gurantees to be swapped to the bottom. So the ultimate effect
is that every right most path is reversed. So we can use this to save time.
What left to solve is how to iterate all the paths. A simple observation is
that the starting point of the right arm must start from the odd indices,
except for the top node.
void bst2heap(int a[], int n) {
reverseArm(a, 0, n);
for (i=1; ireverseArm(a, i, n);
}
void reverseArm(int a[], int from, int n) {
int to = from;
while (to*2+2 < n) to = from * 2 + 2;
while (to > from) {
swap(a, to, from);
from = from * 2 + 2;
to = to / 2 - 1;
}
}

【在 a**********2 的大作中提到】

: 1.Convert a min heap to BST without changing its structure and of course no
: extra space .
: 2.Convert a BST to max heap without using extra memory and in as optimum
: time as possible

g*y2011-07-06 07:07

20 楼

Did you test? first, there is a typo, to = from * 2 + 2, it leads to endless
loop. second, even after change, it doesn't work correct.
Try ->
BST = {9, 4, 14, 2, 8, 10, 16, 1, 3, 7}
heap = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1}

only

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

:
: no
: 2> The first thing I can think of is to still use siftdown method, the only
: benifit is we don't need to do comparison, just use the right child. This
: has been O(N), can it be faster? Let's see what is happening in the
: heapifying process:
: In a BST:
: X
: X4 | X
: X X1 | X X

s*x2011-07-06 07:07

21 楼

2
lyle.smu.edu/~saad/courses/cse3358/ps7/problemset7sol.pdf
problem 4 (b)
from career cup

s*n2011-07-06 07:07

22 楼

能不能这样，把数组排序以后，把他变成一个以median为root的数组，然后找一个
index变换方法，这样就可以用algorithm in c里面那个，按照index rearrange数组的
方法了

s*y2011-07-06 07:07

23 楼

No.2 刚写了一个,似乎是对的,只是测试了2个例子:
{9, 4, 14, 2, 8, 10, 16, 1, 3, 7};
//in place swap without using addition variable
void swap(Tree *a, Tree *b)
{
a->element = a->element ^ b->element;
b->element = a->element ^ b->element;
a->element = a->element ^ b->element;
}
void BstToHeap1( Tree *root)
{
if (!root)
return;
BstToHeap1(root->left);
BstToHeap1(root->right);
if (root->right)
swap(root, root->right);
}
void Heapify(Tree *root)
{
if (!root) return;
Heapify(root->left);
Heapify(root->right);
if ((root->left) && (root->left->element > root->element))
swap(root, root->left);
if ((root->right) && (root->right->element > root->element))
swap(root, root->right);
}
void BstToHeap( Tree *root)
{
BstToHeap1(root);
Heapify(root->left);
Heapify(root->right);
return;
}
bst:
9
/ \
/ \
/ \
/ \
4 14
/ \ / \
/ \ / \
/ \ 10 16
2 8
/ \ /
1 3 7
heap:
16
/ \
/ \
/ \
8 14
/ \ / \
/ \ 9 10
/ \
3 7
/ \ /
1 2 4

s*x2011-07-06 07:07

24 楼

我想是对的。 but how to convert min heap to sorted double linked list ? It
would be easy if the heap is in array. For binary heap, not sure how to
remove the root and sift down.

【在 a**********2 的大作中提到】

: 想了一下可不可以这样做：
: 用sorted double linked list作为两个结构转化的过渡结构
: 1.1) min heap --> sorted double linked list
: 2) sorted double linked list --> balanced BST
: 2.同理，BST 按inorder 转成sorted double linked list，再转成min heap

q*x2011-07-06 07:07

25 楼

不是真题吧。这两道都像工制造的。

no

【在 a**********2 的大作中提到】

: 1.Convert a min heap to BST without changing its structure and of course no
: extra space .
: 2.Convert a BST to max heap without using extra memory and in as optimum
: time as possible

c*m2011-07-06 07:07

26 楼

搞了一上午搞出来了第一题，包含以下几点
1. 基本想法类似于HEAPSORT，每次取HEAP 的最小值，和BST tree 当前最小位置的值
交换，然后再维护HEAP 的结构，同时取BST 中序遍历的下一个值。在整个过程中，树
的一部分变成了BST TREE, 另一部分还是HEAP 结构。
下面介绍相关的步骤。
2. 取HEAP 的最小值：粗略的想法是用HEAP[0]。这里有个问题：当HEAP[0] 被并入BST
部分以后，最小值不再是HEAP[0]，而是HEAP[0] 的右子树。可以证明HEAP[0] 被并入
BST 的时候，它的左子树已经全部在BST 里了，而它的右子树都不在BST里，因此可以
TRACK 当前HEAP 的ROOT。
3.维护HEAP 的结构。算法和SIFTDOWN 一样，但要注意的是SIFT DOWN 的时候必须要检
查当前节点的子节点是不是在BST 部分，如果是，就停止交换。要做到这一点，只需要
TRACK 住当前HEAP 的最小值，BST 里的元素都会小于它。
代码如下（HEAP 用数组heap 表示）：
//取一个BST子树最小节点的索引，辅助函数
protected int GetMinIdx(int ridx){
int left=ridx*2+1;
while(leftridx=left;
left=ridx*2+1;
}
return ridx;
}
//SIFT DOWN， r 是当前节点的索引，t 是当前HEAP 的最小值，比t 小的都在BST 里
了。
protected void SiftDownWisely(int r, int t){

while(r*2+1int left=r*2+1;
int right=left+1;
int swapidx=r;
if(leftif(heap[left]t){//swap only if it's not
already in BST
swapidx=left;
}
}
if(rightif(heap[right]t)
swapidx=right;
}
if(swapidx==r)
return;
else{
int temp=heap[swapidx];
heap[swapidx]=heap[r];
heap[r]=temp;
r=swapidx;
}

}
}
//中序遍历BST 的下一个索引
protected int GetFollowingIdx(int curr)
{
int right=curr*2+2;
if(right{
return GetMinIdx(right);
}
//else trace back to the left branching ancestor
int parent=(curr-1)/2;
if(parent==curr)
return -1;
while(curr!=parent*2+1&&curr!=parent)
{
curr=parent;
parent=(curr-1)/2;
}
if(parent==curr)
return -1;
else
return parent;

}
//主函数
public void MinHeap2BST(){
int head=0;//head 记录当前堆顶
int curr=GetMinIdx(head);
for(int i=0;i{
int temp;
if(head==curr){//head is taken, find a new one
head=head*2+2;//the right child becomes new heap head
if(head>=heap.length)
return;
}
else
{
temp=heap[head];
heap[head]=heap[curr];
heap[curr]=temp;
SiftDownWisely(head,temp);
}
curr=GetFollowingIdx(curr);
}
}