Discussion on Find the Running Median Challenge

Sort 239 Discussions, By:

2 weeks ago+ 0 comments

for c++ , all you need is this :

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<dbl>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

4 months ago+ 0 comments

this my solution but after the 2 case not working with more data :c help

def runningMedian(a):
    # Write your code here
    res = []
    temp = []
    count =  0
    for number in a:
        temp.append(number)
        temp = sorted(temp)
        size  = len(temp)
        middle =  round(size / 2)
        impar = (size % 2)

        if(impar == 1):
            currentSize =  size -1 
            middleImpar =  round(currentSize / 2)
            median = temp[middleImpar]
            res.append(float(median))
        else:
            median =  (temp[middle -1] + temp[middle]) / 2
            res.append(float(median))
            
    return res

5 months ago+ 1 comment

    public static PriorityQueue<int, int> MinHeap = new PriorityQueue<int, int>();

    public static PriorityQueue<int, int> MaxHeap = new PriorityQueue<int, int>(new IMaxCompareTo() );

    public static List<string> runningMedian(List<int> inputData)
    {       

        double median = 0;
        List<string> medians = new List<string>();            

        for (int i = 0; i < inputData.Count; i++)
        {    
            int currentValue = inputData[i];

            if (MaxHeap.Count == 0 || currentValue <= MaxHeap.Peek())
            {

                MaxHeap.Enqueue(currentValue, currentValue);
            }
            else { 

                MinHeap.Enqueue(currentValue, currentValue);
            }


            if ((MinHeap.Count - MaxHeap.Count) >= 2) {

                MaxHeap.Enqueue(MinHeap.Peek(), MinHeap.Peek());
                MinHeap.Dequeue();
            }

            else if ((MaxHeap.Count-MinHeap.Count)>=2) {

                MinHeap.Enqueue(MaxHeap.Peek(), MaxHeap.Peek());
                MaxHeap.Dequeue();

            }

            if (MinHeap.Count == MaxHeap.Count)
            {

                median = (double)(MinHeap.Peek() + MaxHeap.Peek()) / 2;
            }
            else if (MinHeap.Count > MaxHeap.Count)
            {

                median = MinHeap.Peek();
            }
            else {

                median = MaxHeap.Peek();

            }

            var stringM = median.ToString("0.0");
            medians.Add(stringM);

        }

        return medians;

    }



    public class IMaxCompareTo: IComparer<int>

    {
        public int Compare(int x, int y) => y.CompareTo(x);
    }

5 months ago+ 0 comments

Python Interview appropriate heap solution addNum: O(log N) findMedian: O(1) Total = O (log N)

from heapq import heappush, heappop
class Median:
    def __init__(self):
        self.maxHeap, self.minHeap = [], []
    
    def addNum(self, num):
        heappush(self.maxHeap, -num)
        
        if self.minHeap and self.maxHeap and -self.maxHeap[0] > self.minHeap[0]:
            heappush(self.minHeap, -heappop(self.maxHeap))
        
        if len(self.minHeap) > len(self.maxHeap) + 1:
            heappush(self.maxHeap, -heappop(self.minHeap))
        
        if len(self.maxHeap) > len(self.minHeap) + 1:
            heappush(self.minHeap, -heappop(self.maxHeap))
            
    def findMedian(self):
        if len(self.maxHeap) > len(self.minHeap):
            return float(-self.maxHeap[0])
        
        if len(self.maxHeap) < len(self.minHeap):
            return float(self.minHeap[0])
        else:
            return (self.minHeap[0] - self.maxHeap[0]) / 2
        
def runningMedian(a):
    obj = Median()
    result = list()
    for i in a:
        obj.addNum(i)
        result.append(obj.findMedian())
    return result

5 months ago+ 0 comments

def calculate_median(a):
    mid1 = a[len(a) // 2]
    mid2 = a[(len(a) - 1) // 2]
    return (mid1 + mid2) / 2

def sort_insert(arr, num):
    if not arr:
        arr.append(num)
        return

    start = 0
    end = len(arr) -1
    while start < end:
        mid = (end + start) // 2
        if arr[mid] < num:
            start = mid + 1
        elif arr[mid] >= num:
            end = mid - 1
    else:
        if num < arr[start]:
            arr.insert(start, num)
        else:
            arr.insert(start+1, num)
 
def runningMedian(a):
    arr = []
    result = []
    for i in range(len(a)):
        sort_insert(arr, a[i])
        result.append(calculate_median(arr))
    return result

Load more conversations