6
\$\begingroup\$

This is a question I was asked in an interview, below is a cleaned-up copy of the answer I gave. Apparently this answer was not satisfactory. How can it be improved?

Question: Given a dictionary of words (a text file with 100000+ entries) and a list of n letters with possible repeats (i.e. a Scrabble tray), return the list of words which can be formed from some or all of the letters in the tray.

function scrabble(dictionary, tray) {
  return dictionary.filter(w => isWordInTray(tray, w));
}

function isWordInTray(tray, word) {
  // build multiset of letters in tray
  let counts = {};
  for (const letter of tray) {
    if (counts[letter] === undefined) {
      counts[letter] = 1;
    } else {
      counts[letter]++;
    }
  }
  
  // take letters from the word and decrement tray count
  for (const letter of word) {
    if (counts[letter] > 0) {
      counts[letter]--;
    } else {
      return false;
    }
  }
  return true;
}

//---------------

// dictionary (full dictionary contains 178691 entries)
const dict = ['AA', 'ABSORBABILITIES', 'AD', 'ADD', 'BAD', 'DAD', 'FOO']; // ...

// test case
const exampleTray = ['D', 'D', 'A'];
console.log(scrabble(dict, exampleTray));

// expected correct answer (in any order)
// [ 'AD', 'ADD', 'DAD' ]

Caveats

  • The interviewer said that the problem was "kind of like Scrabble", this was the only mention of Scrabble. The size of the tray was given simply as n (it was described as a list of letters, not a tray).
  • The full dictionary was given to me as a text file, it is sorted and has 178691 entries. I've included a minimal subset which works with the test case I was given in the interview.
  • counts is a hashtable but I could have used a 26-element array instead to get O(1) inserts and lookups which improves the worst case from O(n), but n = 26, so it's not a big deal.
  • I'm not looking for micro-optimizations for special cases: I'm only seeking to decrease the big-O worst case complexity.

Alternative Approaches

These are the other approaches which spring to mind:

Approach 2: Generate all words

The opposite approach is to generate all words from the tiles and look them up in the dictionary, but if we treat the tray as a multiset of letters then the number of words we will generate is a multiset permutation and that's just for the case where len(word) = len(tiles) without considering all the shorter words which can be formed.

The size of the tray was given as n, while in the game of Scrabble it's at most 7 (news to me as I don't play Scrabble), the interviewer never gave this restriction, so presumably max(n) = max(len(word) in dict) which is "ABSORBABILITIES" at 15 letters. That's going to be a huge search space. I asked what n was and he said "anything".

If my understanding is correct, the worst case for multiset permutations is when each letter in the tray is unique, because this is simply the number of permutations which is n!. Again, this doesn't account for the need to also find words shorter than the tray length.

7! = 5040, so for an actual Scrabble tray, generating all words is feasible, but at 9! we've generated more words than are in our dictionary and by 15! there's over a trillion.

Approach 3: Use a trie?

When I see words being looked up in a dictionary, I think of a trie (prefix tree). What I can't see is what it would offer in this case, especially w.r.t big-O worst case complexity.

Is there something I'm totally missing?

Big-O

Assuming that all words are of length w and the tray is also that length, the dictionary is of length n, and there are no anagrams; the complexity should be O(n*w).

(This also assumes that counts is replaced with an array as mentioned above.)

\$\endgroup\$
  • \$\begingroup\$ @ggorlen Please add an answer instead of a comment. Refer to the section When shouldn't I comment? on Comment everywhere. \$\endgroup\$ – Sᴀᴍ Onᴇᴌᴀ Jun 20 at 23:06
  • \$\begingroup\$ @SᴀᴍOnᴇᴌᴀ removed--thanks. \$\endgroup\$ – ggorlen Jun 20 at 23:20
  • \$\begingroup\$ You have "a text file with 100000+ entries" and you want to assume there are no anagrams? \$\endgroup\$ – AJD Jun 21 at 19:57
2
\$\begingroup\$

The way to use a trie here is to sort the letters of each dictionary word:

[ AD, ADD, DAD ] becomes A > D [ ad ] > D [ add, dad ]

Then walk the trie and stop descending when isWordInTray returns false.

Worst-case complexity is unchanged (arguably worse, since sorting time is not linear); actual runtime is greatly improved.

