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. Lettingxi denote the i th number of the file, the k th 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 ):

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

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

Algorithm ( naive ):

- sum=0, input a[n]
- for each input a[i]
- Sort a[0..i]
- sum+=a[i/2]
- 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); } }

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

ReplyDeleteYeah I know it. I just published it as a

Deleteproof of concept... :)