EPI - 10.8 - Online median in O(log n) time per element

Although this seems like the classic interview question that involves
one min-heap and one max-heap, and balancing the two whilst reading
input, it is not. This is because the Hacker Rank question also
requires that elements be deleted in O(log n) time as well, whereas
heaps only support O(n) removal.

Hence this solution involves O(n) space and uses a doubly linked list
kept in sorted order and a red-black tree (TreeMap) that maps a number
to the right-most instance of it in the doubly linked list. Maintaining
the invariant of these two data structures is easy enough; the map
gives you the insert and/or removal points, and by using a sentinel
node operations on the doubly linked list are straight forward.

Rather than determining the median from scratch every time (relegating
it to O(n)) we remember what the current median node is and shift it
left/right depending on what is being added/removed.

This solution fails tests 6, 7, and 8 on HackerRank, and passes the
rest. It fails not due to time but due to correctness. I suspect the
median update isn't quite right.