Dynamic Programming for Technical Interviews
I agree with other&#x27;s opinions that asking a Dynamic Programming question is a weak signal for a candidate&#x27;s competencies in general software development work like frontend, backend, mobile applications, and the like.<p>However, I would like to counter a common opinion that eventually follows in similar threads and some of my social circles: &quot;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&#x27;t be relevant in an interview.&quot;<p>It is fair that if you don&#x27;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.<p>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.<p>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.<p>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.<p>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&lt;Integer, Boolean&gt; when they can just use a HashSet&lt;Integer&gt; or with the amount of people who manually treat an Array as a Stack or a Queue when those data structures are readily available.<p>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.<p>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&#x27;t always tell someone that you can&#x27;t implement something because you didn&#x27;t find a Stack Overflow answer or you didn&#x27;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&#x27;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!<p>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.<p>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.<p>Overall, I hope people can look back at their courses in algorithm design and analysis and say, &quot;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!&quot;<p>Nonetheless, I don&#x27;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&#x27;s never too late.<p>Finally, my Software Engineering Toolbox has way more stuff like actual &quot;engineering&quot; stuff like automatic formatters, linters, fuzzers, automation, tests, mocks, coverage, &quot;Infrastructure as Code&quot;, and blah blah blah. :&quot;)<p>I would like to close by saying that a good engineer knows the right tools for the job. :)