i***1
发帖数: 95 | 1 今天上午第一次电面。
先谈了下简历。
然后就做了关于heap的两个题。版上以前有提到。
在google doc里实现。
等消息。 |
m***j
发帖数: 9290 | |
D***h
发帖数: 183 | 3 具体什么题?
【在 i***1 的大作中提到】
: 今天上午第一次电面。
: 先谈了下简历。
: 然后就做了关于heap的两个题。版上以前有提到。
: 在google doc里实现。
: 等消息。
|
i***1
发帖数: 95 | 4 1) 写一个类，支持两种操作，(a)插入数据，(b)取中位数
2）（因为我的solution用到了heap）所以让实现heap
【在 D***h 的大作中提到】
: 具体什么题?
|
h**6
发帖数: 4160 | |
l******4
发帖数: 729 | 6
2个heap, 一个max, 一个min. 先向max里面push数。 当max里面的数多于min里面数+1
的时候，
pop max heap放入min heap. 中位数就是min heap的root
【在 h**6 的大作中提到】
: 如何用heap来实现呢，没有思路啊。
|
z****n
发帖数: 1379 | 7 写代码时候heap是给你的吗，只用写pop，push就行，还是要自己写heap操作？
1
【在 l******4 的大作中提到】
:
: 2个heap, 一个max, 一个min. 先向max里面push数。 当max里面的数多于min里面数+1
: 的时候，
: pop max heap放入min heap. 中位数就是min heap的root
|
I**A
发帖数: 2345 | 8 没明白
你说的pop max heap是指最大值么？
要不要保证min里的全部比max里的小？
1
【在 l******4 的大作中提到】
:
: 2个heap, 一个max, 一个min. 先向max里面push数。 当max里面的数多于min里面数+1
: 的时候，
: pop max heap放入min heap. 中位数就是min heap的root
|
z****n
发帖数: 1379 | 9 根据heap的特点自然就保证了这些了啊
【在 I**A 的大作中提到】
: 没明白
: 你说的pop max heap是指最大值么？
: 要不要保证min里的全部比max里的小？
:
: 1
|
l******4
发帖数: 729 | 10
这又不是我面试啊。 问楼主
【在 z****n 的大作中提到】
: 写代码时候heap是给你的吗，只用写pop，push就行，还是要自己写heap操作？
:
: 1
|
|
|
z****n
发帖数: 1379 | 11 恩，就是想问楼主来着，re错文了：）
【在 l******4 的大作中提到】
:
: 这又不是我面试啊。 问楼主
|
l******4
发帖数: 729 | 12
pop max heap是指最大值。
其实min heap里面所有数都比max heap里面的大（或者等于），因为min heap里面的数
都来自max
heap的最大值。 就相当于把所有数从小到大排列，前半段数都在max heap里面，后半
段都在min
heap中。
【在 I**A 的大作中提到】
: 没明白
: 你说的pop max heap是指最大值么？
: 要不要保证min里的全部比max里的小？
:
: 1
|
i***1
发帖数: 95 | 13 第二个题，就是实现heap。面试前一天晚上刚好看了pearls的后两章。倒数第二章，就
是讲heap的。
【在 z****n 的大作中提到】
: 恩，就是想问楼主来着，re错文了：）
|
I**A
发帖数: 2345 | 14 难道是我理解错了？
1 2 3 5
step 1. 1 to max max(1) min()
step 2. 2 to max, then pop 2 to min， max(1), min(2)
step 3. 3 to max, max(1,3), min(2)
step 4. 5 to max , then pop 5 to min, max(1,3), min(2, 5)
【在 z****n 的大作中提到】
: 根据heap的特点自然就保证了这些了啊
|
I**A
发帖数: 2345 | 15 你们都哪儿找的pearls啊，网上给个link成么？
【在 i***1 的大作中提到】
: 第二个题，就是实现heap。面试前一天晚上刚好看了pearls的后两章。倒数第二章，就
: 是讲heap的。
|
I**A
发帖数: 2345 | 16 对，我后来也觉得是min heap里应该比max heap里大
可是我感觉不能保证这一点啊。
你看看我给的例子，哪儿出了问题？
【在 l******4 的大作中提到】
:
: pop max heap是指最大值。
: 其实min heap里面所有数都比max heap里面的大（或者等于），因为min heap里面的数
: 都来自max
: heap的最大值。 就相当于把所有数从小到大排列，前半段数都在max heap里面，后半
: 段都在min
: heap中。
|
l******4
发帖数: 729 | 17 还真是不对。 我这方法错了。
【在 I**A 的大作中提到】
: 对，我后来也觉得是min heap里应该比max heap里大
: 可是我感觉不能保证这一点啊。
: 你看看我给的例子，哪儿出了问题？
|
I**A
发帖数: 2345 | 18 how about this one?
maintain two heaps, max heap and min heap
for each number v
we compare it against max heap's max and min heap's min.
then, based on the comparison and the difference between the number of items
in min heap and max heap. we either
(1) put v into max or min directly or
(2) we might need to move max's max to min heap and push this v to max, or
(3) we might need to move min's min to max heap and push this v to min.
【在 l******4 的大作中提到】
: 还真是不对。 我这方法错了。
|
l******4
发帖数: 729 | 19 没看懂。
其实只要保证从小到大排列时max heap永远包含前半段， min heap永远包含后半段救
行。
那么还是我原来的方法，每插入一次min heap，检查一下min root 是否大于 max
root。 如
果不是，则交换roots。
one
the
items
【在 I**A 的大作中提到】
: how about this one?
: maintain two heaps, max heap and min heap
: for each number v
: we compare it against max heap's max and min heap's min.
: then, based on the comparison and the difference between the number of items
: in min heap and max heap. we either
: (1) put v into max or min directly or
: (2) we might need to move max's max to min heap and push this v to max, or
: (3) we might need to move min's min to max heap and push this v to min.
:
|
l*******g
发帖数: 4894 | 20 why you need heap??? Also what kind of insertion it is???
You should specify your question.
【在 i***1 的大作中提到】
: 1) 写一个类，支持两种操作，(a)插入数据，(b)取中位数
: 2）（因为我的solution用到了heap）所以让实现heap
|
p******n
发帖数: 32 | 21 You can find the problem in "Career cup 150".
Here is the question:
17.3 Numbers are randomly generated and stored in an array. Write a
program to
find and maintain the median value as new values are generated. pg 52
Solution #2: Keep an additional data structure (a tree)
Use two priority heaps: a max heap for the values below the median, and a
min heap for the values above the median. The median will be largest value
of the min heap. When a new value arrives it is placed in the below heap
if |
i***1
发帖数: 95 | 22 看到前人推荐以后在amazon上买了一本。32块，我觉得还是比较值的。
【在 I**A 的大作中提到】
: 你们都哪儿找的pearls啊，网上给个link成么？
|
