Story time about an interview experience I one had.

So I once interviewed at Google (well, I've interviewed at google many times, and have never gotten passed the hiring committee, but my resume looks decent so recruiters keep coming after me)

Anyways, on said interview, I was asked to program a relatively simple regex matcher (characters and star, perhaps ., don't remember).

Anyways, I totally bombed that question (I'm a big believer that 45m isn't enough time to organize ones thoughts on said Q as phrased, as it gives you nothing to build on, but I'll get back to that in a bit). This of course through me off for the rest of the interview day, because I tend to chew on problems that I have trouble with and tend to not let go of them quickly until I have some better understanding of the issue (including perhaps my limitations in being able to do anything about it).

So after the interview, as I tend to do, I did a bit of research, and came across this article of Kernighan

https://www.cs.princeton.edu/courses/archive/spr09/cos333/be...

which put everything into context beautifully

now, why do I think its a terrible interview Q? Because as Kernighan writes

"Rob disappeared into his office, and at least as I remember it now, appeared again in no more than an hour or two with the 30 lines of C code that subsequently appeared in Chapter 9 of TPOP."

if it would take Rob Pike and hour or 2 to come up with a nice solution, what chance do us mere mortals have in the context of an interview with people staring at us.

With that said, I do think this serves as a basis for a good interview question. Take a simple character by character string matcher as Rob Pike wrote, and ask the interviewee to expand on it, how would they add different functionality to it. 1) could they add '.', 2) could they enable it to match anywhere in the text, 3) could they add anchors, 4) and if really good, could they add star support. You get to see how the interviewee thinks about code, thinks to modify code, and being regex, still provides a good basis for thinking about tests. I hope people I interview find this to be a tractable Q.

Getting back to my story, in order to prove to myself I wasn't an idiot (and to learn some java, I was mostly a C programmer in the linux kernel at the time), I decided to take Rob Pike's approach and try to implement as much of a regex matching engine as I could

which turned into https://github.com/sjpotter/regex.

then when I needed to improve my Go programming skills (and explore possibly bad ways of doing Go programming), I ported it to https://github.com/sjpotter/regex-go

now, what's the point of this story in regards to the article? Implementing the quantifiers gave me a better appreciation of how they worked, both greedy and not (and the performance impacts of them, especially with my naive implementation of a matcher).

By following https://www.regular-expressions.info/reference.html and adding as much as I could (include backreferences, lookahead/behinds and conditionals) it gave me a much better understanding of the power in regular expressions (at least of the PCRE type, I'm not sure my old discrete structures teacher would be happy calling all of these "regular expressions").