Can you explain the logic on how to find the median of a running stream of integers at any point ( online algorithm ) and also how to think the same ( under pressure ) at the time of interview ?
Interview question
Basically, you have to solve this question using the heap, where you will maintain two heaps, min heap and max heap, and running stream will either add numbers greater than original median or numbers which are less than original median.thus all numbers which are less than median will be stored in one heap, and the others will be store in another heap,
thus if you have stream as : -2, 0, 1, 3 , 4 , 5, 12, 100, 200, and if median is 4,
then immediate left no will be stored in maxheap and immediate right no will be stored in minheap
thus both heaps will be of same size, and at any point if the size of any of the heap increases, then that element will be median.