> Also I’ve heard that Google automatically fails people who use regex in interviews,
Hmm... I don't remember that, and I conducted over 100 interviews back when I was at Google. A blanket failure for using a regex sounds like it's missing some nuance. But, maybe that was before or after my time.
I wouldn't be surprised if they start out with some interview questions that are easy to implement as regexes, but then gradually make the question harder and more general, where a pushdown automaton is necessary for a general correct solution, and fail people who either don't get a correct answer or end up implementing a pushdown automaton by dynamically generating larger and larger regexes.
I think it's more that you need to give the O(n) of your answer, which is generally very difficult to do with regex. And even if it's possible, it might not be an acceptable O(n).
In general regexes finish instantly for normal sized inputs, but the actual O(n) might be quadratic or whatever.
Hmm... I don't remember that, and I conducted over 100 interviews back when I was at Google. A blanket failure for using a regex sounds like it's missing some nuance. But, maybe that was before or after my time.
I wouldn't be surprised if they start out with some interview questions that are easy to implement as regexes, but then gradually make the question harder and more general, where a pushdown automaton is necessary for a general correct solution, and fail people who either don't get a correct answer or end up implementing a pushdown automaton by dynamically generating larger and larger regexes.