Re:On a Great Interview Question
by evouga on Wednesday April 12, 2023 @09:38PM
(#35549722)
What you say is true, but the rolling hash solution is susceptible to potential hash collisions while the trie is not.
[ Parent
| on HN ]
Re:On a Great Interview Question
by light_hue_1 on Wednesday April 12, 2023 @09:56PM
(#35549856)
Ok sure. So what?
Hash collisions don't matter unless they're pathological. Just choose an out of the box hash that works well.
The article is just wrong.
Yup, pre-processing with a rolling hash allows you to get away with truly O(1) comparison (after the initial O(w) fixed cost). I don't know if the stdlib of any programming language does this internally if you request a hash of a substring, but it's trivial to implement yourself anyhow.
If you're writing a smug blog post about your "great" interview question, you should at least not make such "obvious" mistakes, especially considering rolling hashes are a "common" interview question trick for string problems. And in practice this hash'd solution probably might end up performing better than the Trie (of course needs benchmarking, etc., but it's not unreasonable to think it might). In an alternate universe you could easily imagine author himself getting failed for overlooking such an "obvious" solution.