In honor of recent news of Google developing a keyboard for iPhone...

Your input (for simplicity, all input is case sensitive):

  1. Location of standard dictionary file. File format is 1 valid word per line; in alphabetical order. Example file:

  2. Location of personal dictionary file (initially, may be empty or non-existant). Format is 1 word per line, comma separated by count of times that word was used. Example file:

  3. A stream of words on standard input (for simplicity, newline separated), in the following format on each line: "Typed_word,intended_word".

You need to emulate a predictive keyboard, as follows. For every line in the stream of words:

  1. Process the typed word character by character
  2. After 3rd character, generate the 5 most-used words that start with the currently-seen substring

    "5" is a hard-coded constant, but my example below uses "2" for simplicity. "most-used" are picked as first words when words are sorted in the order of counting; alphabetic order within same counts.

    The rules for most-used words are: the word from the standard dictionary is assumed to have the used count of 20 (that's a hard-coded constant, but my example below uses "2" for simplicity). The word from personal dictionary has a used count of whatever number the dictionary file has.

  3. If one of 5 words matches intended word, print the success: "MATCH:$substring,$intended_word" and stop

  4. If typed word is finished and matches intended_word, print it: "FULLWORD:$typed_word,$intended_word" and stop
  5. If typed word is finished, but none of teh matches or the word match intended_word, print ERROR message including both typed and intended word: "MISMATCH:$typed_word,$intended_word"
  6. Add the intended word to the personal dictionary if missing from it; or increment its usage count in personal dictionary if already present

Answers should be genuine working code - no gotchas/loopholes, no edge cases like super-small input.


(I'm going to change the constants to 2 guesses (instead of 5) and main dictionary words weigh as 2 user-usages instead of 20)

Standard Dictionary:


User dictionary





FULLWORD:abanana,abanana #after this, add "abanana,1" to custom dictionary
   # NOTE: your code should have matched "abandon,abandoned" till seeing "abana"
   # change custom dict count for abanana to 2
MATCH:aban,abanana #By now, aban matches "abanana,abandon"
MISMATCH:cat,cad # Add cad to custom dictionary

NOTE: someone asked to be able to live with no files. I'm fine with that, the simplest spec seems to be to pass all 3 inputs on STDIN, separated by empty line between the inputs.

  • 1
    \$\begingroup\$ Yep, that helps a lot, thanks. Re: IO - Instead of specifying where this stuff should live / be sent to you can rely on our community defaults to take care of stuff we consider fair. So you could say something like "a list of words containing only upper and lower case ascii letters" and "a dictionary of words containing only upper and lower case ascii letters and a numerical weight". \$\endgroup\$ – FryAmTheEggman Mar 24 '16 at 19:38
  • \$\begingroup\$ Just something to clarify: words in the standard dictionary will never be added to the custom dictionary? And the two initial dictionaries are guaranteed to be mutually exclusive? \$\endgroup\$ – FryAmTheEggman Mar 25 '16 at 1:54
  • \$\begingroup\$ @FryAmTheEggman - yes. And if it simplifies the code, sure let's make them mutually exclusive, since the natural start state is empty custom dictionary and program logic only adds missing words to custom. \$\endgroup\$ – DVK Mar 25 '16 at 2:31
  • \$\begingroup\$ Can we take the standard dictionary from stdin or function argument? Would make solutions easier to test as there's no files involved. \$\endgroup\$ – CalculatorFeline Mar 25 '16 at 2:36
  • \$\begingroup\$ @CatsAreFluffy - I suppose, if you can figure out how to separate dictionaries from data stream. I'd expect that to make the code longer but I'm fine with the idea. \$\endgroup\$ – DVK Mar 25 '16 at 2:53

Your Answer

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

Browse other questions tagged or ask your own question.