3 ms·
> 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
by sverona 4y ago
> 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²).
Is n the length of the word or the length of the dictionary? And if it's the length of the word (<< the length of the dictionary), why does it matter if it's linear or quadratic?
- behdad 4y agon is the length of the string. As for why it matters whether it's linear or quadratic, we are assessing the candidates ability to analyze a problem and possibly improve an algorithm. It might not matter in the problem at hand.
- sverona 4y agoOkay, yeah, that's fair.
- edflsafoiewq 4y agoSurely there is a longest word in the dictionary, so you can short circuit for any string longer than twice that. So an asymptotic analysis in the length of the string doesn't really make sense.
- jameshart 4y agoWe're assessing the candidates ability to do work that doesn't matter? This is a negative hiring signal you're looking for, right?