This was my first thought about how to solve it. It provably works in finite time. This ought to be a satisfactory answer in an interview, particularly if the candidate points out that it's unlikely to be The Optimal Solution. After which point, the appropriate follow-up question from the interviewers would be to ask what the time complexity of the algorithm would be in the worst case.