Re:How to pass a programming interview (2016)
by abetusk on Saturday March 09, 2019 @03:00AM
(#19345039)
I completely agree with you that solving a DP problem for a job interview shows next to nothing about the candidate, that asking a DP problem as an interview problem is cargo culting/rain dancing/etc. On the other hand, I believe DP is fundamental algorithm that comes up again and again and is the equivalent in importance to the simplex method but for millennials and gen-[xyz]'ers.
Among the problems it solves are:
* Shortest path in a graph (aka Bellman-Ford's method) [1], A* path finding [2]
* Approximate string matching [3]
* Viterbi algorithm for hidden Markov models [4]
* Earley parser [5] for context free grammar parsing
* Dynamic time warping [6]
* Finding the base of a strong generating set for permutation groups [7]
I'm consistently surprised that DP crops up in so many places. While most people won't be required to implement the above list in their day-to-day programming life, it's quietly in the background as a fundamental algorithm.
Dynamic programming is one of the few algorithms that, in a "natural" way, reduces a problem that is naively exponential to one that is polynomial. For example, try counting where 2^T random walkers lands in an array starting from the middle after T time steps. Naively, this would require 'simulation' of 2^T but with DP you can do this in O(T^2) (assuming addition of atomic integer types is "free" and there's no overflow on count) using DP (by summing a 'count' of random walkers at each time step, at each bucket in the array).
Among the problems it solves are:
* Shortest path in a graph (aka Bellman-Ford's method) [1], A* path finding [2]
* Approximate string matching [3]
* Viterbi algorithm for hidden Markov models [4]
* Earley parser [5] for context free grammar parsing
* Dynamic time warping [6]
* Finding the base of a strong generating set for permutation groups [7]
I'm consistently surprised that DP crops up in so many places. While most people won't be required to implement the above list in their day-to-day programming life, it's quietly in the background as a fundamental algorithm.
Dynamic programming is one of the few algorithms that, in a "natural" way, reduces a problem that is naively exponential to one that is polynomial. For example, try counting where 2^T random walkers lands in an array starting from the middle after T time steps. Naively, this would require 'simulation' of 2^T but with DP you can do this in O(T^2) (assuming addition of atomic integer types is "free" and there's no overflow on count) using DP (by summing a 'count' of random walkers at each time step, at each bucket in the array).
[1] https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
[2] https://en.wikipedia.org/wiki/A*_search_algorithm
[3] https://en.wikipedia.org/wiki/Approximate_string_matching
[4] https://en.wikipedia.org/wiki/Viterbi_algorithm
[5] https://en.wikipedia.org/wiki/Earley_parser
[6] https://en.wikipedia.org/wiki/Dynamic_time_warping
[7] https://en.wikipedia.org/wiki/Schreier%E2%80%93Sims_algorith...