Alright here's how I did: - part 1: got it in like 20 seconds of thought - part 2: got a variant with a trie in maybe 5 minutes thinking, wasn't exactly the s

Alright here's how I did: - part 1: got it in like 20 seconds of thought - part 2: got a variant with a trie in maybe 5 minutes thinking, wasn't exactly the same as the given one but close enough - part 3: thought about it for an hour (got nerd sniped). got a trie + recursive dynamic programming solution that'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 Let's say the string is wxyz. As we iterate, we'll split into the possible prefixes and suffixes: w xyz wx yz wxy z wxyz (suffix is empty string, we have to special-case this I think) 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. Looking up a string in the trie is O(N). But for the prefixes, we can "remember our place" in the trie, so that the cost of an incremental character is constant. So membership checking wxy only incurs the cost of y, given that we've already just looked up wx. The prefix is either a word in the dictionary, or it isn't. If the prefix is not 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 is 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're done, and we return true. If it'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's a full word in the trie or not. 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: - 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 (Here I've spoken of the "memoized xyz suffix" 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't, because you can just lookup by the index of the start of the suffix. So looking up the memoized results is also constant time.) So summing the cost of all those recursive steps, it is O(N^2) in the length of the string. The word "cantonal" 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't show up for it though, so I'll append "q" to make "cantonalq", which should return False: c -> no ca -> no can -> yes t -> no to -> yes n -> no na -> no nal -> no nalq -> no ton -> yes a -> yes l -> no lq -> no al -> no alq -> no tona -> no tonal -> yes q -> no tonalq -> no cant -> yes o -> no on -> yes (-alq suffix is memoized) -> no ona -> no onal -> no onalq -> no canto -> yes (-nalq suffix is memoized) -> no canton -> yes (-alq suffix is memoized) -> no cantona -> no cantonal -> yes (-q suffix is memoized) -> no -> return False I wouldn'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'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'd get very flustered and self-conscious. Maybe I could have narrated the "cantonalq" example, idk. Generally I don't mind "pure" DS/algo interview questions, so long as they'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's not the same thing. It just seems like a sick hazing ritual that nerds inflict on one another. Conclusion: bad interview question.