I'd be interested to know why you feel that this is a useful interview question.
Implementing a well-known and widely implemented algorithm under stressful interview conditions wouldn't seem to me to demonstrate much about a candidate. In that situation I'd much rather be given a printout of some code and asked to talk around the implementation - how the code maps to the abstract algorithm, implementation trade-offs, readability, etc.