Re:A Google Interviewing Story
by bluesnowmonkey on Saturday November 20, 2010 @11:47AM
(#1924761)
Which is how much? I wanted you to try and quantify the difference, because the process of doing so would lead to the flaw in your argument.
The hash table solution is O(n+m). 24 operations on the example. The array solution is O(n+m) and 24 operations. The same.
Your intuition tells you that the array is faster because subconsciously you're making assumptions about implementation details. What if you're in a language like PHP where arrays are implemented as hash tables? What if you're in C, but the hash table implementation uses a resizable array and happens to choose an initial size of 26?
The hash table solution is O(n+m). 24 operations on the example. The array solution is O(n+m) and 24 operations. The same.
Your intuition tells you that the array is faster because subconsciously you're making assumptions about implementation details. What if you're in a language like PHP where arrays are implemented as hash tables? What if you're in C, but the hash table implementation uses a resizable array and happens to choose an initial size of 26?