I wrote a simple, efficient program to do this, which the interviewer was fine with and then asked for the complexity. I said it was O(n) (it was a linear-time algorithm), and he spent the next 10-15 minutes trying to get a different answer out of me. Ultimately, he told me the answer he was looking for was O(3n)...