Heaps shortlist

[•Cosmin]

http://www.infoarena.ro/blog/heaps-shortlist

[•AlexandruValeanu]

2. We insert in a min-heap the first element from each vector. When we extract the minimum we also add in the heap the next element from the corresponding vector.
Complexity: O(n*k*logn)

4. We maintain a max-heap. First of all, we add in this heap the first k elements from the vector. For each element from k+1 to n we check if the current element is lower than the element from heap's root. If so, we extract the top-element and insert the new element.
Complexity: O(n+k*logk)

Another solution which uses the selection algorithm works in O(n).

[•loses]

#1 it depends how do you define efficient
Do your heap needs to occupy O(N) memory with the 2 * nod + 1 trick for sons, or it should be just a tree with heap property

#2 keep a heap with the first element of every array.
take the smallers one from that heap and put the next element from that array into the heap
O(sum_or_arrays * logK)

#3 keep a min-heap with the first k elements in it. Erase the top, put it in #1 and put #k+1 into the heap -> repeat O(NlogK)

#4 -> you can keep a max-heap limited to size k
insert into heep. while(heap.size() > k) { heap.pop(); }
O(N + NlogK)

ORRRRR you can use kTh element and then sort the first k elements of the array.
it depends if the first K elements should be sorted or not O(N) vs O(N + KlogK)

#5 > or >= ?

#6 I won't fall for that problem AGAIN
someone told me like 3 years ago. From what I heard it was given to Bogdan Tataroiu at his Google/Dropbox interview(I don't remember). And there is the O(KlogK) solution, but there is another O(K) solution. I thought about if for 2 years, and then someone told me it's a cool paper and stuff ..
But there is O(K)

#7 immagine that you have the first 8 numbers computed

Cod:

1 2 3 4 6 8 9 12
           3 2

Than we want to expand this sequence further, and if we want to expand it with 2, the next element whould be at least [12 / 2] + 1
in this case, 8, since we can't make 7
The same applies for 3, [12 / 3] + 1 = 5 -> 6

now we just take the smallest of these numbers and go on.
We don't have to binary search this positions, since they will only grow.
We can just keep 2 pointers at every moment and just itterate throu them.
-> O(N) and prints first N elements made out of 2 and 3
Here is some python code for it

Cod:

#n = int(raw_input())
n = 5000000

exp = [2, 3]
where = [0, 0]
rez = [1]
now = [0, 0]

for i in range(n - 1):
	for i in range(2):
		now[i] = exp[i] * rez[where[i]]
	mn = min(now)
	rez.append(mn)
	for i in range(2):
		if now[i] == mn:
			where[i] += 1

print rez

OFFTOPIC
if you just want the Nthelement, or the sum of the first N elements for 2 factors you can get that in
O(sqrt(N)*logN)
I made a test for factors 2, 3 and 5 and the algo runs in O(N^(2/3) * logN)
and that is a big improvement, since the memory is O(1)

Here is some C++ code for factors (2, 3, 5) and it runs is 0.4 for 10^8 -> BEAT THAT O(N)
http://ideone.com/wwn5QD

I really like this problem

#8
We have
maxHeap - minHeap
if we have 2*n elements
we keep the lower N elements in maxHeap, than the biggest N elements in the minHeap

if the 2 heaps are equal, the medial is maxHeap.top()
else, it is the.top() of the biggest Heap.
Now we want to keep the abs(maxHeap.size() - minHeap.size()) <= 1
if that overflows, we just.pop one and push the value in the other heap.

#9 problem #9 and #5 are mostly the same, since in #9 C[j] = A + B[j] and C is a Young Tableau

#10
The solution should be better than O(K), right?

[•mihaif3]

Isn't 7 solved with a Young Tableau too ?

[•loses]

#7 can be solved with that, but IMO the array solution with 2 pointers is better.

For the Young Tableau you can use binary search to search the value, than O(N) to see how many values <= that are in the array


If you want sth that goes well with K, you can go sth like O(KlogN), keeping on every row the first element, like in the merge or N arrays problem
But you are not using the fact that they are sorted on rows too .. i will think about this a lil bit more, but the bs solution seems legit enought

[•loses]

  Thanks Cosmin for all these beautiful problems and all your involvement in Infoarena

[•mihaif3]

I'd solve the Young Tableau problem similar to the merge N arrays problem, but with a twist: starting with position (0,0), at each step, I remove the min element at (i,j) and add into my heap two more items - elements with positions (i+1,j) and (i,j+1). O(K logK), if this is correct.

[•loses]

It's ok, but you need to take care when pushing the children in the heap; you need to keep track of the children which are inside the heap.
for example if you expand the elements in this order
125
346
789

the element 4 will be expanded from 2 and 3
this problem is for all the elements; at the end of the day you heap will have double the size, because all the elements which are not on raw 1 or col 1 will be expanded 2 times, but this is not a problem after all.

And logK vs logN is not such a big deal after all
if K >= N you will have logN anyway

[•Cosmin]

1. O(n) remains unsolved.
2. O(n log k) solved.
3. O(n log k) solved.
4. Solved in O(n log k) and O(k). One can actually solve it in O(n) time and O(k) additional space: http://www.infoarena.ro/blog/problema-saptamanii-stream-solutie
5. See 9.
6. Solved in O(k log k). One can actually solve it in O(k) (http://www.sciencedirect.com/science/article/pii/S0890540183710308)
7. O(n) solved.
8. Solved.
9. Solved in O(k log k) but one can solve it in O(k) (http://www.cse.yorku.ca/~andy/pubs/X+Y.pdf)
10. Remains unsolved. An O(k) solution is fine.

Good job so far.

[•dnprx]

Solution to Problem#1

Suppose we have the function DownHeap(k, n). This function takes A[k] and unifies the heap A[2*k] with the heap A[2*k+1]. Using this function, we can create now the entire heap with the function

Cod:

void MakeHeap()
{
   for (i=n/2; i>=1; i--)
	DownHeap(i, n);
}

Let’s consider h=log(n) the number of levels in this heap. DownHeap(k, n) function uses only nodes from the levels 0..h-1. For each node from the level i there are al most h-i descents in heap. But on the level i and are 2^i nodes. So the number of operations is given by the sum ((h-i) * 2^i), i = 0..h-1. Elementary mathematical calculations show that this amount is less than 2*n. So the complexity of creating heap is O(n).

Interestingly, a former student of mine received at an interview the following problem: Given an array of length n which is the inorder-traversal of a binary tree, organize the array as a min-heap in O (n) time complexity. But the problem that I have just given the solution is known to have O (n) time complexity. Strange problem, in my opinion.

I apologize for my very bad English.

[•AlexandruValeanu]

10. The problem can be solved using DFS. We start from the root. If root's value is lower than X we increase a counter and run the algorithm for root's children.
The algorithm will be stopped if the counter is greater than k. This means that the kth smallest element in the heap is smaller than X.
Complexity: O(k)