a****a
发帖数: 15 | 1 应该是两个size为m的min-heap（这样能确保min再其中一个heap里面）
heap 1 负责 file 1, heap 2 负责 file 2
每次extract min(root1, root2) 写到 f3, 然后insert new value into the heap
直到file读完 heaps 都为空
至于内存限制.... f3 写的差不多了 就存到disk一下 |
|
C*7
发帖数: 234 | 2 国女，第一题找n个数中最大的k个，我说用size为k＋1的min heap，放满，然后循环里
不断
poll和add。她觉得结果不对，我就写了下伪码示意（她没让我写代码，我是为了给她
讲明白）
minHeap(k+1)
for(){
heap.poll();
heap.add();
}
她认为不正确，说如果先遇到前k大的结果就不对了（此处我也不知道她在想什么），
我就给她解释＋测试，她又想到别的情况，换各种测试，10多分钟浪费在这，她终于觉
得好像没错。中间我试图给她个台阶，说quick select方法更快，但她完全不理会，继
续纠缠heap的正确性。后来终于跟我说，她想要的解法时size为k的heap，循环里先
peek再根据情况add。如果是讨论复杂度我完全理解，为什么方法不一样就认为是错的
，水平实在很让我吃惊，到最后也没跟我提quick select方法，目测已经超出了她的知
识范围
第二题不知从哪粘过来的，背景还是红色的。。在string末尾添加字符串，使原string
成为回文，返回需要添加的最小string。跟leetcode的Shortest Pali... 阅读全帖 |
|
L***s
发帖数: 1148 | 3 hash heap 思路算是 baseline 标准答案。就在原有的 min heap array
基础上内置一个 hash map 来标记 key 在 heap array 中的 index，
sift up/down, pop, push 每次触发 swap 的时候更新 index 即可。
如果 N >> K，为省空间一般用 min heap of size K，时间每次 O(log K)；
如果 N 和 K 差不多，用 max heap of size N，全装进去好了。
股票总数 N 其实不会太大，所以两者均可。
拓展开来，像这种求 top K frequent 的问题，在 N 非常大时，
hash heap 里面那个 hash map 容易爆（虽然可以取模分布在多机）。
如果不需要准确统计变动次数，允许计数误差(高估)，
其实可用一些基于概率的数据结构来替换该 hash map，
比如类似 bloom filter 的各种变种，比如下面链接提到的 CM Sketch：
http://soulmachine.gitbooks.io/system-design/content/c... 阅读全帖 |
|
z****e
发帖数: 54598 | 4 .的意思是先找到heap所在的内存块
然后取那个variable
t.x
t的值放在stack里面
.的话，系统就会定位到heap中去
然后t.x就定位到heap里面x这个variable
t.x = ***意思就是修改heap里面这个variable的值
t.get(0).x
也是类似的
t.get(0)返回一个reference，然后系统根据这个reference value
定位heap中的内存块，然后.x就是找到这个内存块中的x变量
.get(0)这个还涉及到去method区取方法体
楼主还是要先理解内存中的几个不同的区
stack, heap这些，不理解这些，怎么说都是虚的 |
|
r****o
发帖数: 1950 | 5 我的理解是:
heap就是一段内存空间。每个process都有自己独立的heap和stack，在这个heap和
stack中间还有一个过渡地带。
brk是用来扩大heap的边界(往过渡地带延伸)，
mmap是用来在过渡地带中直接划出一块内存出来(不一定和heap相连)，kernel也有可能
从其他process的heap和过渡地带中暂时调用空闲的内存页。
不知道我的理解是否准确。希望大家指正。 |
|
d******i
发帖数: 7160 | 6 i think you definitely want the pop_heap()
to cover the newly inserted element.
but the newly inserted element - back() HAS ALREADY BROKEN the heap-order.
Then the pop-heap won't work correctly.
Once again, pop-heap requires all the elements conforms the heap-order. It
initially did. But after you changed the back(), it wouldn't.
It's not a proble of one more element or not. It's a problem of WHETHER to
include the new element into the pop-heap or not. Absolutely you need. But
then the pop-heap ... 阅读全帖 |
|
d******i
发帖数: 7160 | 7 just check. u r right.
the MSDN's really confusing about the pop_heap:
"
pop_heap
template
void pop_heap(RanIt first, RanIt last);
template
void pop_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in
the range [first, last) to form a new heap, ordered by operator< and
designated by iterators in the range [first, last - 1), leaving the original
element at *first subsequently at *(last -... 阅读全帖 |
|
z****e
发帖数: 54598 | 8 一个program理论上就只有一个process
尤其是可以开多个threads的program
一个process可以运行多个threads
然后每一个thread有自己的stack
但是object并不仅仅是放在stack中
object有两个部分，主体存放在heap里面
然后heap里面的地址，放在stack中
这就是java中的reference
每个thread保留的是object的reference
每次访问的时候，取出reference然后再去heap中把数据读出来
但是有例外，primitive type，比如int, char, boolean这些数据
是直接存放在stack上的，而不是存地址/引用
所以每次用int的时候，不需要访问heap
比如下图中的alphabet，就直接放在stack上了
这就是为啥别人说这个例子看不出来的缘故
你需要object，只有object可以被共享，如果不是object的话
每个thread用到的primitive type都是自己stack上的
楼主是java没学好，不是os的问题
java认认真真从reference, heap... 阅读全帖 |
|
a**********t
发帖数: 631 | 9
：你连这点基本功都不会，还吹什么牛呀？
：debug heap crash是要能看懂assembly language的，我还没听说过CS牛的人连这个都
小六，这就是你的不对了。对不是专业的领域尽量不要随便批评别人。heap自己不会
crash. heap只会corrupt. heap corrupt时读汇编没啥大用，主要还是找哪里有
memory overflow 或 bad pointer dereferencing. heap corruption 很多时候并不
会造成crash. |
|
I**********s
发帖数: 441 | 10 问了1) 研究, 2) 多线程程序设计, 3) 任意无穷字符串流, 内存有限, 找出唯一一对
重复字符串, 这个我说了哈希表和外部排序, 但是面试人说有更好的办法(后来想也许
是bloom filter), 然后追问外部排序的细节到结束. 估计要挂 :(
总结: 面试既是技术活, 又是运气活.
无论如何, 把我的准备工作放下面, 攒点rp, 希望对大家有所帮助.
Interview Qs
Data Structures
1. Integer
- find number of 1s
- next largest smaller
- smallest larger number
- determine if is palindrom
- itoa, atoi
- add 2 numbers w/o using + or arithmetic operators
- implement *, -, / using only +
- find max of two numbers w/o co... 阅读全帖 |
|
p******n
发帖数: 32 | 11 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 |
|
l****c
发帖数: 16 | 12 要利用a[i]+b[j]>a[i+1]+b[j]和a[i]+b[j]>a[i]+b[j+1]
heap里面存(a[i]+b[j], i, j)
insert (a[0]+b[0], 0, 0) to heap
for (int l=0; l< k; l++){
get the biggest element (a[i]+b[j], i, j) from heap
if (i+1 < m) insert (a[i+1]+b[j], i+1, j) to heap
if (j+1 < n) insert (a[i]+b[j+1], i, j+1) to heap
} |
|
r*******e
发帖数: 7583 | 13 维持一个10个元素的min-heap（注意不是max-heap）
每新到一个元素，与heap顶端元素比较，如果小于，直接丢弃
如果大于，讲heap顶端元素抛弃，将该元素加入heap |
|
s********y
发帖数: 58 | 14 lz是今年毕业吗?我觉得还是好好准备吧, 这个面试官可能不太会引导人, 所以他自己
脑子里是什么样的答案就expect你说什么, 所以听到不一样的他就说你错, 是挺打击人
的.
我仔细看了一下楼主的解, lz说heap的时候确实没有说清楚, "Compare the first
element in heap with next element y in the list which had x. Treat y as a
new x. "
这一句就非常confusing, 什么叫treat y as a new x? 其实lz不用说实现细节, 只需
要说heap的get max和insert y 就好了, 如果要说实现细节, heap不是这样的, pop了
max之后调整heap, 插入的时候总是插在数组末端, 也就是最后一个possible的叶子结
点上, 然后调整元素的. |
|
p******x
发帖数: 691 | 15
stack frames的管理是由编译器决定
管理stack 的指令由编译器插入你程序的二进制代码中
malloc() and free()都是针对heap的，不是针对stack.
double free buffers in stack?
可能会有出错信息，这取决于你的heap管理。
如果你用free(buf1), buf1不在heap范围，会出错。
对于heap 的buffer, 每个buffer块也是按照大小分别管理的
每个buffer块都有meta data指出该块范围等信息。
如果用C/C++.需要
如果是用java，python等，由VM或者interpreter负责管理heap. |
|
k****n
发帖数: 369 | 16
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 lengt... 阅读全帖 |
|
P**********c
发帖数: 3417 | 17 来自主题: JobHunting版 - 问道面试题 类似BFS应该可以解。用一个heap存下一级的数。
先把1放进heap里，
vist 1, 把5,9 放heap里。5是root
把5弄出来，把10, 20放进heap里, 9是root。
取9， 把12放进heap里。
取10。
不过应该有更好的解法。比如说9是不可能比10，20位置上的数大的，所以应该像5，9判断5最小后，应该能知道9是下
一个。 |
|
S**I
发帖数: 15689 | 18 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
S**I
发帖数: 15689 | 19 ☆─────────────────────────────────────☆
gzou (gzou) 于 (Thu May 12 02:26:35 2011, 美东) 提到:
马上就要G on site了，
求祝福。
下面是从本版收集到的Google的试题，便于大家查询。
申明：有的附带有解释说明的，也来自于本版或者网络，大家自己看， 不保证真确
http://www.mitbbs.com/article_t1/JobHunting/31847453_0_1.html
本人ECE fresh PhD，背景是电路/EDA，跟G业务基本没什么关系
同学内部推荐的，很简单的一次电面就给了onsite
题都不难，但是自己没把握好机会，出了一些小bug。
总的感觉，出错就是硬伤，宁可从最简单的算法写起，也不能出错。
电面：
1，Skip list， http://en.wikipedia.org/wiki/Skip_list
写code实现struct skip_list * find(struct skip_list *head, int value)
2，sorted array... 阅读全帖 |
|
H*****1
发帖数: 4815 | 20 来自主题: JobHunting版 - 问道算法题 用前k个数做一个min heap
扫描剩下的数，如果比heap的根节点小就算了，如果大，就加到heap里，同时把heap的
根节点去掉
最后返回heap的根节点 |
|
D********g
发帖数: 650 | 21 第二题
１．每台机器sort array, NlgN
2. Maintain一个size为P的min-heap，heap的每个元素是1中每个array当前最小元素
的值和array的id (1 -- p )，以及指向对应array首部的pointer，heap里的元素是按
照array当前最小元素排列的。
3. 对heap的根，increment 对应array的pointer.然后update heap。重复直道找到Ｎ*
P/2个元素为止。
integers
medium |
|
g**x
发帖数: 373 | 22 K-way merge is good. But it doesn't gain the benefits of the condition that
each column is also in increasing order.
How about this:
Just build a size 3 min heap, using A[0,0], A[0,1], A[1,0].
1)Delete the root of the heap;
2)Add new root's two neighbors (suppose coordinates of new root is [i,j],
pick up [i+1,j] and [i,j+1]).
3)Loop 1),2) K-1 times; We got K-th elements at the root of the heap.
The time complexity is K Log(K) (For each loop, heap size increase at most,
so the heap size is K). It... 阅读全帖 |
|
l****i
发帖数: 230 | 23 不是。
scan一边数组：
如果当前的数比heap的最小值大，更新heap
如果heap的当前sum不足key且当前元素>0，插入
如果heap的当前sum超过key且删除
一遍过后，heap中存的就是值不小于key的最小子集 |
|
s*****n
发帖数: 162 | 24 1. Use a min heap. First insert number a0, a1… ak into the heap. We know
that the min number (the root of the heap) must be placed in position b0. So
we remove it from the heap and place it at b0. Next, we insert number ak+1
into the heap. Again, we can see that the current min number must be placed
in position b1.
So, the time complexity is O(n lgk). |
|
c*****a
发帖数: 808 | 25 我的用堆
public ListNode mergeKLists(ArrayList lists) {
Comparator mycomp = new Comparator(){
@Override
public int compare(ListNode a, ListNode b){
if(a.val
else if(a.val==b.val) return 0;
else return 1;
}
};
if(lists.size()==0) return null;
PriorityQueue heap = new PriorityQueue(lists.
size(), mycomp);
for... 阅读全帖 |
|
d*****y
发帖数: 1365 | 26 先排序,x1=i.其他位置填零
.当然构建这个矩阵是N^2.但是如下所述,我们只需要算2*N个数就可以了.
问题变成找这个矩阵A的最大的N个值.由于A右上角是最大值,所以维持一个max-heap,最
开始的时候把右上角放在heap.然后每次从这个heap里面娶一个数,就把她的左边和下边
放到heap里面,由于对于每个数,每次最多放两个数去heap. 所以O(n log n)
但是这条题目太难了一点,让我面试的时候做,是打死我也做不出来的. |
|
e****e
发帖数: 418 | 27 多谢详细解答。差值相等的情况应该比较常见，例如第一个例子2 5 4 6里，差值2和1
各有两个duplicates.
我在想，也许heap或者改进型的heap或者其他类似数据结构，可以处理数值想等的情况
，就是多pop出几次相同的最大数而已。或者heap的元素类型就是list。unique的数值
， list含一个值，duplicate的数值，list含多个值，反正heap的元素类型要包含i和j
的值，i和j是原数组的下标智，它们的差值的绝对值就是a(i,j)，也是heap insert(),
max()运算的依据。 |
|
u*****o
发帖数: 1224 | 28 我也觉得得用HEAP。是不是可以这样呢？
1。建一个size是m的max-heap. 先push进去sum of A[0]+B[0], A[0]+B[1], ....A[0]+
B[m-1]这
个题就是1+3,1+5,1+7.
2。然后从A[1]开始,开始比较A[1]+B[0],A[1]+B[1]...A[1]+B[m-1]（2+3，2+5，2+7）
这些和和heap里面的数大小。如果A[1]+B[0]已经大过现在heap max(1+7), 直接output
3. 如果不，这个题就是2+3 < 1+7, pop out current max, push in 2+3, 重新sort
heap, 现在max 是1+5，再拿2+5和1+5比，外面的2+5大，直接output,要不再一轮的pop
, sort and push..
这个最好时间是m, 最差可能是m^2, 时间应该不是最优吧。。。 |
|
n****e
发帖数: 678 | 29 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
n****e
发帖数: 678 | 30 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
g*********e
发帖数: 14401 | 31 感觉可以用个maxHeap, 存每一个pair, 用pair的和来排序
另外用一个set 来记录已经存入heap的pair
每次从heap里拿出pair sum最大的，比如A(i), B(j)，然后把 和
), B(j+1)> 放入heap. (如果它们不在set里面的话）
初始化就是把放入heap.
然后抽取N次max，每次把新的candidate(s)放入heap |
|
f********x
发帖数: 2086 | 32
原来只是决定有没有winner的......
我一读这题都涉及纳什均衡的讨论，把我吓尿了....哈哈
只有一个heap么？能讲一下思路么？
我的想法，如果发现重复输入
1. 从heap中删除，然后找另一个结构记录重复数（因为都是整数，所以貌似bit不错）？
2. 如果不从heap删除，怎么在某固定时间点找winner呢？（heap的顶可能已经被标记
为重复了，导致可能必须遍历heap？）。 |
|
w******g
发帖数: 189 | 33 来自主题: JobHunting版 - G家面试题 @ silverwolf 这个分析很赞！不过就算不知道一共需要分析不多于 2K个坐标也可以有
klogk的算法：
1. create an empty heap
2. put x[0]y[0] into the heap
3. cnt =0
loop until cnt>=k:
pop e from heap, output e
cnt++
put neighbors of e (only two valid neighbors) into the heap
只要k步，heap里元素最多2k个，所以复杂度是O(klogk).
如果加上@ silverwolf 的分析，有没有更快的算法？例如O(k)? |
|
f******h
发帖数: 45 | 34 也找工作了一段时间了，从版上学了很多，上周G家面完了，求个bless。
之前的一些都挂了，还在继续找其他的。等定下来之后一定发面经回报本版。
谢谢大家啦！！
1. http://www.mitbbs.com/article_t/JobHunting/32005597.html
1) Implement a simple calculator (+,-,*,/);
2) Implement "+1" for a large integer;
3) How to match Ads to users;
4) How to extract useful information from a forum webpage (list all
kinds of useful signal you can think of)
5) How to detect the duplicate HTML pages (large scale);
6) Find all the paths between two places on Google map;
7)... 阅读全帖 |
|
b**********n
发帖数: 21 | 35 大家真的看懂我的答案了吗？感觉大家都没看懂，好桑心！
可能是我语言表达能力太差，我的意思是这题有nlog（n）的解法啊！
帖code
import headq
def scheduleMeeting(self, meetings):
meetings.sort(key = lambda x: x[0])
heap = []
cnt = 0
max_cnt = 0
for i in range(len(meetings)):
while heap and heap[0]<=meetings[i][0]:
heapq.heappop(heap)
cnt -= 1
cnt += 1
max_cnt = max(max_cnt, cnt)
heapq.heappush(heap, meetings[i][1])
return max_cnt
... 阅读全帖 |
|
l*******2
发帖数: 8 | 36 第二题想到一个解法，还是用2 heaps，但是heap里面不直接存number，存一个class，
class里面存number和这个number出现的次数。heap还是以number的值排序。
这样一来max heap和min heap里面总共的数出现的次数不一定相等，需要用两个number
来记一下。另外插入新数的时候比较麻烦，需要用一个hashmap来记一下number到class
的查找 |
|
发帖数: 1 | 37 不会的，假设当前结果是abc，现在queue里有a(4) b(0) c(0)，而此时heap已空。然后
从queue中取出a(4)，然后放入heap中，然后又从heap取出，count--，然后放回queue
里，现在是结果是abca，b(0) c(0) a(3)，那么新的循环开始时，取出b，发现count =
= 0，不放回heap中，heap空了，循环退出
最后的结果就是abca，与原长度不同，抛出异常 |
|
a***y
发帖数: 19743 | 38 ☆─────────────────────────────────────☆
sunfic (sunfic) 于 (Sun May 23 16:08:24 2010, 美东) 提到:
这个看起来牛逼哄哄的东西现在有两个瓶颈
一个是服务器端的运算能力，的确云计算可以通过数量换速度，但并不是所有的应用都
能这么干，特别是想要直接到桌面显示的程度。
一个是普通用户的网络带宽，大家可以做个简单的计算，要达到1024×768分辨率 60Hz
16bit色深需要的网络带宽是多少？考虑到比较成熟的视频压缩技术又要多少？
上面这两个瓶颈都是可以解决的，但是需要时间。那些说2-3年云计算成熟的人我不知
道你们的自信来自哪里
现阶段能够看到的唯一云应用就是云存储。
☆─────────────────────────────────────☆
meiyuan (美元) 于 (Sun May 23 16:31:33 2010, 美东) 提到:
我觉得云都是忽悠， 特别是以Cisco, Juni, HP,Goog带头的忽悠
现在1T, 2T的硬盘白菜价， 我老的A片，电视剧，盗版电影云存... 阅读全帖 |
|
m**c
发帖数: 90 | 39
Should it be "-Xmx300m"? It is not for increasing the heap size, it is
actually for limiting the heap size (maximum heap size). If you want to
increase initial heap size (minimum heap size), you need "-Xms128m". I don't
think you can build "-Xmx300m" option into either JVM or JAR files. |
|
c**a
发帖数: 316 | 40 来自主题: Programming版 - 请教算法题 在 大文本里找频率最高的1000 个词。
有个问题就是， 不管用 BST 还是 prefix tree，
如何 找到 频率最高的 1000 个词呢？
为了简单假设用 map;
如果保持一个min heap，长度为1000，
可以用 vector > ;
有 2种情况：
1. 当前词在 Heap 不在 heap 里， 这时 后者 不把当前词放进去， 后者把它和 root
交换(取决于根节点的值)
2. 如果在 Heap 里， 其相应节点的值要加 1
这时有两个问题，
1. 要找到 该节点
2. 破坏了 Heap 的结构， 如何恢复之？ |
|
I******c
发帖数: 163 | 41 两两合并应该比所有数列一起合并要好。合并的时候只要比较就可以了。另外一种思路
是用求rank来合并。看楼上有人提出heap. 我的另外一个想法就是分别建heap, 然后合
并heap. 这里的heap可能用Fibonacci Heaps比较好。
以上的想法是基于顺序的算法。 如果考虑到并行算法可能还有些小技巧可以使用，比
如先分小区间再合并，或者多路查找。 |
|
I******c
发帖数: 163 | 42 假设有N个数列，每个数列的元素个数是M. 那么两个数列合并的时间复杂度是O(M)，这
种合并需要进行（N/2+N/4+N/8...+1)=N次。所以总的时间复杂度是O(MN)
对于堆合并，如果使用binary heap的话，建堆需要N*O(M). 合并需要O(M)*N。所以总
的时间复杂度是O(MN)
如果使用Binomial heap的话，我不太确认建堆的时间复杂度，合并需要O(lgM)*N
还可以使用fibonacci heap, 不过时间复杂度用的是amortised, 不好比较。
使用Binomial heap和fibonacci heap实现的话可能需要额外空间。 |
|
G***l
发帖数: 355 | 43 Java已经学了不少C#的东西，或者用某些人都说法，抄。比如Java的annotation就是学
的C#的attribute，实际上微软在COM里就有类似的东西了。
网上看到这么一句话说的很好：
C# is not a copy of Java. C# is an evolution of the C-style languages, which
Java is also part of. C# was developed after Java, and learned a lot. A lot
of what they learned came from what IS in Java and a lot of what they
learned is what is NOT in Java. Every good language (every good product
really) learns from its predecessors and competitors. They find out what
makes the other languages most suc... 阅读全帖 |
|
t****t
发帖数: 6806 | 44 actually, the standard does say [first, last) must be a heap, but it also
says "Swaps the value in the location first with the value in the location
last - 1 and makes [first,last - 1) into a heap." and you know last[-1] (
the last element of a heap) is some arbitrary number anyway, be it a part of
heap or not.
when you know what is heap, you can make some creative use of existing code.
although purists like me will write my own code in this case.
BTW you don't need to read MSDN when you can re... 阅读全帖 |
|
l*******s
发帖数: 1258 | 45 说实话，我觉得这个没有必要上cluster和hadoop，有点太复杂了。
简单的方案反而更适合。
这不是个machine learning问题，而是个merge sorting问题。有可能我理解的不透彻
，纠正我。
从n个点中，找出top m个跟给定点距离最近的点。这就是个多路归并加堆排序啊。
单线程思路：
建一个Heap,size为m，然后就遍历数据集，把一个个点扔到Heap里排序，等遍历完了，
Heap里面的就是你要的KNN。复杂度为 O(nlogn)
多线程思路：
把数据集分成若干份，比如10份，把每份按照单线程思路进行堆排序，然后你会得到10
个size为m的heap，然后就是10路merge sorting。复杂度为O(nlogn/10) = O(nlogn)
具体实现：
python我不知道。Java里面直接用PriorityQueue这个class即可。
当然了，你要是足够自信，干脆自己实现一个heap，主要是heapify那块少难点。
多线程部分，python我也不大清楚。java的话，就用现成的线程池好了，省得你自己去
实现， java.util.concurrent... 阅读全帖 |
|
M*****c
发帖数: 2753 | 46 bless！
project,这个阿三比较刁钻，我解释得不是特别清楚，所以不太满意，因为我专业是通
信，所以又问了很多TCP/IP的问题，不过那个阿三也不太懂，所以我就随便忽悠了一下
。然后给我出了一个很简单的编程题，求N的阶乘。
，然后问我知道哪些sorting算法，我说了heap, merge, quick,以及在特定条件下可以
用bucket sort.然后他要求我设计一个交易系统，能够实时处理各种类型的order,比如
limit order, Market order, stop loss等等。我的思路是这样，建两个Heap,一个存
放limit buy order,一个存放limit sell order,当有新order输入是，首先判断能否直
接执行，如果不行，就存放在相应的Heap里面，另外对于stop loss order要另外建立
两个Heap存放。这样的话对order的处理时间
熟，所以估计是最后有拍板权的。随便问了我几个操作系统的问题，我答得还凑或，又
问了我在Wharton做的RA的项目，因为我考了CFA level1, 又问了我一个怎样用Call和
Put |
|
b*********n
发帖数: 1258 | 47 有人说“The answer to the median question is to actually use two heaps, a
min heap and a max heap. Google for "median heap"”但不是很明白
int |
|
k***e
发帖数: 556 | 48 今天想实现前两天大家讨论的minmaxheap找median，结果碰到一个问题。
I want pass function pointer to create a heap that has comparison function
as I defined. Thus I don't need both minHeap maxHeap. By the way, because I
have heap with template parameters, I also need function pointers with
template parameter.
It looks like:
template
class Heap {
private:
T* data;
public:
Heap(const vector& dataSrc, bool (*cmp)(T, T);
};
However, I cannot get a function pointer with template parameter. I really
had no idea h |
|
l******4
发帖数: 729 | 49
2个heap, 一个max, 一个min. 先向max里面push数。 当max里面的数多于min里面数+1
的时候，
pop max heap放入min heap. 中位数就是min heap的root |
|
m**q
发帖数: 189 | 50 想了想应该一个min heap和一个max值就行了，max值track当前
出现过的所有值中最大的。因为每次从heap中取最小的，所以
只要heap非空，max中记录的当前最大值一定保存在heap中。
删除原来max值不方便 |
|
