News for hackers. Stuff that matters.
Re:On a Great Interview Question by behdad on Wednesday April 12, 2023 @05:11PM (#35547002)
You still need to query every byte of the input string...

Any better than that you can do would be O(min(n, k)) where k is the length of the longest word in the dictionary. But without loss of generality that would be O(n).

Re:On a Great Interview Question by agolio on Wednesday April 12, 2023 @05:18PM (#35547106)
Good point, though I guess the point of the disagreement is then for me that the question's "dictionary words" implies to me an english dictionary, rather than an abstract dictionary of words of potentially infinite length
Re:On a Great Interview Question by d1sxeyes on Thursday April 13, 2023 @05:59AM (#35553228)
It would be impossible to look up anything in a dictionary of infinite length.

Therefore, either the question is nonsensical, or there must exist a word (or words) of a maximum length.

Re:On a Great Interview Question by light_hue_1 on Wednesday April 12, 2023 @05:26PM (#35547200)
I don't think so.

You take the first n bytes of your input string. You hash them. You look them up in the dictionary. The lookup is O(1) but hashing your input is O(n).

But there's a simple way around this.

We have incremental hash functions. When you add a byte to the string and you use an incremental hash, you do a fixed amount of extra work to update the hash. Like that you only need to O(1) extra work to compute the new hash.

One trivial incremental hash is to break your input into fixed size chunks, hash each chunk, and xor the chunks together.

Re:On a Great Interview Question by behdad on Wednesday April 12, 2023 @05:27PM (#35547218)
That's the same as the trie solution.
Re:On a Great Interview Question by light_hue_1 on Wednesday April 12, 2023 @07:17PM (#35548419)
It's not at all like the trie solution! Not in performance and certainly not in terms of complexity.

A trie is a pretty nasty datastructure memory wise. It involves chasing pointers all over the place. The constants on a trie are not going to be very good.

For an incremental hash, you hash your string, and then you fix your hash up as you go. Then you look up your hash in a hash table. Code-wise it's far simpler to implement. And performance wise it will be far faster!

The two solutions have nothing to do with one another. Except that they're both O(n).

Re:On a Great Interview Question by evouga on Wednesday April 12, 2023 @09:38PM (#35549722)
What you say is true, but the rolling hash solution is susceptible to potential hash collisions while the trie is not.
Re:On a Great Interview Question by light_hue_1 on Wednesday April 12, 2023 @09:56PM (#35549856)
Ok sure. So what?

Hash collisions don't matter unless they're pathological. Just choose an out of the box hash that works well.

The article is just wrong.

Re:On a Great Interview Question by krackers on Wednesday April 12, 2023 @10:54PM (#35550310)
Yup, pre-processing with a rolling hash allows you to get away with truly O(1) comparison (after the initial O(w) fixed cost). I don't know if the stdlib of any programming language does this internally if you request a hash of a substring, but it's trivial to implement yourself anyhow.

If you're writing a smug blog post about your "great" interview question, you should at least not make such "obvious" mistakes, especially considering rolling hashes are a "common" interview question trick for string problems. And in practice this hash'd solution probably might end up performing better than the Trie (of course needs benchmarking, etc., but it's not unreasonable to think it might). In an alternate universe you could easily imagine author himself getting failed for overlooking such an "obvious" solution.

Re:On a Great Interview Question by abtinf on Wednesday April 12, 2023 @05:58PM (#35547596)
You only need to do that if the length of words is unbound, which would be nonsensical.

The maximum number of iterations is length of the largest word in the dictionary.

Re:On a Great Interview Question by activitypea on Wednesday April 12, 2023 @07:18PM (#35548424)
You either care about the order of complexity, which is the big O, or you care about real-world performance of byte level operations. You can't have it both ways.