5 ms·

Did anyone get the O(document size) solution? I can't see how it would work without checking each word against the list.

• asmithmd1 15y ago
  Use a bloom filter? http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Bloom_filter
  • deleted 15y ago
    [deleted]
• ljlolel 15y ago
  Thank you! This is Hacker News! Why isn't everyone trying to solve the problem?!
• larelli 15y ago
  At first glance I don't think you can achieve O(document size) without some form of preprocessing. Each word in the vocabulary has to be looked at, so a natural lower boundary seems to be O(document size + vocabulary size). Also it is unclear what will count as an atomic operation. Although the description reads as if word comparisons were counted, this makes for another simplification, as words could be of arbitrary size. Also: I only checked the HN comment section to see if someone got the solution and I am amazed that others stuck to that part as well.
  • ljlolel 15y ago
    Yes, you use pre-processing. I framed the problem in a very real-world scenario. Use that. It's not a trick question. How would you solve my real-world problem efficiently?
  • deleted 15y ago
    [deleted]
  • deleted 15y ago
    [deleted]
• jodrellblank 15y ago
  Setup a hashtable of keyword -> wikipedia link. Check every word in the document against it. One check per word should be O(word count) ish, shouldn't it? Hashing every word will have a cost, but will be roughly the same for each word so I'll brush it aside as a constant, setting up the hash will have a cost, but shared over the number of documents to check. Checking every word sounds expensive but so does looking every word up in any data structure or searching every dictionary word in the document keywords and links have to be stored somehow. My biggest hesitation is it can't be that easy or all you and the interviewer would be saying it, so I must be glossing over some big cost somewhere, right?
  • deleted 15y ago
    [deleted]
  • ljlolel 15y ago
    That works if each phrase is one word. Many (most?) of the terms in the vocabulary are multi-word phrases. How would your algorithm work for multiple word phrases? What is its running time?
    • jodrellblank 15y ago
      It would have to be altered; let's see: Create hashtable where the key is the first word and the value is (rest of sentence, link). In the case of collisions, a list of rest of sentences and links. Checking the document would still go word by word, if no lookup fine, if one result compare the rest of phrase with the following document words, if a list, do that repeatedly. Runtime varies a lot with distribution of input phrases - if there are 50,000 beginning "phospholipid" that's not good. I don't know how to estimate the runtime well, best case is no matches or single word phrases, and then as above. Worst case is every document word matches a long list of phrase endings but none of them complete, but even then the searching is only searching a fraction of the phrases in len(longest-phrase) chars of the document. O(doc_words * num_of_phrases_by_prefix * avg_phrase_length) I'm uncomfortable here, wishing I had more algorithm/data knowledge to draw on, and maybe wouldn't have gone down this route had I paid attention to many words from the start. Every problem doesn't need a hashtable. Maybe phrase-trees...
• jbri 15y ago
  Set up a trie containing each phrase in the vocabulary. Repeatedly match phrases starting at the current word against the trie, stopping at the longest matching phrase. Link that and reset from the first non-matching word. The end result is O(n) in the number of characters in the document.
• psykotic 15y ago
  Yet another approach: Translate the regular expression for the disjunction of the search terms into a DFA. Then traverse each document with the DFA to find all matches. Traversing a string of length n with a DFA takes O(n) time regardless of the DFA's size. The DFA turns out to be basically the same thing as the trie. Indeed, the standard DFA construction factors out common prefixes of the search terms, just like a trie. But this formulation has the advantage that anyone can implement it in a few minutes with their language's regex library. In Python you might do something like this: def searcher(terms): pattern = r"(?:^|\s)(%s)(?:$|\s|,|\.|!|\?)" dfa = re.compile(pattern % ('|'.join(map(re.escape, terms)),)) return lambda string: dfa.findall(string) This snippet also tries to deal properly (if simplistically) with search term occurrences bracketed by whitespace and punctuation. As a side note, the problem didn't specify whether matches could overlap. Actualy, it isn't even solvable in O(n) time (plus precomputation) if overlapping matches are allowed. Let's say the search terms are "a", "aa", "aaa", etc, and the search string consists of n copies of "a". Then every substring of the string is a match and so there are O(n^2) matches, which obviously cannot be listed in O(n) time.
  • jongraehl 15y ago
    Most regex libraries don't do determinization (perhaps awk or grep do, but perl doesn't). You'll want to do better than just "use a trie" - like http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_mat...
    • pjscott 15y ago
      Perl will actually use Aho-Corasick string matching for regular expressions like these.