4 ms·
Can someone explain this bit to me please? I then push them on this until they realize that any implementation of the dictionary lookup function of a string wo
by sjducb 4y ago
Can someone explain this bit to me please?
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²).
Surely it's
String -> Hash -> Is hash in hashmap
All of those operations are O(1) so the total operation is O(1)
- ArnoVW 4y agoAgreed. Well, in theory you may have conflicts in the bucket. And recovering the bucket means a round-trip to memory, which is much more expensive than running over a list. And in any case, "n" is the length of the word, but has nothing to do with the distribution of the dictionary. So one should use a "m" to capture that.
- sjducb 4y agoI thought that too The list of dictionary words isn't that big, so you can just have a long hash to reduce your conflicts to almost 0. Also words aren't that long. The longest English word is probably less than 100 characters, whereas you could feed trillions of strings into the algorithm.
- wickedsickeune 4y agoIn order to hash the string you need to access all of its characters, ergo O(n). I agree with you that this sounds weird, but if you imagine arbitrarily long strings as inputs, and don't want to have a lot of collisions, you need to take into account all of the input string in the hash function. In reality they are safely assumed to take O(1), but w/e the interviewer is looking for a specific answer.
- FabHK 4y agoComputing the hash of a string with n characters is O(n). However, the whole discussion in the piece suffers from not taking into account the fact that words don't get arbitrarily long. Thus, insofar that for all practical purposes n <= 30, say, it is indeed O(30) = O(1).