This question was asked by Jane Street. Can you solve it? (1032. Stream of Characters)

[@deadlyecho]

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.

[@cookingsection568]

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

[@Febrin42]

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

[@EdDunkle]

I'm in perpetual dummy mode

[@JacobDlougach]

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

[@DJHypnovibe]

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.

[@Zwieq]

Woah🔥🔥

[@TheMrKlowb]

Wow that sounds like a lot of bullshit.

[@russellgerhard4637]

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!

[@JackHeTech]

Hey sorry for the late reply! Your analysis makes sense, I was bulk making these videos cause I had an internship coming up so a few details I got wrong. It's awesome to see the engagement tho! I'll do better in future uploads.

[@morpheusft7633]

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

[@varunvummadi350]

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

[@paragggoyal1552]

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

[@alidir7570]

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

[@sidasdf]

A little late to the party, but you should not expect a question like this in a trading interview.

[@leonmozambique533]

suffix tree bro

[@user-dz6zd9zk2f]

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).

[@wrong1029]

You may not have the entire word, so a hashmap is no good here.

[@jwh523]

ac automata

[@themisfowl1333]

ez trie problem bro

[@GauravSingh-bo1ys]

Leetcode 1032

[@hdrkn5247]

talk is cheap. show us the code!