Running Median — Coding Question

Problem Statement:

You are given a stream of ’N’ integers. For every ‘i-th’ integer added to the running list of integers, print the resulting median.

Print only the integer part of the median.

Input Format :

The first line of input contains an integer ’N’, denoting the number of integers in the stream.

The second line of input contains ’N’ integers separated by a single space.

Output Format :

Print the running median for every integer added to the running list in one line (space-separated).

Sample Input 1 :

6
6 2 1 3 7 5

Sample Output 1 :

6 4 2 2 3 4

Explanation of Sample Output 1 :

S = {6}, median = 6
S = {6, 2} -> {2, 6}, median = 4
S = {6, 2, 1} -> {1, 2, 6}, median = 2
S = {6, 2, 1, 3} -> {1, 2, 3, 6}, median = 2
S = {6, 2, 1, 3, 7} -> {1, 2, 3, 6, 7}, median = 3
S = {6, 2, 1, 3, 7, 5} -> {1, 2, 3, 5, 6, 7}, median = 4

Sample Input 2 :

5
5 4 3 2 1

Sample Output 2 :

5 4 4 3 3

Code:

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Reshaping the Java Language on the Cloud

Golang GRPC Implementation

Azure Functions plus Docker

ZealousWeb Business Perpetuity Plan In COVID-19 — Zealousweb

Open source Alternative to Oracle Reports 2022

What is Domain Driven Design?

Working of GPIO

Upcoming New Pools to FarmHero Polygon

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

K Smallest Elements

Find the K-Beauty of a Number

[LeetCode] (Easy) 27. Remove Element

GREEDY ALGORITHMS FOR DUMMIES BY A DUMMY