\$\endgroup\$
  • \$\begingroup\$ Just building the trie should be O(len(dictionary) * len(longest_word_in_dict)) and seems a step backwards from building the result immediately. If there were repeated lookups, then there'd be benefit to the up-front cost, but that doesn't appear to be part of the problem description. \$\endgroup\$ – ggorlen Jun 20 at 23:19
  • 1
    \$\begingroup\$ Nice to see a concrete description of Idea 3. I agree that it doesn't help the overall complexity. \$\endgroup\$ – John Hewson Jun 21 at 6:41
  • 1
    \$\begingroup\$ @ggorlen OP's solution visits each dictionary letter once and was deemed unacceptable. We have to conclude there is more to the problem. Given the nature of the problem and the "kind of like Scrabble" hint, I think a reasonable interpretation is "lookups should be efficient even if setup is not." \$\endgroup\$ – Oh My Goodness Jun 21 at 12:24
1
\$\begingroup\$

I have previously looked at this problem - many years ago. The first step is to create an indexed list of all the words in the dictionary, with the characters sorted in alphabetical order. This is a one-off cost O(n) [Where n in this case is the size of the dictionary, not the number of letters in the Scrabble tray].

Now, for each search of n letters, you can filter the list where the list element contains any letter that does not exist in the Scrabble tray. For example, if you had DDA in your hand, the word DEAD would be excluded because E does not exist in your hand. This should be O(n) [Where n in this case is the size of the dictionary, not the number of letters in the Scrabble tray].

The indexing/ordering of letters in the dictionary can be used to your advantage (especially if you use a jagged list), because some words are anagrams of others. So a check of the list for DALE, DEAL, LADE and LEAD should only cost one cycle in the search - four words for one! In addition, if your lowest character in your hand is not A (e.g. say it is M), you can use the indexing on the first character to remove a large swath of words in a single hit - similarly for the highest character in hand (e.g. if the highest character is D, you can stop searching the index when the first character is E).

So now, if you are doing a single search, your cost is at most O(2n), but probably more in the order of O(n + k*n/2). where k is the number of searches you will do. Happy to be corrected on my assessment of O because it has been a few decades since I last looked at formal definitions of O.

\$\endgroup\$
  • \$\begingroup\$ @JohnHewson did the interviewer specifically say that big-O complexity is your problem? Unlikely, since it's not possible to do better than linear in the count of letters, which you've accomplished already. It's important to understand that big-O complexity is not the last word on efficiency. Hash insertion is worst-case O(n) and we still use those every day. \$\endgroup\$ – Oh My Goodness Jun 21 at 12:19
  • \$\begingroup\$ @JohnHewson - No - sorting the list of words in done only once. And with a smart search (which is why sorting the list is a help) is probably Log(n) or n/2. Your interviewer was probably looking for something other than brute force and the approach I have listed above opens up scalability, maintainability and extensibility. The approach above allows the introduction of 'blank tiles' with a little bit of thought, can allow for other wildcard efforts (what if other tiles such as H, X or Z are on the board), and can also be used in other word games including crosswords. \$\endgroup\$ – AJD Jun 21 at 19:53
  • \$\begingroup\$ @OhMyGoodness They didn't, I agree that it mustn't have been a big-O issue. The average case is so much better than the worst case here, as you say. Did three interviews in quick succession last week and this was the least structured of them by far. \$\endgroup\$ – John Hewson Jun 22 at 17:37
  • \$\begingroup\$ @ADJ I checked the sorts and as you say, other sorting algorithms, such as heap sort O(w log w) outperform counting sort O(w+k) when k=26 and w=15. So your sort of word letters for the full dictionary will be O(n*(w log w)). Doing the sort only once does amortize its cost, but filtering it based on the tray letters is still O(n*w) because you have to look at each letter of each word in the dictionary. So you've done up-front work and still have a runtime no better than we began with. \$\endgroup\$ – John Hewson Jun 22 at 18:07
  • \$\begingroup\$ @JohnHewson - No, you do not have to look at each letter in the word. Assume you have ADD in your tiles, and the dictionary word is LEAD. Then your search is A, D, E (fail). If the dictionary word is EGG or GLUE/EGLU, then you can fail even before you get to check the word (E - the lowest char in both words, is >D, the greatest char in your tiles) or you can fail on the first char. This is the point, with both array of char normalised, you short cut the overall search. You are still thinking brute force! \$\endgroup\$ – AJD Jun 22 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.