[00:01] through an AI coding interview question with you. And so, it'll be a question you can see how I, as a former Meta staff engineer, approach the problem. And I'll do it in one take, so you can see my thought process, mistakes, and
[00:14] Uh as the current co-founder of Hello Interview, I've conducted dozens of AI coding mock interviews. And so, while I'm solving it, I'll also talk through how you can stand out in your next AI coding interview. I know there's a ton
[00:28] type, so hopefully this goes a long way to clearing some of that confusion up. Like when to use the AI, how much to use it, and all of those good things. So, and let's get into it. If you head over to hellointerview.com, on the left-hand
[00:42] AI coding. This is going to show you all of the AI for you. Each one of them has an answer key. I strongly suggest that you don't problem. You're just going to learn so much better that way.
[00:55] But, there's lots of problems to choose from. Uh most of these come from user interviews, they come back, they let us know about their questions. Um the reports, we come here and we we translate into an actual problem. So,
[01:10] is that I'm going to walk through one of these problems in full. one take. You guys are going to see the messy mistakes, I'm sure that I'm going As for the problem that I'm going to choose, I probably should have thought
[01:24] choose, I probably should have thought of this beforehand, but I'm going to do container. This is a problem I know less well than get to see my real-time thinking. I'm sure I'll even make mistakes throughout.
[01:38] lot of starter code, I know that. And I think that's good. You guys don't want code. I think that's going to be a little bit boring. I want to try to get possible. So, without further ado, let's go ahead and do word container. I'm
[01:50] going to click start. Everybody can do one of these for free. Unfortunately, to um you need to be a premium member of Hello Interview, but everybody can come in here and at least give one a try. I'm going to choose Python.
[02:03] suggest you guys do if you're practicing. This is going to take you step-by-step through code comprehension, debugging, implementation, optimization, having you explain your solutions, all of that. We're going to do sandbox. This
[02:15] is basically just like an empty environment with no questions, no AI Um, basically this simulates kind of what a real interview would be. And I want to simulate a real interview. So, I'm going to click this one.
[02:28] I'm going to play the role of both the interviewer, the candidate, and the all three of those. Hopefully that's useful. You guys, of comments. But, when the
[02:41] interviewer is going to introduce you to what you're looking at. Now, what we're looking at is the Hello Interview version of the CoderPad environment that coding interviews. They're very, very similar. They're structured this exact
[02:56] files on the left, you have, of course, an editor in the middle. On the right-hand side, you have a panel which has the instructions, the output for when you run the code, as well as the AI assistant here, which you'll be
[03:08] able to use and you can drop down and change the models. Um, your interviewer will, after orienting you, of course, explain the problem to you for a moment, just like a traditional coding interview.
[03:20] moment to maybe explain this problem to you all as problem is. So, what you do is you end up with a and it has a bunch of text files. And if we look at the small one, you can see
[03:34] this text file just has a bunch of words separated by new lines. The goal is that we are going to take in these files and then return the subset of words that are containers.
[03:48] what is a container? Well, a container is a word for which there's another word in the list that is fully contained in it. So, it's easier with an example. Apple here would be in the returned set
[04:01] um because app is contained in apple, so apple is a container. Similarly, application would be returned cuz app is in application, so it's a Banana would be returned, ban is in banana. You get the picture.
[04:15] easiest, which is just apple, app, banana, and nana where the return value should be apple and banana cuz those are the two containers. Okay? All right, so we're just trying to find the words in the list of words that contain another
[04:28] word in the list. Easy enough, hopefully. You'd have some time to ask your interviewer if you have questions, of course. Um but I'm not going to ask myself any in this case. Now, they'll introduce you to this
[04:40] instructions panel, which has a list of tasks. but by and large, these AI interviews get broken down into three phases. The take some time to just understand the code base, right? Orient yourself, the
[04:55] key classes, key functions, et cetera. From there, there's usually a bug somewhere. And so, you'll use the test cases to identify and then fix the bug. the core uh thing that needs to be implemented is. And then, usually you
[05:09] need to optimize it. The tests kind of show that it's either too much space or some uh additional conditions or something of this nature. interviews. You have about 50 minutes to do them. The interview is an hour long,
[05:22] on either side. So, you usually have about 50 working minutes. Um just leave you guys with one tip. This is probably some of the most value that
[05:34] And that's that the number one mistake I see in having conducted so many of these sessions now from candidates is that they're too hesitant to use the AI. to not use the AI it allow the interviewer to evaluate your ability to
[05:50] leverage or wield it in order to arrive at an appropriate solution. Like these questions are meant to be intentionally difficult. And so if you're not relying evaluate your skills there. And you're also setting yourself back. There's a
[06:02] at twice the pace. So we'll show plenty of examples as we asking questions like what is the answer or find and fix the bug are not good AI or find and fix the bug are not good AI questions. Um but being informed based
[06:17] on what you know about the code base and then using the AI to both increase that understanding, to do some of the implementation, um to help you have, that's what you're going to end up um leveraging it most for. So you'll see
[06:30] So without further ado, I'm going to jump into this exactly like it was an interview. Um like I said, I haven't practiced this problem. Um more than the average person, but I think I'll still probably stumble my way
[06:44] The first thing that I'm going to do is I'm going to understand the code base a little bit. And so I'm going to start with the main function here. uh I'll run it again just so I can see what it does. Begin code output. It
[06:58] come from? So I have words get example words. That's in words. So what is that? Okay, so that just returns a simple list of example words. No big deal. That's
[07:11] pretty straightforward. I create a word list with those words. So word list is a class here. It looks like it takes in a list of words. Uh and then we instantiate a words and
[07:25] word set. Okay. And these are basically just the valid words that we passed in. Okay. How do we know that a word is word is valid?
[07:37] a space in it. Okay, I won't get too deep into that but this instantiates that. We instantiate a solver. to solve. Yeah, so there's nothing here. A solver takes in that word list class.
[07:50] and then find containers. That's where we want to return, obviously, our list implemented, which is why we just get none here. So, we call containers, find containers, containers were none. Cool.
[08:05] Uh if there are things in the containers, then for each container Interesting. Okay, so we'll be able to like use this to debug. understanding there. I'm going to come back to these two key
[08:19] classes again. They're short. Word list, valid word is no space, get words, get substring. So, this takes the container and the contained. I assume it returns whether or not contained is in container.
[08:36] Uh that might be our bug. We'll have that later. Uh words it Okay, just loads. files. And it returns the list.
[08:50] fast. Of course, I I'm assuming this is the least interesting thing for you guys interview, you'll have a bit more time to understand this. Practical advice. I classes now. They're they're really short. Um
[09:04] candidates and I've seen candidates take two approaches, both of which are equally effective. The first is that you can come here and say for words.py and list.py add single
[09:19] bad typer sentence comments to each core function So, I might do that right out of the gate, actually. I noticed these classes gate. And then
[09:34] reading through the classes. And as you can see they're coming in here. And so this is just going to make um comprehending of the code a lot quicker. Cuz I can read the string, see what it's
[09:46] supposed to do. Make sense of it. Go from there, right? So it's sum with words. See if it goes on to word list now. So initialize the word list with valid unique words from the input list. Yep,
[09:59] that's what we discussed. Uh Did you freeze on me, buddy? Hello.
[10:19] checks if the word is valid by ensuring it contains no spaces. Return a copy. that's a pretty effective thing to do there. Another thing I've seen as effective, is right in the beginning you can say something like give me a
[10:32] you can say something like give me a concise bulleted list of the key functions per class and what they do. So maybe even before you read the code, you just ask for that. And it's going to
[10:45] So the word list class, you know, whatever. We already know it, so we're this is in an effort to just understand the code as quickly as possible. So many candidates are hesitant to use the AI early here. Um
[10:57] your understanding. So by all means, please do. probably don't need to spend too much time reading the code cuz the best way to really understand the code is to work backwards from the test cases.
[11:09] And so if we go back to our instructions, it tells us that uh we there's some test cases. Those tests are going to be here in test word list. We need to run these and figure out what's wrong.
[11:22] cases to really understand my understanding and I'm going to be understanding and I'm going to be communicating with the interviewer case we instantiate a word list with apple, banana, and cherry.
[11:35] Um we remember that the instantiation here just takes valid words. These don't have spaces, so they're all valid. There's no duplicates. So, I'd assume words will have all of those uh words now.
[11:47] So, it should return three. And let's test that. already passed. Great. So, that returned three, it should. Uh apple apple banana, duplicates here. So, it should return two. It does. Okay, because it's going
[12:01] looking at. Now, assert true contains as substring apple app. Okay, let me just validate contains as substring. Again, container, shorter one second. Um
[12:15] passed. Bigger one, shorter one passed. Cool. Cat dog, dog is not contained in cat, so that's false. Cool. Let me just kind of prove might do this in the interview. Like, adding additional test cases is cool.
[12:29] So, if I do this in the inverse, this should be false. Right? And so, test word list still passes. Cool. positions. What does this do? Assert true contains as substring he is in
[12:43] hello. Yes. It's the start. I guess who cares where it is. We're just testing that it works. Low at the end, L in the middle. They'll return true, and they did. Okay. So, now we get here
[12:55] and you'll and you'll see certainly in the meta interviews that The whole point of the question marks is to test your code understanding. Like, expected to return in the first place? And you can chat with your interviewer,
[13:10] code and make sense with it, and you know, maybe leverage the AI if you need So, in this case, we instantiate an empty word list. I guess we're not even going to use it. We're just using it to call the the
[13:22] method here. Apple apple. Um >> [clears throat] you instantiate a word list, you can't have two words of the same anyway. So, this is almost like a can't get here state. We realize that, right? And as a
[13:35] interviewer at this point and be like, "Can a Can a word contain itself?" Um now, if I was the interviewer, um which I am here in this case, I would And it seems like that makes sense from the setup that we have here. So, I'm
[13:50] going to make this expected value be false, okay? error. Now, I remember from reading the code up. So, let's go look at it. Contains a substring, container, and contains.
[14:05] It says, "If the length of the contained is less than or equal to the length of the container, then return whether it's in it." Okay. Um clearly, I think this should be less
[14:17] that's where we're failing right now. We have apple passes that, and then of course it's in it. Um bug fixed there. I'm going to explain that of course to my interviewer that
[14:32] contain itself, um then the contained word should always be strictly shorter than the container. And let me run again, and I passed. So, fixed the first bug, but let's see if anything else comes up there.
[14:47] Um def contains longer word. Oh, look at this. This is here. So, I guess we're one step ahead. So, does app contains apple? No, this is don't just do the in, right? So, this should return
[15:03] And does. Love to see it. Um test valid normal word. So, is valid word hello? It should return true. There's no space in it. So, it's all good. Okay.
[15:18] it's all good. Okay. Test valid word empty. string a word according to this test? No. code tested for that. I don't think it did.
[15:32] So, we need to go look at is valid word and it looks like the expectation is that is valid word is false for an empty Uh and so if we go back to word list, we have is valid word which just checks
[15:45] spaces right now. So, if there's a space in the word or word equals equals empty string, then return false.
[15:59] Return true anyway. We could make this a ternary. Or excuse me, not a ternary. We can just do return of the inverse of this. mess with it too much. Okay. Um still passing. Cool.
[16:14] What else do we have here? Test valid Oh, test valid word no spaces. Yeah, so this should be false because there's a space in the word. Our words have to be far. Passes.
[16:26] What about this one? We instantiate a word list with apple, normal word, empty string? Nope. Banana, good. Hello world, nope. Cherry. should be three. And it is. Okay.
[16:41] Okay. Well, we fixed the two bugs. Um The bugs are often times pretty straightforward. Maybe in this case they were a little a little on the easier side. Um but especially if there's more
[16:54] nervous in an interview, you know, I maybe I maybe be making this look easier than it is even I think with that exercise, but nevertheless, I wanted to fly through that a little bit. Um that still ended up taking us about 15
[17:07] Is that true? Well, yeah, I guess including the the So, um let's go back to our instructions. We fixed the bugs, now we need to implement solver. So, complete five find
[17:20] Okay. test solver. Looks like we'll have some test cases So, let's implement this first. Okay, um let's talk about good and bad
[17:33] they could come right over to the AI and they could say implement solver. is your What is your interviewer going to learn from you if you do that? type implement solver. All right? So, that's not the greatest. Instead, what
[17:49] that like I want to hear your thought process. Don't spend too much time on this, but at a high level, teach me that you understand this problem, you understand what a solution could be, and then let's go ahead and engage the AI.
[18:01] the code. It's 2026. I don't need to be writing code anymore. Um but I want to make sure that I'm always in control and that I'm I'm um kind of adding that additional value.
[18:13] for a second and I would say, "Immediately out of the gate, I see a And that brute force solution would probably look something like this. I'm going to write it down both for myself, but so the interviewer can see it, too.
[18:25] Is that I'm just going to say, "For each word, every other word, okay, and then see if contains
[18:37] if yes, add it to, you know, list to return. Whatever. So, for loop is going to for every single word check every other word. It's going to call that helper function that we had. What was it? Contains as substring.
[18:54] Um and if it's true, it'll add it to the list that we need to return. So, pretty straightforward. Um I'm going to come over here and I am going to force the AI to implement that just for
[19:08] have to go with the naive brute force I think it's useful to build your way up. Kind of gives you time to build your So, I'm going to say I'm going to put it
[19:20] ask in edit mode, by the way. Edit allows it to make changes directly to file, but it'll give you code here. So, if you're just brainstorming and you it, put it in ask. If you want it to actually uh be able to edit, put it over
[19:35] here. So, I'm going to be kind of explicit here, and I am going to say implement find containers using the helpers in wordlist
[19:49] Just do brute force nested for loops. Okay. Um so, that should then go implement our simple solution.
[20:01] okay, it was pretty quick, but I'll be talking to my my interviewer again about the solution, what I'm expecting to see Any code that the AI gives you, you're going to want to be able to make sense
[20:13] I've seen a lot of candidates like read line for line and like narrate line for kind of rolling my eyes. I don't care. I want to hear your happening, and I want to see that you checked it and you understand that it's
[20:26] And so, I'm going to do exactly that. I've already told you what my expectation is, and so we instantiate an empty list for containers. That's what far. Words, get the words from the wordlist, straightforward.
[20:39] For container word in words, I love that we we named it that. That makes it clear. Thank you, AI. For container words in in words, and then for the nested for loops. If contained word does not equal
[20:51] contained word, it's fine, but I don't need that, right? substring, we do the length thing. So, that was just kind of unnecessary. Um if self.wordlist contains a substring container, remember container first,
[21:05] then container's out of pen, the container. This break here is great, right? So, if we had I think that we had an example here where banana has nan and ban and nana. By the time we find out ban, let's
[21:17] going. Um so, this looks good. This looks like it works to me. Time complexity-wise, right? This is O of N. This is uh O of N.
[21:31] And then this itself, this contains a substring does in right? Right? Uh I think so. Uh I think so. Um so, that's another O of N.
[21:47] So, N we're going to say N is the number of words. M is the length of the word. Um so, this whole thing is going to be O of N squared times M. So, I'm talking that to my interviewer. But let me come here and say what is the
[22:03] city if N is num words and M average length of word. Now, this is really important. I'm going My last one I was pretty explicit cuz I wanted the brute force one.
[22:18] interviewer what I think it is, but then I'm asking the AI with not being overly specific. I'm not saying is it N squared times M, right? I'm letting it do it. Um not going to be sycophantic, and so I can see if it actually agrees with me.
[22:32] In this case, M for each contains, so it looks like we nailed it. N squared times M. Okay, cool. Let's This looks good to me. Um let's see if it works. And so, instantiates a word list with cat and dog.
[22:46] Solver dot find. Actually, the very first thing I want to do is let me go run that main cuz that looked pretty useful, right? So, main apple banana application details. Apple contains app and it contains an
[22:59] app. application Cool. Okay. Uh got a little tripped up here cuz it returned application twice. Um but fortunately, uh the container word still just has it once. So, that
[23:11] looks right to me. Love that. Um but let's go ahead and run the tests. So, the first test here, find containers. Okay, it's just it's just asserting that expect. Um
[23:24] so that's great. Um okay, what's the next one doing here? We have apple, app, banana, nana. Call find containers. And we're checking what's expected. So, this was our canonical example.
[23:36] So, this was our canonical example. We expect apple and banana. And they're sorted. Okay. see. Cool.
[23:49] Cool. Um like, why is it returning so many tests here? Test solver. Okay, both of those passed. Silly. Okay. Um test no containers.
[24:05] fish. Find containers. None of those contain each other. So, empty list. Let's see. Um next one. And I'm doing tests one by one like this, right? I I I see
[24:19] candidates uncomment all tests and then run them and then they're just like they have to do and they end up commenting them all out and leaving just yourself the headache. Go one by one here. All right.
[24:32] Um multiple words contained. So, we have work, worker, yes. Rework, yes. Working, So, these three are what I'm going to return expected count.
[24:45] Assert equals. We want count this time. Okay, cool. like if I was in an interview, I would be like, candidate if they put the list here, they'd run it, and they'd figure it out,
[24:57] but like cool. I caught myself I I was moving quick, I read it, I saw it actually wants to count. Um so kind of just shows my code reading comprehension maybe. Um so that one worked. Test nested
[25:10] containers. And yes, ant, rant, grant. So same thing, all four of them have A. Obviously ant also has an and so on. Count again. Um so let me do four there.
[25:23] Cool, cool. So far brute force is crushing it. Um test from small file. So we get them from that small file. Find containers, assert that it's a list, expected minimum.
[25:38] pass. Seems kind of stupid. I don't know, that doesn't make me feel great about my correctness. So I want to update this test. What is this? Word small, get word small, word
[25:53] small. So how many should this have? Apple, yes, so one, two, three, three, four, five, six, seven,
[26:05] eight, nine, 10, 11, 12. So I count 12. I did that fast, so I might be wrong. Um but I want to actually test my correctness. I think this test stinks.
[26:17] Um so I'm going to do assert equals the length of result is expected. cool. Um
[26:32] cool. So that was interesting there. Um in the interview like there's probably but I think it would look really good. If a candidate did that to me, I'd be down and a positive on their verification. Um
[26:45] written test that they added a new test or adjusted a test, so it's a place where you can definitely um kind of show some brownie points. So, Um test medium word list. What does this
[27:00] words, find the containers. So, we're timing how long find containers takes. Um assert is instance here. So, I put the
[27:12] So, this is just seeing how long it takes for us to do find containers. There's no correctness here. So, I guess we've tested correctness. under a second. Our brute force probably fails.
[27:24] No, our brute force is still stupid fast. Okay. would. Uh what about this one? Large words. Now, we got 5,000 words. So, order magnitude higher. Um and it should be half a second.
[27:41] force breaks us, right? So, we're close. 0.55 seconds. but we're slow. And so, we need to optimize. time. Yeah, okay. Uh basically it's telling us that. So,
[27:55] Now again, I could go right to the AI and I could say "I need an optimization. It's not the end of the world. You could do it. It wouldn't be my my my favorite as an interviewer. Um but I'm not saying I'm
[28:07] if you understand all the code that comes out of it. But let's just take some time to actually think through this and
[28:22] I'm checking each checking each word against every other word. And then I have this O of M contains a substring. That is standing out to me as like a
[28:34] first optimization. It kind of sucks that that's O of M, to be honest. Like I I should be I can make that O of 1, I imagine. I imagine. Um
[28:53] So, what could I do? If I use the set here to make this O of one, I could have a set with all of the And then I could try each substring of a given word against that
[29:06] set, right? Okay, yeah. So, if I had So, let's just say I had rework as top-of-mind from an example that we just had. All of rework's substrings are r e w o r k, then r e e w
[29:21] w o Whatever, you get the point. Um all the way until we get up to rewer and ework and finally rework.
[29:33] So, I could try all those substrings. And now, if there was like work also in And now, if there was like work also in the list, then in the middle here, you know, dot dot dot comma work, I would have work as a substring.
[29:47] And if I check this substring into the set, Okay. And so, creating all of these And so, creating all of these substrings, this is O of n squared.
[30:02] But then I get O of one on the lookup. Okay. So, I think that's I think that sounds decent. I think I think that sounds decent. I think that's what I'm going to do. Um
[30:19] ahead and telling the AI to do that like I did before, and this is a common pro tip here, big pro tip. If you tell the AI to do something, it's were right. You were so smart. That was so great."
[30:32] going to do here is I'm going to be cautious. I'm going to keep this in my but I'm going to delete that so the AI can't even see that old version. think. Yeah, I'm going to start a new chat here, so I'm not biased with the
[30:46] previous junk. And what I'm going to say is um give me a concise list of options to optimize
[30:59] find containers um beyond the brute force solution. So, had you just written this and never talked to the interviewer beforehand,
[31:12] bad, but it's okay. But, what I did here is I had uh talking to the interviewer about what I think is going to be a good approach, coming to the AI and saying like, is the set approach good? I'm telling it to
[31:24] maybe there's something better that I didn't think about. And even if mine is that without it being um kind of forced into it, right? So, I'm going to ask that question here on a blank slate, unbiased by anything.
[31:39] Based on the current brute force solution, solution, still knows that.
[31:51] efficiently find all words that are substrings of a given word. Suffix array, process words into suffix structure with fast substring queries. Hash-based grouping, group words by
[32:03] length. Sounds like a heuristic. Algorithm options, early termination, Algorithm options, early termination, bidirection, hash. The string match uh okay.
[32:24] pretty interesting. I have a feeling that's going to end up being our most optimal. Um should I jump right to it? Uh
[32:37] kind of take the suggestion here and go in that direction, but I set thing is also viable. I kind of want to try it first. So, what I kind of want to try it first. So, what about if we had a set with all the words
[32:52] and then iterated over all sub substrings checking against the set. So many spelling mistakes, but good thing AI is smart.
[33:05] solution. Okay, never trust it when it tells you that. set for each word generate all its substrings, check each substring against word as a container. Time complexity.
[33:25] times M. Yes. This approach would be N times M squared. times one Significantly faster.
[33:37] Okay. Um Gosh, bad spelling. Implement that approach, please.
[33:50] interviewer. They understand that I understand what I'm talking about here. word. I'm going to check all of those substrings against the set. The creation substrings against the set. The creation of that substring is M squared. And then
[34:03] uh the set is O of one. We do it for every word, so N times M squared. We got the words. word set
[34:18] for that? get word set I don't know. Honestly, kind of kind of silly, but word set. Yeah. Kind of silly, but I want my interviewer
[34:30] to know that I'm paying attention. Um so self. word list.get word set Wasn't there a get words, too? What is it doing here?
[34:46] like these are showing well in the interview. You want to be careful lot of candidates who like get over eager and are changing a lot of things have just done that. We might hit run and it might break. Um but it's nice to
[34:59] Now, for word in words, okay? So, that's our O of N. It's our O of N. Generate I for range and length of word. Okay. For J in range I plus one length of
[35:14] word. This needs to be plus one, right? Substring equals Uh so, we get the substring.
[35:27] word set. If it is, appended the word, right? And Um else continue.
[35:39] So, this makes sense. This is This is our O of N squared. set. That's our O of one. We break if we already found one. What's this else continue? Uh for
[35:58] still in the containers. All right, let's run it and see what happens. Got it wrong. It got it wrong. Oh, boy. Oh, boy.
[36:13] The hell's this? We want to go till the end of the words, We want to go till the end of the words, right?
[36:25] What happened here? Um so weird substring I'm going to have to actually analyze this. This is annoying. For I in range length of words
[36:43] to debug this. I want to look at the substring and the word set. Run it again. Oh boy, that's annoying. Oh boy, that's annoying. So I'm going to run main.
[37:02] So let me do container and then contained consistent with what we've been doing.
[37:14] because we're counting our own word. So substring is in word set, yeah, like no duh, right? So it's if substring is in word set and substring does not equal word then append it, right?
[37:33] Okay, and it all passes and it's damn quick. 0.0006. Okay, wait, so what about this one? Is it the same It's the same thing. No. Yeah, okay. So we I was right about that, too. Okay. Wow, the AI really
[37:48] screwed us there. That was dangerous. Okay, that was dangerous. Wow, what's the lesson there? Obviously the clear lesson is like don't always trust the AI, but I'm actually surprised the AI screwed us so hard there.
[38:00] Um I debugged, obviously. I could have just asked the AI what the issue was and hopefully it would have ended up telling telling us correctly. Um
[38:13] I guess this is just a warning to you guys, right? Like the AI is not always ready. I was so on top of the code. I understood what the solution was supposed to be doing. I added a print statement um so that I
[38:25] was able to see what ended up going wrong and as a result was able to kind of appropriately debug it. So, yeah, we got a we got lucky there, I guess.
[38:37] Now, here's what I'm going to do. I'm going to remove What did we say this was? We said that this was O of M squared Right?
[38:51] this is the M squared. Ooh, what about this? Word IJ, certainly in Python we're splicing a word which means we're allocating new memory for it and moving it over there
[39:05] up to length M, average M and a a half M. This is M cubed. This is M cubed cuz that's M. This is M cubed cuz that's M. M M M N.
[39:19] It's just wicked fast because so long is small. This is M cubed. It's only wicked fast because so long as the list is longer than the words are this is a good solution. Otherwise, it's a bad solution.
[39:31] I'm going to clear. I'm going to make sure I don't have any of my comments about complexity and I'm going to say what is the time complexity of
[39:43] find containers where N is uh number of words and M average length of words. You guys are probably looking at this watching this knowing something I don't,
[39:56] watching this knowing something I don't, but M squared. I didn't think about this. I didn't think about this. So, we have N M M M. So, it's M cubed.
[40:09] lesson here, long words are going to not work. Um tests if anything. Let's see.
[40:26] we're passing, we're flying. So sick. Huge word list. What does this one look Okay. So this is a big N, small N's. So it should fly. Yeah, it's fast. A little a little
[40:39] slower here. Um, It even says requires optimization, stupid. just making sure same code.
[40:59] long. Yeah, look at this. These aren't even words. we're going to be screwed is because we're doing M cubed on every single one of its substrings, and to do that, um, you know, we're finding A I and J.
[41:14] through all the J's. Um, and then we're also doing that substring splice. So I bet if I run this, we're going to time out.
[41:30] needed to be one. So we need to get even smarter here. Well, I mean, was probably going to be good, right? So I've kind of
[41:42] been tipped off to that, which is why me asking that question about like what are thing to ask. And we know we could have jumped right to the trie potentially. us pretty far, and I think the interviewer would have appreciate this
[41:54] Um, but I know a trie solution's probably think about what this would be. Uh, uh, maybe just quickly for anybody who's watching this who doesn't know what a trie is. A trie is a tree
[42:07] for which each node is a letter. The edges connecting letters that are subsequent in a word. Um and so like concretely you have some root and let's say we wanted to add to the tri that word rework then we would
[42:19] add R E W O R K like that where each of those are nodes and each of those are edges. And then if I wanted to add like reward then you would branch
[42:32] A R D. And so if you wanted to check if reward was in this tri you would just walk it reward and you would get there and you would find out that it is in the
[42:45] tree or in the tri. Um so that's what a tri is. Um how do we construct this tri? So it's that M cubed that is killing us.
[43:04] How do we make that not be M cubed? remember we were writing out all of the different substrings of rework and it
[43:18] was just so long. There were so many substrings. N squared or M squared. We don't need most of those. How do we what do we need?
[43:38] say let's say I needed the word re. Let's say R E W is a word obviously it's not but I would walk R E W and then I got to W. So I know wait a
[43:51] and then I just need to walk to the end of the word to find out what the actual word is. Right?
[44:03] this. And so then my tests that I need to be testing are just the suffixes. are just the suffixes. They're just the suffixes.
[44:21] I'm going to create a trie with all of the different words. So create a trie with every single word. And then for every word And then for every word check all of its suffixes.
[44:34] Because if any suffix gets to the end without, you know, having a mismatch without, you know, having a mismatch then that word is the container. Yeah, then that word is the container.
[44:52] Um Concrete example would be that if we had I'm just going to make this easier on myself and do spaces. Let's say we had banana and then we also had
[45:07] nana. Those are two words. of these checking just their suffix. So we built And then now for banana, I'm going to try
[45:20] I'm going to try banana and it's going to match, but it's the I'm going to try the next thing, which is just an anana. Banana. It's just anana. There's no a a root node, so no nothing. Then I'm going to try nana.
[45:34] Match. So I know that banana the word I was trying all of its suffixes. And the key here is that to try just the suffixes is O of M. It's not O of M squared.
[45:46] Cuz we're just trying b anna nana ana na. That's almost all of them. through this. Let me take Let me take a break. In a real interview, you probably Like you can jump over to the AI and start asking it questions to understand
[45:59] little fun and I don't know if you guys enjoyed seeing my thought process there or not, but um this is this is what I am landing on. So, let me say here um
[46:13] I think there's a tri solution. Again, I've communicated my interviewer with all the words. For each word, try all of its suffixes. If there's a match, its suffixes to the containers. But, I'm not going to say that explicitly to the
[46:27] uh I think there's a tri solution. Explain it to me. let's just see if if it agrees, right? I don't want to like force it to do the same thing as me. So, I'll explain how to find containers.
[46:42] Tri solution, a tri prefix tree. Prefix. Have I been saying suffix when aren't they suffixes? Uh can reduce to O of N times M squared. Yep. By limiting this tree creation order
[46:56] head, build a tree for each word, traverse all possible substrings of the traverse all possible substrings of the tree. We don't need to traverse all substrings.
[47:10] Just the suffixes. Right? Like for rework God, I shouldn't have said it right. Um Hm. Be skeptical. Is it cool?
[47:26] We don't need to traverse all substrings. Just the suffixes. So, for substrings. Just the suffixes. So, for rework we only test work work. Okay. Okay.
[47:46] Okay, so either it's being sycophantic and we'll find out or Um it generates all possible substrings, not suffixes for rework.
[48:03] Time complexity. What? No, I don't need all of that.
[48:23] we only need to check subtext six subtexts. So, for each word it's M not M squared. Um me? Can you disprove this or is it right? I
[48:39] you're absolutely right to question this. Looking at the problem, we want to this. Looking at the problem, we want to find all pairs.
[49:05] We missed finding the rework contains rew.
[49:25] Uh that's right. Rew is a prefix of rework, not a subtext of it. It only checks subtexts of rework. We don't only check counter example. Hello, ello.
[49:40] should check on rework. So, if I have if I have rew rework and I have rew, they're both in my tree, my tree, then when I'm testing rework.
[49:57] backwards. Conclusion, we need to check all substrings.
[50:10] substring creation thing. Yeah. Yeah. Huh, huh, huh. tree is going to allow us to not have that uh this part.
[50:26] Which is going to get rid of one M, which is going to make it M squared. anyway. I guess I was wrong about the suffix thing, and I see why here. I still feel like there's a way to get that to work.
[50:43] implement it. Mhm, mhm, mhm.
[51:01] So, find containers, gets the words, containers, build the trie, so create a trie node. Trie node just has children, and then the terminal is word. For car in words, for car not in node. Okay, so we're just building the tree.
[51:15] word in words, found container equals false. For I in break. Otherwise, for J in length of I length Otherwise, for J in length of I length of word,
[51:29] Found a valid substring. If node is word, we're only doing it if we found a valid substring. we found a valid substring. Found container equals true. Okay.
[51:43] 0.136. Um ended up being longer than I wanted it to. I'm so sorry. You can see what the final solution is here. It's a try where for the try we
[51:56] put every single word into the try and then we check all possible substrings. This avoids us from doing the splicing for every single substring and only we do it only on the ones that that we need
[52:08] because we're walking the tree or the try for each one. it's an optimization for when we have really large words. is going to be slower when you have a large N but a lower M than our other
[52:24] faster. But you can see how these problems are way almost like that the AI is I don't know somehow just like eager to lead you the wrong way and you
[52:38] leading it to allow it room to push back on you and to not just be so sick of fancy which it's always eager to do. Clear context. Make sure that your old work isn't necessarily always you know on the screen for it to be able
[52:52] to Wait, did I even uncomment out the last test? Okay, first things first immediately after finishing that one take I took a bit more time and confirmed I'm right about the suffix try thing. So there's a
[53:05] the clock, feeling the pressure, not wanting to let this video get too long ultimately letting the AI bully me. But in any case, hopefully you found that as dozens of others at hellointerview.com and most importantly
[53:19] good luck with your upcoming interviews. Take care.