> I failed that interview by overengineering.

Almost. You needed to clarify what the interviewer was asking and discover requirements. As much as HN likes to hate on coding interviews requiring specific algorithm knowledge, determining requirements is very much part of the job, and engineers have a tendency to build what they want to build, not what the customer wants.

I don't care about people who like to overengineer things, as long as they are humble and have awareness of this tendency. Sometimes you need the extra power and creativity. If they are affable and don't take critics personally, they usually get in with the program easily.