ACE Test Series

Question

A ) 

B ) 

C ) 

D ) 

Comments

What explanation they gave for option d?

---

> Use an array of size k as a min heap.
> With every element, compare it with min of heap, if found larger, insert in heap, else, ignore.
> Once the heap is full, if found larger than min of heap, delete the min and insert.

N = {8,4,2,6,1,5,6,9,10,3}, let k = 3 K = {}

N = {8,4,2,6,1,5,6,9,10,3} K ={8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {2,4,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {4,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {5,6,8}

N = {8,4,2,6,1,5,6,9,10,3} K = {6,8,9}

 

N = {8,4,2,6,1,5,6,9,10,3} K = {8,9,10}

 

N = {8,4,2,6,1,5,6,9,10,3} K = {8,9,10}

---

@amitraj123 They have given this explanation.

Answer 1

Answer will be max heap of size n.

We can access first max element from max heap in O(1). 

After that just delete k max element from heap and after every delete heapify the tree make sure it is max heap, which will take O(logn). 

So for K element time complexity will be O(klogn). And K is constant so O(logn).  

Comments

But are we allowed to modify the array’s contents?

---

But they can be copied right? Just take the n elements, copy them to an array, buildMaxHeap in O(N). I am not sure if I get your question correctly or maybe I am going wrong somewhere?

---

Yeah, I understand now, thanks!

Answer 2

Min Heap of Size of K. If size exeeds k, pop the top element out of Min heap