5 ms·
I shared my experience in a blogpost: http://swizec.com/blog/inside-a-google-onsite-interview/swizec/4352 http://swizec.com/blog/inside-a-google-onsite-intervie
by Swizec 14y ago
I shared my experience in a blogpost: http://swizec.com/blog/inside-a-google-onsite-interview/swizec/4352 http://swizec.com/blog/inside-a-google-onsite-interview/swiz...
A few days ago I finally realized why they said I'm not good enough at big-O to play with them (despite saying my coding was excellent). For some reason I had a mental block that day and wanted to implement hash tables as prefix trees every single fucking time.
I have no idea why. Of course I know a hash table is O(1), but for some reason, that day, I kept trying to convince everyone it should be O(N) (N=length of key) because it's implemented as a prefix tree in the background.
Idiot.
- abecedarius 14y agoHm? Hashing is O(N) unless it's oblivious to some bits. Though the prefix tree part is optional, yes. :-) Better luck next time. (For some reason programmers really love tries / prefix trees when answering on stackoverflow and such. I'd like to understand why -- tries are neat, but you don't see them nearly as much in actual use.)
- JoshTriplett 14y ago> Hashing is O(N) unless it's oblivious to some bits. O(N) only makes sense when you agree on what N means. When using big-O notation, always make sure you agree on the base N values you want to work with. In this case, it sounds like you interpreted N as the number of bits to hash, in which case yes, any sensible hash algorithm has to look at all the bits so it'll use an O(N) algorithm. However, the post you replied to talked about hash tables, a structure used to implement (among other things) maps from keys to values. For such a structure, N refers to the number of items stored in the table; hash tables have the rather unique property of supporting O(1) insertion, removal, and lookups (modulo amortization arguments about the size of the table).
- pjscott 14y agoWell put. I'd like to add that, while hashing time is proportional to the key length, in practice it's very, very fast for all non-enormous keys, at least on modern processors. Compare with the cost of pointer-chasing in a tree, and hashing time starts to look pretty constant-ish. (Yes I'm handwaving around the details. So is everyone who talks about big-O notation in connection with real software.)
- abecedarius 14y agoThe post I replied to said N is the length of the key.
- deleted 14y ago[deleted]
- jhartmann 14y agoJust my two cents, Well hash tables might be O(1), but depending on the circumstance they are used in, how they handle collisions, implementation details and the quality of the hashing algorithm they can see real world performance that is not O(1). Inserting into a hash table can cause the hash table to expand, if the hash table is too small you will get collisions, etc. etc. Some choices of hash functions are actual O(n) instead of O(1). Sometimes hash tables are not appropriate due to the memory requirements. You get the idea. I actually like people to point these things out, even if the amortized cost is constant in lots of real world usage. When talking about time complexity I appreciate attention to detail, rather then just hand waving and saying its constant. My answer is always, 'well it depends'. Be careful though, back up your answers in a way that shows you do know what you are doing. Otherwise you can come off as blowing smoke. Truly understanding writing performance critical code is a black art, and you need to understand more then just the big O of some common algorithms. Showing that you know that performance and complexity are hard and you know there are hidden costs that can bite you and tradeoffs you have to take into account shows maturity.
- Swizec 14y agoYes yes, of course. But the answer most certainly isn't "Well I don't know _exactly_ how python does dictionaries, but I would implement them with a prefix tree and there is nothing better". Which is roughly the answer I gave, in different settings. To five interviewers.
- haberman 14y ago> Some choices of hash functions are actual O(n) instead of O(1) I think you're getting your n's confused. O(n) in the context of a collection applies to the size of the collection, not the size of the keys. Nearly all hash functions for strings are O(n) in the size of the string. This doesn't mean the hash table is O(n) for lookups.
- jhartmann 14y agoMy point is the whole process needs to be taken into consideration when talking about performance and runtime complexity. If you just use the address of an object for the hash, that has a implication to performance. If you choose a cryptographic function, that has another implication. If you use something like cityhash, that has yet another. If you use rehashing or a linked list to handle collisions that has another impact on the performance depending on what is going on. If you choose to auto grow the hash table upon a certain number of collisions, this is another thing you have to worry about. The process of lookup might use a precalculated cache of the hash code calculation if it is expensive and sacrifice some memory for this storage. My point of all these examples is that the simple runtime of the collection isn't the whole story and lots of crap can happen under the covers. We stand on the shoulders of giants, but we have to know what weaknesses and strengths we are exploiting. While just picking the right data (or wrong) structure makes a huge impact, you need a lifetime of experience to really know what matters, and what the trade off of one or another is in a given scenario. Hard to test for that intuition and I always like people that interview with me that start talking about these sorts of issues.
- timr 14y agoA hash table lookup is O(n), where n is the number of elements in the table. They have amortized constant time lookup (i.e. constant time in the average case).
- shrughes 14y agoOr it's O(log n). Depends on how collisions are handled.
- timr 14y agoIf you use a balanced tree instead of chaining or probing, sure. But, of course, nobody ever does that in practice, because the complexity isn't justified by the theoretical gains. Point was, worst-case time complexity isn't constant. I'd be happy to see more people get that right in interviews.
- haberman 14y agoHash tables, in general, have average constant time lookup. Only some hash tables have amortized constant time lookup. An amortized bound is a bound on the total cost of a sequence of operations. Loosely speaking, it guarantees that you can't keep hitting the worst case indefinitely. An average bound is averaged over all possible inputs, but doesn't protect you against hitting the worst case over and over.
- deleted 14y ago[deleted]