An Interview Question: Dynamic Median Structure
October 30, 2013 § Leave a comment
While I was thinking about puzzles, I thought it might be nice to do something useful for my readers that actually want jobs (jobs in the technology industry, I mean). I was browsing the internet, and I came across an interview question that I myself have been asked before, and I think it is actually a pretty good technical question. Anyway, enough beating around the bush.
The problem is phrased as follows: you are to design a system (a datastructure, if you want to call it that) which can receive numeric elements as input and can deliver the median at any time as output.
Of course, this is somewhat open-ended as there are so many ways to accomplish this. Of course, that is what interviewers usually want, as it helps them (or so they claim) to take a look at your thought process. So, while I can not gauge your thought process, if you would like to benefit from this, you should find ways to optimize your structure. Try to see how much efficient of a solution you can deliver and how what trade-offs you might be able to make from time and space.
Thanks for reading!
-A Student of Logic