Describe the most time-efficient way to implement the operations listed below an

Question

Describe the most time-efficient way to implement the operations listed below and give the order (Big O) in terms of N.

a. Given a queue of N integers, find the minimum value in the queue and delete it from the queue. When you finish, the rest of the values must be in their original order.

b. Given a binary search tree of N integers, find the median value and delete it. For this question, assume N is odd. [Note: If the values were in a sorted array, the median value would be at index (N - 1) / 2. For example, the median of {1, 4, 9, 10, 17} is at (5 - 1) / 2 = 2 which is 9.] Hint: You need to consider the elements of the tree in order of their values.

Explanation / Answer

To find the minimum element of the queue, look at the smallest two elements of the individual min-stacks, then take the minimum of those two values..

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)].

Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one.

E.g for a pop request, moving all the elements from first stack[(4,4), (2,2), (5,2), (1,1)], the second stack would be [(1,1), (5,1), (2,1), (4,1)]. and now return top element from second stack.

To find a median of stream of integers we can use the concept of heaps:
Insert the first element in either of the below mentioned heaps and this number is the current median. Then compare the second incoming number with the first one. If the number is more then insert it in the HeapLow and if it less then insert it in the HeapMax.
Keep two heaps and keep on adding the numbers in these heaps as they come. If the numbers in the two heaps are even then you just take the average of the roots of the two heaps. Otherwise if they are unenven and difference is one in both the heaps take the number from the heap which has a higher count. If difference between their counts is more than one then take a number from the heap which has more elements and insert it into the another heap. And then find the median.

1. HeapLow: This heap is the max heap of the smaller of the numbers in the input stream so far
2. HeapMin: This heap is the min heap of the maximum of the numbers in the input stream so far ..

This problem can be also solved with a Binary Search Tree and an integer keeping count of number of elements received so far.

1. Insert every incoming element in the Binary Search Tree. Using self balancing tree like AVL tree or Red-Black BST is even better option.
Worst Case Time complexity: O(N)

2. Also every time a new element is received and added to the BST, increment the input counter (which keeps track of number of inputs so far) by 1.
Time complexity: O(1)

3. When the query is made for median, perform an inorder traversal of the BST and stop when the in order element count is n/2.
The median is, if the elements received so far are odd, the median is n/2th element. If the elements received so far are even, then the median is (n-1 th element) + (n th element) / 2

Time complexity: O(N)
.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.