4 ms·
List all 5-letter words that remain words after replacing a b with o. How can we solve these efficiently? Put them in a set(), then iterate over its members an
by raldi 6y ago
List all 5-letter words that remain words after replacing a b with o. How can we solve these efficiently?
Put them in a set(), then iterate over its members and report any that contain b and are still in the set after the string replacement. O(n), which can't be beaten.
Edit: If you're downvoting, could you post a comment saying why?
- voldacar 6y agoa quantum computer could do it in O(n^.5) with grover's algorithm
- raldi 6y agoHow would it beat O(1)? Even a quantum computer can't read in the wordlist without looking at every word.
- jordan_curve 6y agoQuantum computers can see information about more than one word with just a single “look.” You’re right to think this is impossible though. Grover’s algorithm was one of the first examples of something that clearly could not ever exist classically.
- brians 6y agoHow do you put them into the set in O(n), exactly?
- raldi 6y agoSet insertion is O(1): https://stackoverflow.com/a/44080017 https://stackoverflow.com/a/44080017
- margalabargala 6y agoSet insertion is O(n) in this case. An O(1) set insertion refers to constant time regardless of the size of the inserted element, but if you add one element to a set, then add a billion elements to the set, the latter will take about a billion times longer.
- deleted 6y ago[deleted]
- raldi 6y agoRight, inserting N items takes O(N), which is what I said.
- jayd16 6y agoDetermining if something is in the set is not free. You need to specify the gets, inserts, removes and exists speeds of the sets you're using.
- raldi 6y agoSet lookup is O(1), and with this data structure is synonymous with get and exists. Insert is O(1). Remove is irrelevant.
- jayd16 6y agoI guess you're assuming a hash set and ignoring collisions? So you fill the set with in O(1*N), again loop through the (original?) list assuming its O(N) to do so searching the set for replacements? So at least a few passes through every element. You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts.
- raldi 6y agoOf course I'm ignoring collisions — it's a wordlist.
- jayd16 6y agoNo collisions in the input does not mean no collisions in the hash algorithm. In reality there's book keeping overhead in a hash data structure that might be significant.
- YeGoblynQueenne 6y ago>> You could actually reduce this by excluding elements as you insert. You don't need to fill your search space with with anything that has a "b" for example, eliminating inserts. I'm not sure that works. Suppose "abab" and "abao" are words. Note the problem spec says "after replacing a b with an o", i.e. after replacing _one_ b in a word with an o. If you exclude all words with a "b" and replace one b with an o in "abab" you will get "abao" which you have excluded, so you will think it's not a word. I think at best you can ignore only words with a single b.
- YeGoblynQueenne 6y agoI don't understand how this is O(n). You have to go through the set once to select each word and replace a b with o, then you have to go through the set again to search for the new word resulting from the replacement. That is, if Ws is the set of 5-letter words we want the set Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ws}. You can see that that's an O(n²) operation (each ∈ is an iteration over Ws). jayd16 proposed omitting every word that has a b in it from the "search space". I take this to mean, in practice, that we start by initialising a set Ss = {w: w ∈ Ws, b ∉ w}. Then Rs = {w: w ∈ Ws, w.replace(b,o) ∈ Ss} and the time complexity is O(|Ws||Ss|) which is again O(n²) in the worst case (where Ws = Ss). Note also that some words in Ws may have more than one b and since we are only replacing "a b" (i.e. one b) we may remove valid words this way. In any case, I don't see an obvious way to do this in O(n). Maybe I'm not thinking straight though, it's way past bed time.
- raldi 6y agoYou agree that set lookup is O(1) and we need to do it N times, right?
- YeGoblynQueenne 6y agoYep, my mistake. I was thinking of list lookups. I should have gone to bed :) In any case, even if it was O(n²) that's a polynomial time complexity and I don't see why BDDs are needed.
- taeric 6y agoTwo algorithms that are both O(n) can be wildly different in execution times. More, an O(n) algorithm can be more "efficient" than an O(lg(n)) one, for some values of n. (Or just in another facet. Maybe you actually do care about space.)
- raldi 6y agoWe're talking about five-letter words. I'm pretty sure a 25-year-old computer could iterate over all of them in well under a second.
- taeric 6y agoHow does that change the point? The claim wasn't how to do it fast, per se. It was how to do it efficiently. And comparing two algorithms of the same order can have a wide difference in the answer.