News for hackers. Stuff that matters.
Re:A Google Interviewing Story by bluesnowmonkey on Friday November 19, 2010 @07:58PM (#1923452)
Oh really? How much faster would that be?
Re:A Google Interviewing Story by jamesaguilar on Saturday November 20, 2010 @04:45AM (#1924211)
As much faster as the length of the second string times the difference between an address lookup and a hash table lookup.
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?