5 ms·
> In your specific case maybe you both weren't aware of the nomenclature? Well, "always O(1)" is simply wrong in my opinion. This may be a cultural thing, but
by Udo 10y ago
> In your specific case maybe you both weren't aware of the nomenclature?
Well, "always O(1)" is simply wrong in my opinion. This may be a cultural thing, but I'm used to referring to the worst case behavior in big O as a default, so I would have said something along the lines of "the worst case is O(n) and that can turn out to be problematic in some cases". And normally interviewers do want you to talk about these kind of corner cases. I don't think I'm using the nomenclature wrong, and I certainly didn't ever refer to something as O(5) which as far as I can tell is not and should never a thing...
To my best recollection, the question came up as a dynamic language issue. Specifically what the interviewer wanted to hear is that accessing (both read and write) an object property in JavaScript is always O(1), since it's a hash map access under the hood. Leaving aside for a moment that this is fuzzily untrue in a typically JITed environment, it's also untrue in general. You could try to make a case for that when doing a read on a specially optimized hash table, but it would certainly not be true in the general case where you also add things to the table. But all of these considerations are already way too detailed and far beyond what the interviewer wanted to talk about.
They just wanted to check off "knows it's a hash table under the hood" and "knows that hash tables are always O(1)", even though both of these are untrue in my opinion.
- zzzcpan 10y agoIsn't it too implementation specific to simply claim worst-case as O(1) or O(n)? Depending on how much memory is acceptable to waste and how fast insertions should be worst-case could range from O(1) to O(n).
- Udo 10y agoI would not consider a table where the data size of the hashed keys equals the data size of the unhashed keys a hash map. If you got, say, a u8 as a key, and your lookup table uses u8s for keys internally, that's not what most people would refer to as a hash table. It's simply a lookup array. In all the usual cases, the hashed key size is way less than the unhashed key size, and you need to pay the price for collisions somewhere.
- zzzcpan 10y agoNo, if you rebuild on collision you waste just a bit more memory, but get O(1) worst case look-ups. It's still a hash table and not a table that maps an entire key space. See how dynamic perfect hashing works.
- Udo 10y agoRead what I wrote. Rebuilding is not free.
- zzzcpan 10y agoThere are various trade-offs, as I said, but getting O(1) worst-case look-ups is not hard. Only naive implementations could corner you into O(n) worst-case. I'm sorry, but you don't really understand hash tables.
- Udo 10y agoRead things more carefully before rushing to judgement. I'm not talking about a lookups-only scenario. Of course you can make anything O(1) as long as you arbitrarily define all the parts that aren't as external to the solution, but you're just kidding yourself in the end. > I'm sorry, but you don't really understand hash tables. I'm not the one who made this personal, but I'll match that allegation back to you, and I raise you one "you don't really know how to interpret what people say".
- zzzcpan 10y agoI'm sorry, I didn't mean to make it personal.
- Udo 10y agoHonestly, I think implying that rebuilding the hash table is an O(1) operation is worse. :P But judging by the downvotes I'm getting on that particular comment, it seems that most people agree with you that rebuilding is indeed free. So it seems you won this argument on several fronts ;)
- lorantt 10y agoO(1) is usually prefixed with "amortized" or "average worst-case", which is where the difference in interpretation comes from imo. I found this explanation a bit wishy washy on some details but good (and has an appropriate appeal to authority/original sources). https://m.reddit.com/r/compsci/comments/2z74z8/why_is_hashtable_lookup_o1_rather_than_olog_n_or/ https://m.reddit.com/r/compsci/comments/2z74z8/why_is_hashta...
- sp332 10y agoYup, pathological worst-case can be annotated with an omega Ω(n).
- quickben 10y agoThere are three curves. Big O is simply the average best fit. You also have max worst and min best. JavaScript does (unless I'm wrong) a layer of variable lookup, so the time is far off from O(1). So, you are right on technical terms, and on interview terms, it depends. When I was just out of university I'd have probably went for the job. As I'm getting more senior, I'd still be polite and explain them where they are wrong, but stand my ground with the recruiter afterwards and tell him the interviewer was out of his depth, and checking off questions he probably googled somewhere. I'd then ask him to give me more serious companies to be considered by. Stuff like your story have more to do with team skills then technical skills. Who cares if you answer right or wrong on the question, when you are the guy you are supposed to work with get pissed off with each other after few minutes technical discussion. General advice: go for where you are celebrated and not for where you are tolerated. A bit of synergy can go a long way.