> They mostly suggest that if implemented as a hash function, it would be O(1) lookup. I then push them on this until they realize that any implementation of the dictionary lookup function of a string would be o(n) at best, and as such the total runtime of the solution is O(n²).
This seems pretty nitpicky, especially considering we're assuming substring creation is O(1). And isn't a hash table lookup of a string O(n) at worst, not at best? And since this seems like a fixed dictionary, we're only doing queries not insertions, couldn't you just choose a different hashtable algorithm like dynamic perfect hashing to guarantee O(1) lookups?
I also don't like how it starts off with the dictionary being a blackbox style function, and a later part of the question requires you to change the internals of this dictionary query function. My very first thought would be about the structure of the dictionary query. And then when told to ignore that, I would assume that's still the case when asking to later optimize the algorithm.
This seems pretty nitpicky, especially considering we're assuming substring creation is O(1). And isn't a hash table lookup of a string O(n) at worst, not at best? And since this seems like a fixed dictionary, we're only doing queries not insertions, couldn't you just choose a different hashtable algorithm like dynamic perfect hashing to guarantee O(1) lookups?
I also don't like how it starts off with the dictionary being a blackbox style function, and a later part of the question requires you to change the internals of this dictionary query function. My very first thought would be about the structure of the dictionary query. And then when told to ignore that, I would assume that's still the case when asking to later optimize the algorithm.