On: A Google Interviewing Story

[mdwrigh2]

How could you do this in O(1)? Or are you saying you can get a probably right answer in O(1)?

[swolchok → mdwrigh2]

It's impossible to do in O(1) in the worst case, because you have to at least examine all the input (e.g., if the input matches the regex AA*B.)

[mdwrigh2 → swolchok]

That was my thought process, but the parent of my post claimed he could do it in O(1) (actually, he claimed it in o(1), but I'm assuming he just typo'd). Hence my question.

[TARMAP → mdwrigh2]

http://en.wikipedia.org/wiki/Chinese_room