>optimal solution in less than a minute
you're interviewing wrong and i'm surprised that you haven't figured it out given 200 attempts. put yourself in the shoes of the interviewer - interviews aren't their main focus in the company and hence they're not invested in being excellent interviewers. they're most likely trying to do a good enough job such that it counts towards promotion and simultaneously not have a horrible time during the interview. so they have roughly a script that they'll follow
1. give the imprecise problem statement
2. give the opportunity for clarifying questions (points added or subtracted from interviewee for asking relevant/irrelevant/interesting/mundane question)
3. give the opportunity for naive solution (points added or subtracted for facility in implementing and runtime discussion)
4. introduce challenge portion (optimization or constraint or whatever)
5. give another opportunity for clarifying questions
6. give opportunity for talking through a solution
7. give opportunity for writing solution
assuming you make it this far
8. give the opportunity for discussion of trade-offs in time/space/code complexity/latency/etc.
that's 6 opportunities to demonstrate that you're smart, fastidious, affable, etc but only 2 of them are really technical. if you're aiming for writing the best/most optimal solution as fast as possible then you're aiming for the wrong thing - it's not a standardized test but an interview (i.e. two people are involved). you should be aiming to impress the interviewer! those aren't the same (the first is a component of the second).
if you'd you should put your contact info either here in a response or in your profile and i'll reach and we can chat about interviewing (i'm not a coach or a business but i do interview well so maybe i can help you a little).