Given that integers are read from a data stream. Find median of elements read so for in efficient way. For example, median of the stream, A = [1, 5, 3, 2, 6, 2, 3] is = 3. Note that we need to find the running median at any time of the stream. That is each […]
Tag Archives: median
Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array. For example, A= 2, 4, 5, 6 1, 2, 2 ,4 3, 4, 4, 5 1, 2 , 3, 3 Then the merged array would be [1, 1, 2, 2 ,2, 2, 3, 3, 3, 4, 4, […]
Given an array of integer. Find the kth smallest element in the array in a most efficient manner. For example: A = [2, 1, 0, 3, -1, 3] and k=3 then the 3rd smallest element is 1. This is also (6-3) = 3rd largest element. A trivial solution is to sort the array. But question […]