This was used as a "weeder" question (IE, a way to quickly weed out candidates) at Google pretty frequently. I had never heard of it before and when it was originally explained to me I thought it was impossible. In retrospect, anybody who has implemented a running average in minimal space has done 50% of the work to get to this algorithm, and with some hinting, can often find their way to solving this problem even if they haven't seen it before.

Like the "cycle detection problem" (whcih I believe was common at Microsoft?) it was "solved" by experts only fairly recently and often favors people who took CS instead of learning to hack.