We software types must be masochists. It took Rob Pike an hour in the comfort of his private office to write this piece of code. How is this _at all_ like a typical software interview?

You're right. At the same time, could it be interesting to see how someone approaches (not solves) an intimidating problem?

Also known as hazing.

There's a common question, "convert an RE into an NFA" (https://en.wikipedia.org/wiki/Thompson%27s_construction)

Have you seen that used for interviewing? Yes, some people can do it in a 1-hour interview, but wouldn't you rather ask something that can't be done from memory?

I know engineers who have asked it, yes. It really seems to be a test for "who was paying attention to that one lecture in CS205 near the end of the semester"

Wow. That's quite a tricky test, too -- if you study Thompson's original paper you can see plenty of pitfalls. E.g. his main code would loop forever on a star of a star, and he solves this in an appendix with a preprocessor to rewrite regexes of that kind, only it looked like that rewriting would blow up the size of the regex exponentially in the length of the stack of stars. No hire!

it doesn't any worse than what Huffman did for his CS classes at UCSC.

I have seen this one go by, which, from the perspective of someone who has been doing regex implementation for 14 years, more or less, is fairly amusing. It seems unfair, as someone aware of potential pitfalls of backtracking would presumably feel obligated to build a automata-based solution; someone aware also of the potential pitfalls of DFAs (failure to determinize quickly on some nasty patterns) might also feel obligated to build a Thompson or Glushkov NFA solution as well.

It's quite possible you might turn someone competent into a gibbering wreck (they are asking me to implement RE2 or Hyperscan in an hour!) :-)

I used to use this exact problem years ago when interviewing candidates at Google. At that time I thought it was a great question, but now I'm not that sure anymore if this approach to interviewing is the best way to assess candidates.

Super interesting. Could you say more? Perhaps it depends a bit on the role?