Find The Median Of Infinite Stream Of Numbers

A friend of mine who works in a big Bay Area company recently asked me this question. “There is an infinite stream of numbers and you have to provide a median of those numbers a any given time.” At first it sounds impossible (BTW, do not confuse median with mean or average). When asking further about the problem domain he provided me some more information that helped me solve the problem in couple of minutes. I am not going to give you the answer, but I will provide you the domain information. The infinite stream of numbers is actually the response time of pages served by the web server. At any time you are supposed to find median response time. The obvious limited resource constraint applies.