4 ms·

I guess I’ve always been confused by this question. If the dictionary isn’t infinitely large, and you have plenty of space, why can’t you put the dictionary in

by texuf 3y ago

I guess I’ve always been confused by this question. If the dictionary isn’t infinitely large, and you have plenty of space, why can’t you put the dictionary in a Set and look up words in O(1), reducing the overall complexity to O(n)? Obviously hashing has its limitations, but i thought we could hand wave over that part. If we’re limited by space can we assume that the dictionary is ordered and make the lookup in log(n) via a simple binary search? Or are we obsessing over the string equality operation? I feel like I’m missing something.

behdad 3y ago
Yes, the string equality itself is o(n).
elijaht 3y ago
Yea, I dislike it (a bit) for that reason. The "meme" in leetcode interviews is that "hashmap lookup is O(1)". It does feel like a bit of a gotcha to (correctly, mind you) expect an answer of O(n) for the lookup. That being said, I think you could get around this with careful prompting (ie, ask first "what is the Big-O for dictionary lookup with the respect to the number of letters" before asking the overall big O). But I think there is a bit too much wiggle room to make this a completely consistent question, too much variance candidate to candidate. I like the problem a lot, but wouldn't feel comfortable using it.
- texuf 3y ago
  Because the author didn’t bother to explain that this is what she’s looking for in a well thought out blog post, I assume she also didn’t explain this is what she was looking for in the interview, leaving a lot of candidates who didn’t have the same educational background floundering.
- jameshart 3y ago
  In general, hash map lookups are considered O(1) in the size of the hash map. Which is not the n the author is using, to begin with. But. Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits. And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right? So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too) Yet we call hash map lookups O(1). Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity). By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps... But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for. (Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)
  - pcthrowaway 3y ago
    > Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers This is a great point. If you're sorting an array of strings, you would never add an extra m in that complexity analysis for the size of the longest string, in bits (not length, because unicode) The OP seems wrong to make candidates do this
    - jameshart 3y ago
      Another thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and more physical space. Since we live in three-dimensional space, the retrieval time for a hashtable containing n entries must be bounded by the fact that the entries are located a distance of at least O(n^1/3) away. (Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.) So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.

by texuf 3y ago

behdad 3y ago

Yes, the string equality itself is o(n).

elijaht 3y ago

Yea, I dislike it (a bit) for that reason. The "meme" in leetcode interviews is that "hashmap lookup is O(1)". It does feel like a bit of a gotcha to (correctly, mind you) expect an answer of O(n) for the lookup. That being said, I think you could get around this with careful prompting (ie, ask first "what is the Big-O for dictionary lookup with the respect to the number of letters" before asking the overall big O). But I think there is a bit too much wiggle room to make this a completely consistent question, too much variance candidate to candidate. I like the problem a lot, but wouldn't feel comfortable using it.

texuf 3y ago
Because the author didn’t bother to explain that this is what she’s looking for in a well thought out blog post, I assume she also didn’t explain this is what she was looking for in the interview, leaving a lot of candidates who didn’t have the same educational background floundering.
jameshart 3y ago
In general, hash map lookups are considered O(1) in the size of the hash map. Which is not the n the author is using, to begin with. But. Hashmap lookups require calculation of a hash of the key. Calculating the hash of a key requires examining all of the bits in the key. If the keys are int32s, then the hash algorithm has to read 32 bits. If they're int64s, then the hash algorithm has to read 64 bits. And if your hash map contains n distinct values, then at a minimum they must be drawn from a key space where each key contains O(log n) bits. If you want a hash map to contain more than a few billion values, you'll need bigger-than int32-sized keys to distinguish them, right? So for any hashmap of size n, that means there's an O(log n) hash calculation in there. (especially when we are considering the asymptotic case where the hash map grows infinitely large... such hash maps will necessarily have infinitely long keys, too) Yet we call hash map lookups O(1). Because in practice we imagine a hash map has a key space of a fixed size (even though such a constraint would mean that the hash map has a fixed maximum size and therefore no asymptotic performance case since it can't scale to infinity). By playing around with big-O on hash table lookups with keys of size n, the interviewer is skating dangerously close to this contradiction at the heart of big-O analysis of hashmaps... But unnecessarily so, since the key space they're using is dictionary words, which have a maximum length, so their length isn't the n you're looking for. (Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers. Is it a hand wave? Probably not when you're dealing with numbers. Maybe when you're dealing with strings)
- pcthrowaway 3y ago
  > Note - for the same reason, big-O analyses of sorting algorithms don't usually take an extra O(log n) factor (in n being the size of the valuespace) for the time it takes to compare entries, even though obviously it takes 'longer' to compare two 64bit numbers for size than two 32bit numbers This is a great point. If you're sorting an array of strings, you would never add an extra m in that complexity analysis for the size of the longest string, in bits (not length, because unicode) The OP seems wrong to make candidates do this
  - jameshart 3y ago
    Another thing we ignore in big-O analyses: as a hashtable grows arbitrarily large, the physical media in which it’s data is stored must also take up more and more physical space. Since we live in three-dimensional space, the retrieval time for a hashtable containing n entries must be bounded by the fact that the entries are located a distance of at least O(n^1/3) away. (Not actually purely an academic concern - this physical constraint is what drives the difference in performance between using data in L1cache, RAM, disk, or on remote networked nodes.) So yeah, O(1) hashmap reads are a convenient lie we tell ourselves, which are really only true for ‘small hashmaps’.