[curiousDog]

Unpopular opinion, but the best way to prepare for DP problems is to solve the well known ones and memorize them and their recurrences. Only 2-3 companies like FB and Goog ask them (well they’re the only ones worth studying DP for anyway). Coming up with a recurrence on the spot is very hard. The edit-distance paper was an award winning ACM paper and expecting someone who has never seen that before to code it up (even the memorized one) is ridiculous.

[steelframe]

The best way to perform well in an interview is to have seen and worked on the problem at some point beforehand.

When I got a job at Google (in a previous life), two of the questions in my interview loop were ones that I had seen in previous interviews. I kept my mouth shut about that and faked brilliance in the moment. That is, I pretended to be stumped for a second, then I created a narrative where I had a sequence of 2 or 3 "Ah-ha!" moments where I figured out how to refine my solution.

I cued off the interviewer, waiting until they seemed just about to blurt out a hint, when I raised my hand and said, "WAIT! Maaaybe.... I can use a BFS instead of a DFS here and label the cells!" Then the interviewer would usually smile and nod in satisfaction.

Finally, I "stumbled on" the "right answer" and slammed out the code that I had pretty much memorized up to that point.

Make a stupid game, I'll play the stupid game, and have fun doing it.

For the record, I kicked ass at Google (getting promoted twice) before moving on to greener pastures.

[bootsz]

Yep, 100% this. I recently finished a series of interviews after extensive preparation and had at least 3 sessions that went something like this. Practice enough problems and eventually you start seeing them crop up in real interviews.

Doesn't say much for the usefulness of such an interviewing paradigm but that's a whole other conversation.