Word Selector: Solution Walkthrough
Word Selector is a small helper for a word game. Given a list of words, its job is to select a few that together use as many distinct letters as possible, without repeating any letter. The repository already includes code to clean up the word list and make a quick guess at a pick.
The round lasts 60 minutes and has four phases:
- Phase 0: Understand the code. Read the existing implementation and show that you understand how it works.
- Phase 1: Fix a bug. Correct an issue in how words are cleaned up.
- Phase 2: Find the best pick. Replace the quick greedy guess with one that always finds the true best pick.
- Phase 3: Make it fast. Make that exact search fast enough to handle 50,000 words, with up to 4 words per pick.
At its core this is a small exact search, and most of the challenge comes down to four details.
First, a letter bitmask cannot see repeated letters within a word, so a word like letter can slip past the overlap check. Second, the obvious greedy pick doesn't always produce the best answer, and the visible tests won't show this. Third, the tie-breaking rule, which favors fewer words, decides the order in which Phase 3 runs its searches.
Finally, Phase 3 has to speed up the exhaustive search from Phase 2. The key is a bound that prunes branches early without ever cutting off the branch that holds the best answer.