Find the Running Median Data Structures and Algorithm Cognizant Handson Solution

In this post, we are going to cover the Data Structures & Algorithms Find the Running Median hands-on solution asked in Cognizant.

The question of this hands-on is available here.

Steps to upload answer in GenC Platform:

1. Click on this link.
2. Insert the below code in the Hacker Rank code editor.
3. Compile & Execute the Code.
4. Take a screenshot of the successful execution.
5. And upload the screenshot to the platform.

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'runningMedian' function below.
     *
     * The function is expected to return a DOUBLE_ARRAY.
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static List<Double> runningMedian(List<Integer> a) {
    // Write your code here
        PriorityQueue<Integer> left = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> right = new PriorityQueue<>();
        List<Double> res = new ArrayList<>();
        for (int i = 0; i < a.size(); i++) {
            int tmp = a.get(i);
            left.add(tmp);
            if (left.size() - right.size() > 1) { right.add(left.poll()); }
            if (right.size() != 0 && left.peek() > right.peek()) {
                left.add(right.poll());
                right.add(left.poll());
            }

            double median;
            if (left.size() > right.size()) {
                median = 1.0 * left.peek();
            } else {
                median = (left.peek() + right.peek()) / 2.0;
            }

            res.add(median);
        }
        return res;
    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int aCount = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = IntStream.range(0, aCount).mapToObj(i -> {
            try {
                return bufferedReader.readLine().replaceAll("\\s+$", "");
            } catch (IOException ex) {
                throw new RuntimeException(ex);
            }
        })
            .map(String::trim)
            .map(Integer::parseInt)
            .collect(toList());

        List<Double> result = Result.runningMedian(a);

        bufferedWriter.write(
            result.stream()
                .map(Object::toString)
                .collect(joining("\n"))
            + "\n"
        );

        bufferedReader.close();
        bufferedWriter.close();
    }
}