w***y
发帖数: 6251 | 1 我就是自己做了一个main部分测试了一下, 其他部分都是copy书上的
import java.util.Comparator;
import java.util.PriorityQueue;
public class heap {
/*
* careercup里答案部分
*/
private Comparator maxHeapComparator, minHeapComparator;
private static PriorityQueue maxHeap;
private static PriorityQueue minHeap;
public static void addNewNumber(int randomNumber) {
if (maxHeap.size() == minHeap.size()) {
if ((minHeap.peek() != null) && randomNumber > minHeap.peek()) {... 阅读全帖 |
|
c*******r
发帖数: 610 | 2 错误在于你的Point 是class template, 不同于一般的class,你用的时候成了Point
type, 不是Point type. T需要你explicit或者编译器可以自动 deduct type.
下面是修改的代码：
#include
#include
#include
using namespace std;
template
class Point {
public:
T x;
T y;
Point() : x(0), y(0) {}
Point(T a, T b) : x(a), y(b) {}
};
template //如果没有这一行，编译器不知道T是什么type,所以这个函数必
须是
//function template
T distance(const Point& i) { //这里必须是const Point& , 可能因为
... 阅读全帖 |
|
b*******g
发帖数: 57 | 3 感谢前辈csiscoder经过实测的耐心细致的回复！给一千个赞！
运行了您修改的程序，bug free!
不过，还有个问题请求指点：
如果我将程序分别存在.h和.cpp文件里，为何有这样的报错呢：“error LNK2019:
unresolved external symbol”
--------------------------------------------------------------------
LeetCode.h内容为：
#include
#include
#include
template
class Point {
public:
T x;
T y;
Point() : x(0), y(0) {}
Point(T a, T b) : x(a), y(b) {}
};
//Find k closest points to origin
template
vector > findkClosestPoints(... 阅读全帖 |
|
k***7
发帖数: 6 | 4 窗口大小为N
list大小为N，顺序存放数值以及记录元素在heap中的存放的Element address[这个不
随堆的调整而变化]
min heap大小为 N/2
max heap大小为 N-N/2
median为max heap顶上元素，access time O(1)
维护堆：list[0]要被下一个新数n替代
if(list[0]<=median){//list[0] is in max heap
remove(list[0], maxHeap);
if(n>maxHeap.top()) {
insert(n, minHeap);
insert(minHeap.top(), maxHeap);
minHeap.pop();
} else {
insert(n, maxHeap);
}
} else { //list[o] is in min heap
remove(list[0], minHeap);
if(n>maxHeap.top()) {
insert(n, minHeap... 阅读全帖 |
|
c**a
发帖数: 316 | 5 下面代码编译时，提示说, std::vector::const_iterator Not a type
非常奇怪。。。
#include
#include
template
class MaxHeap
{
public:
typedef std::vector::const_iterator const_iterator;
MaxHeap(size_t n){v(n); size = 0;};
MaxHeap(const_iterator b,const_iterator e){v(b,e);size = e-b;
BuildHeap();};
MaxHeap(T c,size_t n){v(c,n);size = n};
MaxHeap(const MaxHeap& h){v = h.v; size = h.size;};
|
|
b*k
发帖数: 27 | 6 O(nlog(n)) solution:
Using DP in general:
sort (i, ai) by ai take O(nlog(n))
got (i_1, ai_1), (i_2, ai_2), .... (i_n, ai_n)
where ai_1 >= ai_2 >= ... ai_n
then keep a minHeap and maxHeap for i_k
maxInfo.cap = -INF;
for (each i_k from (i_1 to i_n))
i_min = minHeap.getMin();
i_max = maxHeap.getMax();
tmpCap = ai_k*(max(abs(i_k - i_min), abs(i_k - i_max)))
if (tmpCap > maxInfo.cap)
maxInfo.cap = tmpCap
//book keeping the i_k, and i_min or i_max
minHeap.insert(i_k)... 阅读全帖 |
|
s*****s
发帖数: 94 | 7 因为Priority queue默认是MAXHEAP，
所以可以写 priority_queue maxHeap;
一句话就能定义一个MAXHEAP。MINHEAP没有这样的便利啊，在C++里面没有。JAVA里面
可能两者都很
容易实现。所以想问C++中有啥不太麻烦的实现办法 |
|
f********e
发帖数: 166 | 8 我有一个超级傻逼的idea：
把矩形分成两个三角形，左上和右下
左上本来的数据是个minHeap
右下本来的数据是个maxHeap，
把左上的minHeap变成maxHeap,右下的maxHeap变成minHeap,
两个heap size一样就能找到median
时间复杂度 O(log(N^2)) |
|
p*****2
发帖数: 21240 | 9 来自主题: JobHunting版 - 讨论一道题
达到一定程度一次性丢掉就可以了。
if(maxheap.size()>N)
{
new maxheap
copy K elements into new maxheap
delete old max heap
} |
|
l********n
发帖数: 54 | 10 我对楼主TreeMap或者MinHeap & MaxHeap的方案有点疑问。
按我的理解，MaxHeap应该记录Max值的。如果在future的stream price大于heap top的
值，那么更新top.但假设t1的值是20, (t2, 15), (t3, 19),然后t3后的值都小于19。
那么在t1 expire后，max of t3就丢失了。
我能想的用minHeap & maxHeap的情况是用 linked list + heap。linked list 按照时
间顺序insert,当list head expire时候delete。每次insert & delete都fix heap. 不
知道楼主是不是这个意思。
我想到一中方案使用deque.
find max:
(1) 当stream data中一个值v来的时候，不断pop_back queue中所有比v小的。
(2) query max的时候，check queue front的data是否expire, 如果expire pop_front
到12 months内的data,那就是max。有点leetco... 阅读全帖 |
|
p*****3
发帖数: 488 | 11 来自主题: JobHunting版 - 周末上道题 给一个很大的maxHeap, size n, 数组形式表达，array A
给一个k+constant的数组 Array B，constant<< k << n
求kth max in maxHeap，不能改变maxHeap (Array A只读) |
|
k******e
发帖数: 19 | 12
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
k******e
发帖数: 19 | 13
情况
你这明显是先入为主了，面试最忌讳的就是先入为主，不跟着面试官的思路来想。
这问题是个很基本的东西，MINHEAP和MAXHEAP都可以。基本就是有N个ITEM，找其中的
TOP K的问题。
- 用MINHEAP的话，空间复杂度是O（K）， 时间复杂度是O（NlogK）。
这个方法适用于当数据不能PRELOAD进MEMORY，比如说数据是从一个STREAM来的。你
就是先建立一个大小是K的MINHEAP， 在ROOT的就是最小的，其他K-1个都比ROOT大，然
后从省下的N-K个里一个一个取，和你的ROOT比较，如果比ROOT小的就丢掉，比ROOT大
的就REPLACE ROOT，然后将其 SIFT DOWN。
－ 用MAXHEAP的话，空间复杂度是O（N）， 时间复杂度是 O（KlogN）。
这个办法只能用在N不是太大的时候，可以先HEAPIFY，用时O（N）。现在你的ROOT
是最大的，把ROOT拿掉放进你的RESULT里，你的HEAP的ROOT空了，把最后一个元素放进
ROOT，SIFT DOWN， 又得到一个MAXHEAP，重复刚才的操作K次，得到你的RESU... 阅读全帖 |
|
d*******e
发帖数: 24 | 14 建立两个heap，一个maxheap，一个minheap，保证maxheap里的数比minheap里的小，两
个heap大小相当。
这样heap的根就是中位数。每插一个数的cost应该是O(log n) |
|
s******n
发帖数: 3946 | 15 window分成1个maxheap紧接1个minheap，保持2个heap的大小最多差1，maxheap的最大
值小于等于minheap的最小值。复杂度每插入一个数是log(L)，L是window的大小。 |
|
z********c
发帖数: 72 | 16 来自主题: JobHunting版 - 讨论一道题 每次都要添加元素到maxheap里么？那MaxHeap的大小超过了K怎么办？ |
|
f*****e
发帖数: 2992 | 17 复杂度:
没有，每次pop minheap and maxheap and insert minheap and maxheap操作耗时log(
n)，每次operation，至少有一个数组的size要减半，如果每个数组的size都是n，把一
个数组削的只剩一个要log(n)，然后有n个数组，所以nlogn。nlogn * logn = nlogn^2
medi
目的
常大
的k |
|
o***d
发帖数: 313 | 18 我怎么觉得是maxheap阿?
这个问题似乎是这样的:
如果每秒钟来1000个股票的现在的价格,要求显示今天股票涨幅最多的5支.
说个错误的做法:
第一次来数据的时候,把1000个股票的前5个找到,放到sorted array里.
然后,下次再来的1000个股票,okay,挨个算涨幅,然后跟现在的5支挨个比较?然后再怎么
维护这个sorted array? time complexity太高了吧?每次要insert and then rearrang
ement.
正确的做法是用maxheap??? |
|
p*****2
发帖数: 21240 | 19
我现在是这么输出的，你看有什么问题吗？今天搞了一个上午了。Heap里存的是Long型
if(maxCount>minCount) return maxHeap.head.toString
else{
val sum=maxHeap.head+minHeap.head
if(sum%2==0) return (sum/2).toString
else return (sum/2).toString+".5"
} |
|
p*****2
发帖数: 21240 | 20 改了改，还是有一个test case fail。这个输出有问题吗？
if(maxCount>minCount) return maxHeap.head.toString
else{
val sum:Long=maxHeap.head+minHeap.head
if(sum%2==0) return (sum/2).toString
else return "%.1f".format(sum.toDouble/2)
} |
|
u*****o
发帖数: 1224 | 21 多谢总结，但不是太明白第一题为什space complexity 是o(n)
按说要维护两个堆，空间很大啊
比如说前20个URL，最长的放在minheap, 19个放在maxheap, 用hashmap记录average
再进来20个，最长的两个放在minheap, 38个放在maxheap,update hashtable.
随着数据越来越多，两个堆就像堆雪球越来越大啊，虽然随时可以从hashtable读当前
average，但heap要放在memory不是太可能吧，难道有什么flushing system?
). |
|
k*******r
发帖数: 355 | 22 我知道无限stream中维持topK frequent query是用hashtable加一个大小为K的minheap
但sliding window中维持topk频繁的query这应该怎么做？如果用一个大小为K的
minheap再加一个大小为N-k的maxheap, 再加上hash table应该可以搞定。但通常N>>K
所以维持N-k的maxheap代价太大。
这题标准答案应该是什么样的？ |
|
d****n
发帖数: 397 | 23 用两个heap.一个max heap，一个min heap， maxheap size ＝ min heap size 或者
maxheap size ＝ minheapsize ＋ 1.
java implementation
public class Solution {
/**
* @param nums: A list of integers.
* @return: the median of numbers
*/
public int[] medianII(int[] nums) {
// write your code here
PriorityQueue pmin = new PriorityQueue ();
PriorityQueue pmax = new PriorityQueue (10, new
MaxComparator());
int i, l = nums.l... 阅读全帖 |
|
p********7
发帖数: 183 | 24 做题作到的，发现不会。。。问题很简单，希望大家指点一下，卡的很难受
建了一个Student的class，有名字，成绩。
然后又建了一个class，constructor如下
public MaxHeap(Collection collection)
请问我调用的时候怎么写？
我想大概是下面这样的，可是一直抱错。。。卡勒。请帮忙看看
xx= new MaxHeap(("Susan",60), ("John,70)); |
|
k***e
发帖数: 556 | 25 今天想实现前两天大家讨论的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 |
|
H*M
发帖数: 1268 | 26 你这是好学还是什么？
如果你不想自己写的话，STL里有现成的priority_queue，稍微重写个compare的functo
r就可以用成minHeap和maxHeap了
I |
|
B*****t
发帖数: 335 | 27 code
struct Node {
int val, ix;
bool operator>(const Node &ot) {
return val>ot.val;
}
Node(int _v=0, int _ix=0):val(_v), ix(_ix){}
};
int a[N]={...}, b[N]={...}
int i, j, p[N] = {0}, res[N]={0};;
MaxHeap hp;
for(i=0; i
hp.insert(Node(a[i]+b[0], i));
}
Node tmp = hp.pop();
p[tmp.ix]++;
res[0] = tmp.val;
int ix = tmp.ix;
for(i=1; i
hp.insert(Node(a[ix]+b[p[ix]], ix));
tmp = hp.pop(); |
|
n*******s
发帖数: 482 | 28 第二题
data=[4,1,2,2,3,1,2,1,4]
def find_recurword(data):
a1 = 0
a2 = 0
i = 0
while i
pre1 = i - a1*2 -1
pre2 = i - a2*2 - 2
if pre1 >= 0 :
if data[pre1] == data[i] :
a1 = a1+1
if pre1 == 0:
return 1
else:
a1 = 0
if pre2 >= 0 :
if data[pre2] == data[i] :
a2 = a2 +1
if pre2 == 0:
return ... 阅读全帖 |
|
p********7
发帖数: 549 | 29 heap 不合适，因为你要max 和minheap，maxheap更新了，minheap也需要更新，而且删除原来max值不方便 |
|
K******g
发帖数: 1870 | 30 面试的是美国人，英语很好
一上来就问为什么申请twitter
然后马上coding，实现strstr（）。还没有写完，就问我complexity。我说是O(nm),他
追问一下，什么情况下是exactly O（nm)，我说是当str2不是str1的substring的时候。
写完代码后，就问优化。首先是算法上，我说了KMP，然后要我大概讲一下KMP的思路，
我只记得有个preprocess的过程，把一个string的prefix弄到一个array里去。然后又
问，怎么从程序结构上优化，比如str1非常非常长，我就说分成很多chunks，放到不同
的machine上去跑。他又说，那样会有问题，有可能在分chunks的时候把一个substring
的match打断，问我怎么办。我没有答上来，后来想通了，其实很简单。在分chunk的时
候，把断开的地方的左边和右边一定范围内，再弄一个chunk出来，这样子如果有match
的话，就逃不掉了。
接下来，就是设计问题。许多machine，每个machine上有许多user，每个user有很多
followers，怎么统计每个user的平均foll... 阅读全帖 |
|
z****o
发帖数: 78 | 31 追梦很sharp啊~ 的确是这个地方没有说的够清楚。
我写一个证明，正确性可以保证，但是是临时想的有可能绕弯子了。
并且这个证明不能用来估计复杂度。
重新证明可终止：
Let me prove in details:
Lemma 1. 算法在有限次会终止。
Lemma 1.1 每次交换后新生成的两条边长均小于原有的两条边长。（易知）
Lemma 1.2 一个交叉 B1-R1,B2-R2 在交换分离之后仅可能重现有限次。
Lemma 1.2.1 一条边在被删除后只能重构有限次。
Proof. 数学归纳法
注： 总假设 B1-R1 的长度>=B2-R2的长度，对证明无影响。
base case: B1-R1 是初始情况下最长的边，B1-R1 若被删除，
只能重构有... 阅读全帖 |
|
w**7
发帖数: 71 | 32 面试加州P公司
一面是华人GG
1. 给个数组，给个target, 求找两个数和等于target
然后拓展到找3个数，4个数，分析复杂度
这经典题，没啥说的，hashmap
一个金字塔，有n层，第i层有i个数，有点类似倒置的杨辉三角那种
让你找出一条路从塔顶到塔底，使得这条路链接的节点和最小
这个用hashmap存层数和路径长度值，从底层向上遍历
二面是个白人
2. 给个数组，没排序，已知数组中每个元素距离排序以后的位置最多是k，让你给这个
数组排序
这就是弄个k size 的min-maxheap, 然后先把前0-k-1个元素放到heap里，然后从数组K
位置开始，从heap中取出最小，然后从数组取一个放到heap里，最后O(nlogk)排好
我把方法一说，interviewer感觉可以，说那你写个code发过来吧，然后do you have
any questions。没20分钟就结束了
两面感觉都没啥问题，最后周一就收thank you letter了。有好几次都这样，感觉
technical 题目都没啥问题，两面就悲剧，求经验……move on到麻木了，唉 |
|
s********x
发帖数: 914 | 33 // MaxHeap: heapArray starts from index 0
public static void heapSort(int[] a){
// Trickling Down in Place: start at node n/2-1, the rightmost node
with children
// O(n/2*log(n))
for (int i=(a.length/2-1) ; i>=0 ; i--)
trickleDown(a,i, a.length);
// remove max from heap and insert it at the end
// O(n*log(n))
for (int i= a.length - 1; i> 0; i--){
int max = a[0];
a[0] = a[i];
trickleDown(a,0, i... 阅读全帖 |
|
s*****s
发帖数: 94 | 34 c++ STL中的Priority queue直接可以实现MaxHeap。
有什么简单的方向实现MinHeap么？
发现面试题中有时候会需要用到MinHeap,但是不是主要考察MinHeap,所以不想现场把大
量的时间花在
实现MinHeap上 |
|
c****p
发帖数: 6474 | 35 minheap 和maxheap在实现方法上有什么差别么。。。 |
|
c****p
发帖数: 6474 | 36 key值取负，然后放到maxheap里，实际上不就成了minheap了么。
取值的时候再变回来。 |
|
f*******t
发帖数: 7549 | 37 感觉我想的解法好naive..
内存里放一个minheap，从大到小过滤，内存里的heap转成maxheap存进file
要扫描O(n/m)遍文件，n是原文件大小，m是内存大小 |
|
k****n
发帖数: 369 | 38 来自主题: JobHunting版 - 请教一道题 这个是经典题了，我都怀疑是不是还有面试官会问
hashtable的部分是必须的, O(n)
对整个数组用maxHeap做k次siftdown，O(m+klogm)
一般会比mlogk好一点。
了，
为O |
|
k****n
发帖数: 369 | 39 说的可能是两回事，求k个最大值的话
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了 |
|
k****n
发帖数: 369 | 40 哈哈哈，看错了。。。
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了 |
|
k****n
发帖数: 369 | 41 说的可能是两回事，求k个最大值的话
如果是用一个k个元素的heap，那应该是minheap
每次把当前最小值扔掉，剩下的是大的
如果是整个数组heapify的话，那就是maxheap了 |
|
k****n
发帖数: 369 | 42 哈哈哈，看错了。。。
如果是m个最大元素，用k-way merge的办法的话，的确就是maxheap了 |
|
m*****k
发帖数: 731 | 43 amazonLocal 组，
上上周3面的，本周2收到据信，攒人品，上面经。
印女，PM，
1. copy linked list with random link in each node. 我给的答案不是回家后
google到的那个big linklist then separate， 我让原node的random link point to
its clone。
这样也能达到要求但改变了原始link,她也没反对。
2. code IsBST,
我写了个递归，还需要看root结点是否大于left child's subtree max, 以及是否小于
right child's subtree min, 被她问到复杂度， 指出非最优，重新想了一会， 说那
就inorder traversal , 每次和前一个值比一下，先给一个Prev=-infinity, 在白板上
纠结了一阵写出了和http://www.mitbbs.com/article/JobHunting/31990685_3.html相似的code.不过我是把prev传入IsBST,而且用
prev = +infinit... 阅读全帖 |
|
s******n
发帖数: 3946 | 44 应该是用size为K的MaxHeap，Head是最小k个里最大的一个。 |
|
s*******f
发帖数: 1114 | 45 basically idea is maxheap + minheap as u, but can be simpler.
i lost in this problem, though i figured it out at last. |
|
d****n
发帖数: 56 | 46 一天三面，都是 SUMMER INTERN。
Amazon的第二个电话，又是一个NATIVE，又是开始就让我CODING， 问题很简单，判断
二叉树是不是BST,写了个RECURSION的，念代码。 找N个星球最近的一个，用的MAXHEAP
, 分析复杂度，然后就说“THAT'S ALL THE QUESTIONS I HAVE FOR YOU TODAY" 不知
道这种半小时两道题的面试是不是好兆头，求分析~
BLESS BLESS BLESS BLESS AMAZON是目前最满意的一家了 -----华丽的分割线
下午面了ON CAMPUS 的ITG，2VS1， 问题很脑残，c++多重继承会有什么问题，如何判
断一个链表是CIRCUS的， 设计一个VENDING SYSTEM, 如何不用TEMP和BIT OPT交换两个
数。 下一部应该是ONSITE。 感觉公司的技术不强。
然后是一个YAHOO的HIRING MANAGER的BEHAVIOR INTERVIEW。 昨天被一个PM还是神马的
联系了一下，聊了以前的项目，问了几个SQL，JOIN之类的问题。感觉YAHOO的电面非常
的非... 阅读全帖 |
|
C***U
发帖数: 2406 | 47 amazon现在还在找summer intern么？
之前网上投了
没消息。。。
MAXHEAP |
|
w***y
发帖数: 6251 | 48 就是那个用minheap + maxheap做的.
Numbers are randomly generated and passed to a method. Write a program to
find and maintain the median value as new values are generated.
答案是不是不对啊, 我是说那段程序. 我看的是2010年的4th edition, 题目编号是20.
9
我看那个用PriorityQueue做heap, 觉得不对劲啊. 试着运行了一下那一段程序, 结果
也跟我想的不一样.
不知道是不是我理解有误啊.
我等下把程序贴在2楼 |
|
s******n
发帖数: 3946 | 49 第二题，就是搞2个Heap来实现。
Heap1：MaxHeap, Heap2：MinHeap，保持Heap1.size==Heap2.size或者Heap1.size==
Heap2.size+1
void addNum(int num) {
if (Heap1.size==Heap2.size+1) {
if (num<=Heap1.maxValue()) {
int heap1MaxValue = Heap1.pop();
Heap2.add(heap1MaxValue);
Heap1.add(num);
} else Heap2.add(num);
} else {
if (num>=Heap2.MinValue()) {
int heap2MinValue = Heap2.pop();
Heap1.add(heap2MinValue);
Heap2.add(num);
} else Heap1.add(num);
}
}
多个机器的问题：从每个机器读一个block过来，效率比较好 |
|
z*********8
发帖数: 2070 | 50 求前1000个用 maxheap就行了， 求median就只能那么做 |
|
