Me clicking this video when I have never done programming in my life.

I implemented a similar data structure for a game, called Scrabble, the data structure is called GADDAG which is based upon the DAWG data structure, "Directed Asyclic Word Graph", the main objective was to efficiently generate all the possible moves given the rack of letters.. and this GADDAG dictionary was to make sure that the move formed a correct word.

Hey Jack, thanks for the video! I have a few questions about the trie solution. First, let's say 'n' is the number of words and 'm' is the number of calls to query. With a trie, for each call to query we just need to traverse the trie. Let's call 'k' the length of the longest word in the word list. I believe the worst case runtime would be O(m*k) because on each query we're traversing down k nodes in the trie. Second, I also believe the brute force search of the entire word list would be O(m*n*k), because for each query call I must compare every word to the stream, and comparing each word requires a letter by letter comparison of at worst k letters. For the space of the trie, we could imagine a vast list of words: let's say every permutation of the English alphabet (26 characters) whose length is less than or equal to the max word length k. At each depth of the trie, we have 26 new possibilities. The max depth of the trie is k. So the total space required, in the worst case, would be 26^k. More generally, if 'a' is the size of your alphabet, then the size complexity is on the order of a^k. Finally, if we wanted to append to the back of the list, we could write the trie constructor such that it puts words into the trie backwards. This way, we just read off of the back of list to move down a path in the trie. I think it's likely I'm not totally correct because this is a rather complex problem, so let me know your thoughts!

Why haven't you even mentioned Aho-Corasick? That would be a true linear solution.

As @russellgerhard4637 mentioned it would be faster if we build the Trie backwards. Then we can iterate on the stream backwards, and we either end up in a terminal node (meaning that this suffix is a correct word) or we break as there is no transition

I started coding in assembly, then pascal, then C, and anything with strings and search can usually be sped up using binary proxies. I'd create some reduced binary representation of each word, chain them together, and then use math to quickly deduce if anything from my stream was in my overall target. I usually can speed up code at most companies written by recent CS and math grads. At one gig last year, this major payments processing company had a job that would run for 5 hours, and I devised an algorithm that would calculate the same result in a couple of minutes.

But why would you need to store the stream at all? That does not seem to be a requirement.

Thanks for making awesome videos Can you make a video on how to prepare for these companies

O(nm) ? Its going to be o(m*(max length of a word))

ac automata

suffix tree bro

Can't we just use a hashmap to store the words instead of a list. That way the search complexity will become O(1) and the overall solution will become O(n).

ez trie problem bro

Leetcode 1032

Hello Is this question for an internship in quant developing? Could it be asked in quant trading interviews?