My claim was a very weak one, too. It was that somebody who never heard the problem before can get better than the brute force solution in 45 minutes. As m0zg intended it, that means better than 2^n*|D|, which is easily true. As I intended it, that people could do better than the "greedy" algorithm in 45 minutes, well, my image of a canonical developer is going to get the greedy algorithm right away, and then have 45 minutes to improve on it. And, I think they'd be able to accomplish that.
But if you aren’t in the mindset at all, these problems can be complete WTFs. For example, I just started interviewing recently and on one my first interviews someone gave me the house painting problem. I was completely stumped without knowing where to start, wasn’t familiar with the structure for solving these kinds of problems, and anyways these never really came up in my area of expertise. Ask me to write an interpreter, compiler, text editor, live programming system, reactive programming framework, I know all the tricks, but if you ask me to minimize the paint on a bunch of houses...
I'd imagine you might want a bit of practice get refreshed. I know what you mean. But I'm guessing it's not a month of practice, and you're not thinking you have to memorize the problems beforehand.
For me, it's a similar background (interpreters, compilers, text editors) and for any algorithms interview, what always got me have been dynamic programming problems and remembering that hash tables exist.
Edit:
Funnily enough, one time on a phone screen, fresh out of college, I got asked directly what data structure I'd use for a text editor. The next words out of my mouth were, "a pair of finger trees," and it turned out that it didn't go well, I didn't get a follow-up interview.
Ya, I think we are sometimes actually better off with the generic brain twister questions because the more specialized questions are harder evaluate. Like, my idea of writing a code editor might be completely different from yours because I’ve dealt with different requirements. And if the interviewer is junior enough (or not versed in the specialty), they might not be ready to have a serious discussion about trade offs and design spaces.
Usually, when interviewing people on an algorithms interview, I've asked an straightforward warm-up question, followed by a more interesting second question, that might be difficult for somebody that hasn't thought about anything interesting in 10 years. I don't think there was ever a situation where somebody got through the first just swimmingly, and then hit a wall on the second. The pain always starts on the warm-up question.
Coming from doing research for the past 10 years and now looking for a dev job, I have the opposite feeling: all these interview questions (even the hard ones) are way too boring.
You've also never been through a FANG interview, according to your LinkedIn profile. I've been through several (successfully), and conducted well over a hundred. It is very unlikely anyone can pass them without extra work to prepare.
I find these problems very annoying and I code a lot of clever algorithms in my research. But none of it is have the strong scanning variety, I mean, except lexing in a compiler.
And that’s how I would solve this problem in any case: I would just construct a scanner for D that would simply add to the state set rather than transitioning. That isn’t even in the canonical solution set, and anyways, would be considered too trivial as a test of compiler construction knowledge.