Hi,
I've seen a large chunk of my upsolving/practice time goes into trying to learn how to implement algorithms or data structures from scratch (like KMP/suffix arrays etc) when I encounter these new algorithms.
I understand — albeit at a high level — how/why the implementations work, but is it important to spend time perfecting one's ability to implement these from scratch when I already know how to apply them to most applications?
What are the scenarios where not knowing how to implement from scratch handicaps you where a template won't save you? Algorithmic interviews? Would I ever need to worry about implementing such algorithms there?
I would say that the value of only knowing what the algorithm calculates vs knowing how it works vs mastering implementation greatly depends on the algorithm. For example, FFT can be used as a black box almost every time while I usually use DFS-tree differently every time. Using your example, I mostly use KMP in an unique way if I use it (some kind DP over the automaton perhaps) and in this situation I think using a library implementation of the algorithm isn't enough.
I don't know what you mean by "understanding at a high level how the implementation works". In general, unless the algorithm is very black-boxable, I would want to be able to implement it. But I wouldn't spend extra time just to perfect my ability to implement if I am already able to implement.
This makes a lot of sense. I guess I'll just need to spend the extra time understanding the algorithm better to enable implementing it easily. Thanks!
in many competitions (mostly onsite ones) you are not allowed to use the internet and all the code must be written during the contest.
In most of those though, you’re allowed to bring physical reference documents, so you still usually aren’t implementing suffix arrays yourself, you’re just typing your (or somebody’s) prewritten suffix tree code again.