[gorbachev]

You think "I'd use a well tested 3rd party library for this problem" would eliminate you from the running on an interview with this question?

This, and many other of these algorithm questions, are asking people to come up with solutions to problems solved umpteen times with well designed and tested libraries available for all of them.

A sign of competence as a software engineer would be to use them.