Problem
:
The
Median
In general, t
he Median is the
"middle
"
of a
sorted
list of numbers
.
For example, for the following list of
sorted
number
: 10
,
11
, 13,
15,
16,
2
3, 26
, the median is
15
as we have
a total of
7 numbers
and after sorting 15 is
the
mid
dle
number on this list.
Ho
wever, if we hav
e even number of items,
we have two number
s in the
middle and in that case the median will be the average of those t
wo numbers.
In this assig
nment,
you will receive a
n
unordered
stream of
distinct
strings
where the strin
gs will contain on
ly
single word and
lower case letters
. T
he maximum number of characters of a string can be
50. As soon as you
receive a string, you need to print the median
of the strings you have received
so far
.
If you have even number
of strings,
you should print bot
h of the middle
strings
in sorted order (based on the following
definition
)
as
part o
f the Med
ian.
I
n order to
compare strings,
you will use the following rule:
•
Given strings a and b, we say a < b="" if="" a="" has="" fewer="" characters="" than="">
•
If two strings a and b have the same length, we say a < b="" if="" a="" comes="" before="" b="" in="" alphabetical="">
Example:
Let
’
s say
the dat
a str
eam
are
orange,
apple,
app, mango
,
cherry
,
peach
,
melon
.
Afte
r
reading the first
item
“
orange
”

> th
e median is
“
orange
”
Afte
r
reading the
second
item
“
apple
”

> th
e median is
“
apple
orange
”
(according to our definition
as we have even
number of items and apple <>
Afte
r
reading the
third
item
“
app
”

> the median is
“
apple
”
Afte
r
reading the
fourth
item
“
mango
”

> the median is
“apple
mango
”
After reading the fifth item "
cherry
”

> th
e me
dian is
“
mango
”
After reading the
sixth
item "
peach
”

> th
e me
dian is
“mango
peach
”
After reading the
seventh
item "
melong
”

> th
e me
dian is
“
melon
”
Implementation restriction
and
important
hints
:
•
Note that you are getting one
string
at a time and then print
the median
immediately
.
•
Yo
u must im
plement a compareTo
function
that will receive two
strings and re
turn
a
positive
number if the first string is
greater than
second string based on the
specified rule. Otherwise,
it should return a negative number if the first string
second string
.
•
If there are a total of n strings, t
he run

time complexity has t
o b
e O(n log n)
[this O(n log n
)
restriction does not include
how you will take the input.
]
•
Using insertion sorting technique during this process could be a good idea
, however, it w
ill
resul
t in O(n
^2)
. So, you are not
allowed to use any sorting algorithm
in your code
.
•
You must
use priority queue
(heap) to solve this problem.
•
Important hints:
You mi
ght be
no
w thinking
that how do we reall
y use heap in this
problem
and how can we
find median
without
sorting
! Here is the trick:
o
Y
ou can have two heap
s
,
one will
store smaller half o
f the numbers
(
left
h) and
the
other
one
(righth)
will store
bigger half of the data
. One of them will be mi
n heap and
th
e other will will be maxh
eap.
Please think a bit
which one will be minheap and which
one will be max heap.