Comment by GistNoesis | Hacker News Reader

Comment by GistNoesis | Hacker News Reader

Parent Full thread

> lookup is O(1) and explain that it’s actually O(n)

I don't get why the dictionary solution is actually O(n).

Surely you can have the hash function be O(1) by only looking at a subsets of characters something like

hash(s) = (s[0 %s.length ] ^ (s[6 %s.length]<<c1) ^ (s[7 %s.length]<<c2) ) % (size of the hash table)

You can trade-off memory for speed to avoid collisions by having a mostly empty big table (like 9/10 empty table). And you can also use multiple hash functions that must both simultaneously collide to avoid having too big a table (kinda like fronting your hash-table with bloom filters).

And you can pick the selected sub-index at random such that they split well your dictionary. Maybe you can even build a "Perfect hash function" so that all your dictionary words have distinct keys.

You only have to check for the whole string when the hash match, probability of which you can make as small as you want.

> > About Part 2 :“Write a function that given a string, determines if it’s a concatenation of a number of dictionary words.”

Isn't it just recognize if a string belongs to a regular language, where the language is defined by words in a dictionary ? So you just build a parser for your language and you test for belonging.

I'm quite rusty in non-deterministic finite automatons and regular languages, but surely there exists algorithm that build an automaton from the dictionary to recognize the language in something better than n^2, no? (We are moving the states of the automaton once per character, and we likely won't have n active states (except maybe for pathological dictionaries), complexity should be something like O(k*n) where k is a constant depends on the dictionary).

The hash table is O(1) even without your modification. Because there is a fixed dictionary, the length of the longest possible word is known in advance. That provides a constant bounds that does not grow. Let's say the longest word is 25 letters. Your hash computation is O(25) which is equivalent to O(1).

What this means in practice is that there is no polynomial curve for very long words. You don't bother hashing them, so the curve peaks and then flattens.

Obviously a trie is an interesting and possibly faster solution, though the hash has the benefit of being more cache friendly. But the big O analysis presented for this problem is flawed.

It depends on what you are counting as 'n'. It's reasonably clear in the discussion that we're talking about operations on individual characters. Calculating the hash of a string of length n is O(n). Look up in the hash table is still O(1), but you need to calculate the hash first, and that's linear in the length of the string (for non-degenerate hash functions).

On these kinds of problems, I like to suggest that we might be thinking about arbitrarily long "words". Get out of the headspace of language dictionaries, look at things more abstractly. Otherwise a lot of big-O analysis becomes degenerate.

Also, don't forget hostile inputs!

If dictionary lookup is O(1), we could just make a dictionary of all the doubled words? Now the whole problem is O(1)!

But making that is O(n^2) time and space, where n is the size of the dictionary

"Surely you can have the hash function be O(1) by only looking at a subsets of characters something like"

I seem to remember that in the very early days of Java the standard hashing method for strings only looked at a small prefix - turns out that very common use case was to be storing URLs as keys which, of course, mostly start with the same letters...

I got stuck in that too, but I think it’s right. No matter how smart you do the hashing, in the end you need to do an equality check, and that has to be O(n).

Eg you can’t just do equality on collision, you need to do equality on every lookup at least once.

Total O(n) using hashes, but not total O(n^2).

> you need to do equality on every lookup at least once.

I still don't think so. You only need for when the split would correspond to a good partial match.

There are also other smarter hashing thing you can do to help convince you.

For example if hash( s ) = sum_over_i( g(s[i]) ) if you pick g(x) = x or g(x) = xx or g(x)=xxx (or any function you are free to choose) (it's kind a like matching statistical moments of words).

You can calculate this hashes in amortized O(1) because of sliding window trick.

You can also index on split length.

You can filter your set of candidate split positions so much that you only have very probably valid split positions in your candidate set, and therefore the complexity is just verifying the validity of the candidates splits, so still O(n(number of candidates after filter) ).

> > Part 2

A solution based on filtering a candidate set could also probably be made to work for multiple words. You use the matching statistics to get candidates starting positions and length for words of the dictionary that appear in the string and you verify if they touch each other. Pathological cases are when words overlap each other but this may not appear very often in practice.

You can also add some filter based on pairs of words (or triplets..., or n-grams) .

All in all, I think the problem is rather bad because smart candidates will often have a solution that the interviewer may not be able to comprehend, and as a candidate you have just put yourself in a possible ego battle with the interviewer were even explaining the proof is not easy. In fact if the alternative solution is more interesting than the rest of the problem, you might get your candidate be focusing on that instead of your simpler but boring trie based solution.

I wonder if it's possible to construct an edge-case so that nearly every dictionary lookup results in a match, requiring you to do the string comparison on each lookup if you want a guaranteed zero false-positive rate?

My initial hunch was an example where every prefix of the word is part of the dictionary, then on an example like `abcdefgh` you'd test `a`, `ab,` `abc,`... But on such a case you can be clever and defer the string match until you verify that the hash of the suffix also exists in the dictionary, which it won't.

So it would seem a pathological example needs both prefix and suffix matches, but this just means that it's very easy for us to find a valid segmentation, so we will find one very early on.

I guess this is probably what you meant by "split would correspond to a good partial match" though.

Reply on news.ycombinator.com