On a great interview question
Alright here&#x27;s how I did:<p>- part 1: got it in like 20 seconds of thought<p>- part 2: got a variant with a trie in maybe 5 minutes thinking, wasn&#x27;t exactly the same as the given one but close enough<p>- part 3: thought about it for an hour (got nerd sniped). got a trie + recursive dynamic programming solution that&#x27;s O(N^2) in the size of the input string. the actual solution took me 15 minutes, the rest was trying to prove the the big-O<p>Let&#x27;s say the string is wxyz. As we iterate, we&#x27;ll split into the possible prefixes and suffixes:<p><pre><code>    w xyz
    wx yz
    wxy z
    wxyz (suffix is empty string, we have to special-case this I think)
</code></pre>
If we find a prefix-suffix pair where the prefix is in the trie, and a recursive function call on the suffix returns True, then we return True. If there is no such pair, then we return False.<p>Looking up a string in the trie is O(N). But for the prefixes, we can &quot;remember our place&quot; in the trie, so that the cost of an <i>incremental</i> character is constant. So membership checking wxy only incurs the cost of y, given that we&#x27;ve already just looked up wx.<p>The prefix is either a word in the dictionary, or it isn&#x27;t. If the prefix <i>is not</i> in the trie, we advance to the next character and repeat, with the next prefix grown by one character and the next suffix shrunk by one character. If the prefix <i>is</i> a word in the trie, we call our function recursively on the suffix, and memoize the result. If the recursive call comes back true, we&#x27;re done, and we return true. If it&#x27;s false, we advance to the next possible prefix and repeat. If we reach the end, the prefix now comprises the whole string, so we just return whether it&#x27;s a full word in the trie or not.<p>In the base case of the recursion, the suffix is a single character, which is a constant-time lookup in the trie. So every recursive call after that can just look up that memoized result. Same for the 2-character suffix, 3-character suffix, and so on:<p><pre><code>    - 1 character: z:    z: 1 operation
    - 2 character: yz:   y, z suffix memoized, yz: 3 operations
    - 3 character: xyz:  x, yz suffix is memoized, xy, z suffix is memoized, xyz: 5 operations
    - 4 character: wxyz: w, xyz(memo), wx, yz(memo), wxy, z(memo), wxyz: 7 operations
    - N characters:      prefix 1, (N-1)(memo), prefix 2, (N-2)(memo), prefix 3, (N-3)(memo) ...: 2N operations
</code></pre>
(Here I&#x27;ve spoken of the &quot;memoized xyz suffix&quot; and so on, so you might think the lookup time grows with the length of the suffix, because you have to hash it. But actually you don&#x27;t, because you can just lookup by the <i>index</i> of the start of the suffix. So looking up the memoized results is also constant time.)<p>So summing the cost of all those recursive steps, it is O(N^2) in the length of the string.<p>The word &quot;cantonal&quot; works as a good test case because it has lots of sub-words: can, cant, canto, canton, a, an, ant, anton, ton, tonal, on. The memoization doesn&#x27;t show up for it though, so I&#x27;ll append &quot;q&quot; to make &quot;cantonalq&quot;, which should return False:<p><pre><code>    c -&gt; no
    ca -&gt; no
    can -&gt; yes
        t -&gt; no
        to -&gt; yes
            n -&gt; no
            na -&gt; no
            nal -&gt; no
            nalq -&gt; no
        ton -&gt; yes
            a -&gt; yes
                l -&gt; no
                lq -&gt; no
            al -&gt; no
            alq -&gt; no
        tona -&gt; no
        tonal -&gt; yes
            q -&gt; no
        tonalq -&gt; no
    cant -&gt; yes
        o -&gt; no
        on -&gt; yes
            (-alq suffix is memoized) -&gt; no
        ona -&gt; no
        onal -&gt; no
        onalq -&gt; no
    canto -&gt; yes
        (-nalq suffix is memoized) -&gt; no
    canton -&gt; yes
        (-alq suffix is memoized) -&gt; no
    cantona -&gt; no
    cantonal -&gt; yes
        (-q suffix is memoized) -&gt; no
    -&gt; return False
</code></pre>
I wouldn&#x27;t have been able to do this in an interview setting. Most of my time was spent gazing vacantly off into space. Interviewers want you to narrate your thinking but I can&#x27;t do that .. I have to shut the fuck up for a while as my brain works. But long periods of silence are intensely awkward in such a setting and I&#x27;d get very flustered and self-conscious. Maybe I could have narrated the &quot;cantonalq&quot; example, idk.<p>Generally I don&#x27;t mind &quot;pure&quot; DS&#x2F;algo interview questions, so long as they&#x27;re plausibly related to something one might actually do. I have actually used tries before on a real problem. Dynamic programming with memoization tricks? Never. Has anyone ever had something remotely similar come up in real work? I mean I know there are caches everywhere but that&#x27;s not the same thing. It just seems like a sick hazing ritual that nerds inflict on one another.<p>Conclusion: bad interview question.