Don't get me wrong, I'm not saying DP is useless, it came in handy a couple of times over the course of my 20+ year career. I'm just saying that you could always look it up, and the amount of signal you get out of someone solving this problem is very close to zero, because it amounts to: "this person solved this problem before the interview", whereas the question you really need to answer is "can this person solve the problems we need solved".
The solution commentary [1] doesn't mention DP.
[1]: https://techdevguide.withgoogle.com/resources/find-longest-w...
I don't even see that as DP.
Not everybody will be as quick as me, but there are plenty of people that don't spend a month practicing for a Google interview. If somebody is practicing solving data structures problems for the first time in their life, that's fine -- maybe they went to a substandard school. But if they have to spend a month refreshing any time they want a job, it means their brain drops skills they learn that are closely related to the job they do. That means their experience is worthless -- they aren't retaining it, long-term.
Sounds like the skills are the useless things, not the work experience.
I posit that ability to solve such problems is completely irrelevant to one's job performance, at Google or anywhere else. Google's own test of this hypothesis (hiring a control group of people irrespective of their interview scores) seems to bear it out.
This idea that some people like to push, that these interviews are all about memorization, is a false one.
Link?
DP isn't used the vast majority of the time. That's not retaining "experience".
What's wrong with starting with a hashtable of substrings of fixed length? For inputs with low autocorrelation, that'll get you a good average-case speed up.
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.
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'd never heard this problem before and it took a few seconds to think of something better than brute force. Many colleagues I've worked with would too, and could probably improve on their first non-brute-force idea over the span of 25 minutes.