[nine_k]

I don't see any mention of time constraints, except for "to save time, we have written some boilerplate for you". I wish my prospective employer clearly communicated key constraints like this.

If I were the candidate, though, I'd first explain the idea of the solution (takes half a minute), then discussed ways to implement it (a minute or two), then went with a particular solution (counter, bitmap, two chasing indices, etc). I'd keep feedback from interviewers constantly flowing.

[madeofpalk]

Well, it's an interview. As both an interviewer and interviewee, you should be respectful that time is finite.