Me clicking this video when I have never done programming in my life.
@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.
@russellgerhard46372 жыл бұрын
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.
@JacobDlougach Жыл бұрын
Why haven't you even mentioned Aho-Corasick? That would be a true linear solution.
@Febrin424 ай бұрын
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
@TonyVuolo Жыл бұрын
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.
@Zwieq10 ай бұрын
Woah🔥🔥
@TheMrKlowb9 ай бұрын
Wow that sounds like a lot of bullshit.
@morpheusft7633 Жыл бұрын
But why would you need to store the stream at all? That does not seem to be a requirement.
@varunvummadi3502 жыл бұрын
Thanks for making awesome videos Can you make a video on how to prepare for these companies
@paragggoyal155214 күн бұрын
O(nm) ? Its going to be o(m*(max length of a word))
@jwh5232 күн бұрын
ac automata
@leonmozambique5332 жыл бұрын
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).
@wrong102911 ай бұрын
You may not have the entire word, so a hashmap is no good here.
@themisfowl133311 ай бұрын
ez trie problem bro
@GauravSingh-bo1ys Жыл бұрын
Leetcode 1032
@alidir75708 ай бұрын
Hello Is this question for an internship in quant developing? Could it be asked in quant trading interviews?
@sidasdf7 ай бұрын
A little late to the party, but you should not expect a question like this in a trading interview.