Stream of Characters

HardStringstrie

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a dictionary of words up front, then receive a stream of lowercase letters one at a time. After each letter, report whether some **suffix** of the stream received so far is exactly one of the dictionary words. Implement StreamChecker: - StreamChecker(words) stores the dictionary words. - query(letter) appends letter to the stream and returns true if any non-empty suffix of the whole stream equals a word in words, otherwise false. Each query should cost O(L), where L is the length of the longest dictionary word, regardless of how long the stream grows.

Examples

Input: ["StreamChecker","query","query","query","query","query","query"] [[["ing","g","sin"]],["s"],["i"],["n"],["g"],["x"],["g"]]
Output: [null,false,false,true,true,false,true]
After "sin" the stream ends with the word "sin". After "sing" it ends with both "ing" and "g". After "singxg" it ends with "g".
Input: ["StreamChecker","query","query","query","query","query"] [[["aa","aaa"]],["a"],["a"],["a"],["b"],["a"]]
Output: [null,false,true,true,false,false]
The second and third queries end the stream with "aa" (and "aaa"). The "b" breaks the run, and a single "a" afterwards is too short.

Constraints

  • 1 <= words.length <= 2000
  • 1 <= words[i].length <= 200
  • `words[i]` and `letter` consist of lowercase English letters.
  • At most 4 * 10^4 calls are made to `query`.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More trie problems