Programming Geek
Rated 4.7/5 based on 1446 reviews

Median Maintenance

The problem statement is taken from Coursera programming assignment #6 .

Download the text file here.

The goal of this problem is to implement the "Median Maintenance" algorithm . The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one. Letting xi denote the ith number of the file, the kth median mk is defined as the median of the numbers x1,,xk. (So, if k is odd, then mk is ((k+1)/2)th smallest number among x1,,xk; if k is even, then mk is the (k/2)th smallest number among x1,,xk.)

In the box below you should type the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits). That is, you should compute (m1+m2+m3++m10000)mod10000.

Algorithm ( naive ):
   
  1. sum=0, input a[n]
  2. for each input a[i]
    1. Sort a[0..i]
    2. sum+=a[i/2]
  3. print sum%10000
JAVA implementation : 

/**
 *
 * @author VIK VIKASH VIKKU
 */
import java.util.Arrays;
import java.util.Scanner;

public class MedianMaintenance {

    public static void main(String[] args) {
        int[] list = new int[10000];
        Scanner sc = new Scanner(System.in);
        long sum = 0;

        for (int i = 0; i < list.length; i++) {

            list[i] = sc.nextInt();
            Arrays.sort(list, 0, i+1);
            sum+=list[i/2];
        }
        System.out.println(sum%10000);

    }
}

2 comments :

  1. Hello, I don't want to spoil your mood, but this is the worst implementation of this problem. I think you didn't understand the purpose of this algorithm, you was supposed to implement it using two heaps, a good explanation can be found here http://stackoverflow.com/questions/10657503/find-running-median-from-a-stream-of-integers

    ReplyDelete
    Replies
    1. Yeah I know it. I just published it as a
      proof of concept... :)

      Delete