[Ancapistani]

I'd argue the point of the exercise isn't to implement an O(1) solution, but to verify that the applicant understands how the logic they're writing actually executes, and is capable of minimizing complexity.

Whether they arrive at an O(1) solution doesn't matter a bit to me. Most of the time, I don't even care if they phrase it in big-O notation - or have even heard the term!

Given the choice between someone who completed the exercise with an O(1) solution in half the allotted time and someone who never wrote a single line of valid code, I'll choose the person who is able to articulate the problem and potential solutions best every time.

It's far easier to search the web and find a "cute solution" than it is to learn how to think about and communicate complexity.