Dynamic Programming for Technical Interviews

I am not arguing with this. In my comment my intend was to show that the distinction between the memoized top-down approach and bottom-up (the approach that is usually taught as DP in a classroom) is significant in some memory optimizations.

> It's pretty hard to get someone solving actual problems in a single day. Do you have some examples of how this might be done?

Solve a small problem - of which millions can be found in issue trackers.

Here is an example I just read on Github:

Somebody reports that reading a JSON file results in a value that clearly is an integer being misidentified as "Not an integer". The source code is a parser written in C and the code is quite readable.

Give the candidate an hour to try to figure out what is happening (obviously, the language and context must be a match for the job).

Important - I think: It would be good if the problem is unsolved and the interviewer him-/herself does not know the answer. Also: Don't send them into a room alone, watch them. I know that adds stress, but learn how to lower it, make it clear you too don't know the answer. If the candidate really can't cope with someone watching, well, okay, let them try alone, I just think if the atmosphere is right this is valuable. There is no right way to approach solving such a problem, but without and not meant for judgment, I think this is just interesting to see how different people approach problems. Of course, if the interviewer has string opinions about how it should be done that is a bad method and I myself would not like to be interviewee in that case.

> It would be good if the problem is unsolved and the interviewer him-/herself does not know the answer.

I think one-use questions like this must be are bad. It makes it harder to compare candidates, which is what you really want in an interview.

I agree with other's opinions that asking a Dynamic Programming question is a weak signal for a candidate's competencies in general software development work like frontend, backend, mobile applications, and the like.

However, I would like to counter a common opinion that eventually follows in similar threads and some of my social circles: "Algorithms is an undergraduate course in which students learn specialized solutions to esoteric math problems, all of which they ultimately forget when they spend real time working in the industry, so the knowledge shouldn't be relevant in an interview."

It is fair that if you don't exercise what you learned, you will gradually forget it, but I believe its still important for a candidate to cherish algorithm design and analysis because I consider it a great toolbox of the trade.

For all the concepts and the techniques I learned from my undergraduate course in data structures and algorithms, I utilized them as the basis of my Software Engineering Toolbox.

What is my Software Engineering Toolbox? It is a collection of algorithm design concepts and techniques that I can employ anytime I am faced with a novel problem or a problem whose standard Stack Overflow solutions are inadequate.

The Software Engineering Toolbox contains the following: Arrays, Linked List, Stack, Queue, Hash Table, Binary Search Tree, Priority Queue, Set, Trie, Sorting, Binary Search, Divide-and-Conquer, Backtracking, Dynamic Programming, Range Query Trees, Graph Algorithms, Bit Mask Optimizations, Square Root Bucket Optimizations, and Multiple Pointer Optimizations.

First, I rarely implement my own data structures from scratch; all the programming languages that I use provide great standard libraries. Yet, I always remind myself the use of these data structures, because you would be surprised with the amount of people you can meet who tries to answer a problem that boils down to a set membership with a HashMap when they can just use a HashSet or with the amount of people who manually treat an Array as a Stack or a Queue when those data structures are readily available.

Second, I rarely implement my own sort or search functions from scratch; again, all the programming languages that I use provide great optimized functions. I treat Sorting and Binary Search as techniques that lend themselves to optimizing the locality of a data set such that you can easily answer basic statistics, find the bucket for a token in a ring, or merge data sets. These are simple techniques developers should readily know to exist when optimizing their code.

Third, why do I have Divide-and-Conquer and Backtracking in my toolbox? I believe that no matter what problem you face, you should be able to bruteforce it. You can't always tell someone that you can't implement something because you didn't find a Stack Overflow answer or you didn't deduce a collage of standard library functions or third-party libraries to solve your problem. Using these techniques, you can at least arrive at a pretty weak solution which is still a solution. To actually address Divide-and-Conquer and Backtracking in relation to bruteforcing, these techniques allow you to easily traverse through a search space to filter for a certain combination or permutation of items that satisfy a customer's constraints. Furthermore, Backtracking is a relatively easy to medium difficulty technique that is the basis for a lot of the Graph Algorithms people keep balking at!

Fourth, Dynamic Programming. To be honest, I rarely utilize it, but I appreciate it because the common subproblem types of 1D, 2D, Range, and Sub-Trees taught me how to order subproblems successively to solve other problems, which applies beyond DP. I discourage people from trying to pattern match Dynamic Programming problems and solutions, and I encourage them to truly digest CLRS and understand its 4 rules for Dynamic Programming to consider possible dependencies and structures for various combinations and permutations of the problem parameters to identify what the optimal substructure really is.

Finally, the remaining things in my toolbox are included in my toolbox because they are useful in my work experience with real-time network anomaly detection and streaming analytics. For example, topological sorting distributed tracing events into a rooted tree that I encode into a bit vector using a left-child right sibling binary tree. Not everyone will do this, but with my toolbox I never worry much about facing new frontiers of problems or being tasked to create libraries and tools for myself and others to use instead of being at whims of someone else on the Internet.

Overall, I hope people can look back at their courses in algorithm design and analysis and say, "Yeah, the problems and the solutions were really weird, but the techniques hidden away within them are actually GENERALIZABLE and are a fundamental basis to build new things and solve complex problems!"

Nonetheless, I don't want anyone who is weak in algorithms design and analysis to feel discourage. Play to your own strengths whatever they maybe, or you can always strengthen them; it's never too late.

Finally, my Software Engineering Toolbox has way more stuff like actual "engineering" stuff like automatic formatters, linters, fuzzers, automation, tests, mocks, coverage, "Infrastructure as Code", and blah blah blah. :")

I would like to close by saying that a good engineer knows the right tools for the job. :)

I disagree. If we're considering the debug/issue fix approach (which I quite like, because it displays code literacy and clarity of explanation in a context like that one would find in a typical workday), if I use the same task/tasks for each candidate, I'm implicitly (and tremendously) biasing myself toward a universe shaped by the tasks I chose. What I'm really looking for is a more universally distinguishably trait of lucidity and perspicuity (coupled with sufficient technical skill, which, again, bias and variance from your tests' structure is always an issue in accurately scoring), in any case.