Transcript: AI Coding Interview w/ Meta Staff Engineer

Watch video

Hello Interview53:22Transcript ✅Added May 21, 12:53 am GMT+8

Source video ID: A1kX8fJx53c

Transcript

0:00 — Hey everyone, welcome back to the channel. Today I’m going to walk through an AI coding interview question with you. And so it’ll be a question that I haven’t solved before so that you can see how I, as a former metastaf engineer, approached the problem. And I’ll do it in one take so you can see my thought process, mistakes, and all those messy inner thoughts. 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 what interviewers are looking for and how you can stand out in your next AI coding interview. I know there’s a ton of confusion about this new interview type. So hopefully
0:30 — 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 without further ado, let’s have some fun and let’s get into it. If you head over to hello.com on the lefth hand side, you can go to practice and then AI coding. This is going to show you all the AI coding practice problems that we have for you. Each one of them has an answer key. I strongly suggest that you don’t read an answer key before trying a problem. You’re just going to learn so much better that way. But there’s lots of problems to choose from. Uh most of these come from user reports. So users go take real
1:01 — interviews. They come back, they let us know about their questions. Um the questions that have a lot of user reports, we come here and we we translate into an actual problem. So what I’m going to do for you guys today is that I’m going to walk through one of these problems in full. Uh hope I think I’m going to do this in one take. You guys are going to see the messy mistakes I’m sure that I’m going to make. Um, as for the problem that I’m going to choose, I probably should have thought of this beforehand, but I’m going to do I’m going to go ahead and do word container. This is a problem I know less
1:32 — well than the others, so you guys will actually get to see my real-time thinking. I’m sure I’ll even make mistakes throughout. Um, but importantly, it doesn’t have a lot of starter code. I know that. And I think that’s good. You guys don’t want to see me just like reading a bunch of code. I think that’s going to be a little bit boring. I want to try to get to the implementation as quickly as possible. So, without further ado, let’s go ahead and do Word Container. I’m going to click start. Everybody can do one of these for free. Unfortunately, to do more than one, 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
2:02 — Python. Um, guided practice is actually what I 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 is basically just like an empty environment with no questions, no AI evaluation, no nothing. Um, basically just simulates kind of what a real interview would be. And I want to do that with you all today. I want to simulate a real interview. So, I’m going to click this one. Um, I’m going to play the role of both the interviewer, the
2:32 — candidate, and the teacher. So, you’ll see me talk through all three of those. Hopefully, that’s useful. You guys, of course, will let me know in the comments. But when the uh when the interview first starts, your 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 companies like Meta use for the AI coding interviews. They’re very, very similar. They’re structured this exact same way, which is that you have the 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
3:04 — output for when you run the code as well as the AI assistant here, which you’ll be able to use and you can drop down and change the models. Okay. Um, your interviewer will after orienting you of course explain the problem to you for a moment just like a traditional coding interview. And so in this case, let me take a moment to maybe explain this problem to you all as I try to remember myself what this this problem is. So what you do is you end up with a data folder here and it has a bunch of text files and if we look at the small one
3:34 — you can see this text files 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. And now your next question would be 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. Um because app is contained in apple. So apple is a
4:05 — container. Similarly, application would be returned because app is in application. So it’s a container. Banana would be returned. Ban is in banana. You get the picture. The simple example here is probably the easiest which is just apple banana and nana where the return value should be apple and banana because those are the two containers. Okay? Right? Right. So, we’re just trying to find the words in the list of words that contain another word in the list. Easy enough. Hopefully, you’d have some time to ask your interviewer if you had questions, of course. Um, but I’m not
4:36 — going to ask myself any in this case. Now, they’ll introduce you to this instructions panel which has a list of tasks and they’re all a little bit different, but by and large, these AI interviews get broken down into three phases. The first is code understanding. So you’ll take some time to just understand the codebase, right? Orient yourself, the key classes, key functions, etc. From there, there’s usually a bug somewhere. And so you’ll use the test cases to identify and then fix the bug. You’ll move on to implementing whatever the core uh thing
5:07 — that needs to be implemented is. And then usually you need to optimize it. The tests kind of show that it’s either too much space or it’s too slow or it doesn’t work under some additional conditions or something of this nature. So that’s the general flow of these interviews. You have about 50 minutes to do them. The interview’s an hour long, five minutes for pleasantries and questions on either side. So, you usually have about 50 working minutes. Um, I think before I get started, I want to just leave you guys with one tip. This is probably some of the most value that you’ll even get out of this session. And that’s that the number one mistake I see
5:37 — in having conducted so many of these sessions now from candidates is that they’re too hesitant to use the AI. This is an AI coding interview. And so to not use the AI doesn’t allow the interviewer to evaluate your ability to add value on top of the AI and to 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 on the AI, you’re not allowing them to evaluate your skills there. And you’re also setting yourself back. There’s a candidate who’s using it who’s moving at twice the pace. So we’ll show plenty of examples as we go through
6:07 — the session, but clearly asking questions like, “What is the answer?” or find and fix the bug are not good AI questions. Um, but being informed based on what you know about the codebase and then using the AI to both increase that understanding, to do some of the implementation, um, to help you brainstorm, to answer questions you have. That’s what you’re going to end up um, leveraging it most for. So, you’ll see me do exactly that. 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
6:37 — problem. Um, I know a little bit about it. Uh, maybe more than the average person, but I think I’ll still probably stumble my way through a couple of things. So, let’s watch me do it. The first thing that I’m going to do is I’m going to understand the codebase a little bit. And so, I’m going to start with the main function here. And so, for the main function, I’ll run it again just so I can see what it does. Begin code output. It gives me input words. Where do those come from? So, I have words get example words. That’s in words. So, what is that? Okay. Okay, so
7:07 — that just returns a simple list of example words. No big deal. That’s pretty straightforward. I create a word list with those words. What is word list? 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 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?
7:37 — if it doesn’t have a a space in it. Okay, I won’t get too deep into that yet, but this instantiates that. We instantiate a solver. I assume that’s what we’re going to have to solve. Yeah, so there’s nothing here. Solver takes in that word list class. Um, and then find containers. That’s where we want to return obviously our list of containers. So that’s not implemented, which is why we just get none here. So we call containers find containers. Containers were none. Cool. uh if there are things in the containers
8:07 — then for each container find the word that it contains interesting okay so we’ll be able to like use this to debug okay I feel like I have a decent understanding there I’m going to come back to these two key classes again they’re short word list valid word is no space get words get word set nothing to it contains as substrings so this takes the container and the contained and I assume it returns whether or not contained is in container that’s interesting thing less than or equal to.
8:38 — That might be our bug. We’ll find out later. Uh words it okay just loads looks like it loads the words from these files and returns the list. I’m going through this a little fast of I I’m assuming this is the least interesting thing for you guys to watch. So I’m flying through here. Of course in an interview you’ll have a bit more time to understand this practical advice. I feel like I I kind of understand these classes now. They’re they’re really short. Um, but here’s what I would do. I give candidates and I’ve seen candidates take two approaches, both of which are
9:08 — equally effective. The first is that you can come here and say for words.py and word list.py, add single bad typer sentence comments to each core function saying what they do. So, I might do that right out of the gate. Actually, I noticed these classes were small, so I didn’t have them doing it, but I might do that right out of the gate. And then while that’s working, I’m going to be reading through the classes. And as you can see, they’re coming in
9:38 — here. And so this is just going to make um you know, my reading and my my comprehending of the code a lot quicker because I can read the string, see what it’s supposed to do, make sense of it, go from there. Right. So it’s done with words. See if it goes on to word list now. Great. So initialize the word list with valid unique words from the input list. Yep, that’s what we discussed. Uh, did you freeze on me, buddy? Hello.
10:10 — Finish wordless uppie. Don’t know why it stopped on us. Okay. Checks the word is valid by ensuring it contains no spaces. Trying to copy. Cool. You get the picture, right? So, that’s a pretty effective thing to do there. Another thing I’ve seen candidates do which I think is equally as effective is right in the beginning you can say something like give me a concise bulleted list of the key functions per class and what they do. So maybe
10:41 — even before you read the code you just ask for that and it’s going to be able to give you something like this. So the word list class you know whatever we already know it so we’re not going to read through it. But all of 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, and it it can be used to speed up your understanding. So, by all means, please do. Now, once you’ve done that, and you probably don’t need to spend too much time reading the code because the best way to really understand the code is to work backwards from the test cases. And so, if we go back to our instructions, it tells us that uh we
11:13 — need to fix the bugs. And it says that 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. So I’m also going to use these test cases to really understand my understanding and I’m going to be communicating with the inter or test my understanding and I’m going to be communicating with the interviewer throughout. So test word count in this case we instantiate a word list with apple, banana and cherry. 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 would assume words will
11:44 — have all of those uh words now. So it should return three. And let’s test that. Cool. So all all four of these tests already pass. Great. So that return three. It should uh apple banana duplicates here. So it should return two. It does. Okay. Because it’s going to be filtered out by that set we were looking at. Now assert true contains as substring apple app. Okay. Let me just validate contains as substring again. Container. So bigger one first, shorter one second. Um bigger one first, shorter
12:16 — one second pass. Bigger one shorter one passed. Cool. cat dog is not contained in cat. So that’s false. Cool. Let me just kind of prove what I’ve been emphasizing here. And I might do this in the interview like adding additional test cases is cool. So if I do this in the inverse, this should be false, right? And so test wordless still passes. Cool. Um test contained at different positions. What does this do? Assert true contains a substring. He is in hello. Yes, it’s the start. I guess
12:46 — who cares where it is? We’re just testing that it works. low at the end, L in the middle, it’ll return true. And they did. Okay. So now we get here uh and we have some tests to uncomment. And you’ll you’ll see certainly in the meta interviews that they have question marks in the test cases. The whole point of the question marks is to test your code understanding like do you know what this code is even expected to return in the first place. And you can chat with your interviewer. Um but ideally you’re able to read the code and make sense with it and you know maybe leverage the AI if you need to. So in this case we
13:16 — instantiate an empty word list. I guess we’re not even going to use it. We’re just using it to call the the method here. Apple apple. Um well, first of all, we know that when 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 result of that, I’m assuming that this should be false. But I’d probably ask my interviewer at this point and be like, can a can a word contain itself? Right? Um now, if I was the interviewer, um which I am here in this case, I would say, no, a word cannot contain itself.
13:47 — And it seems like that makes sense from the setup that we have here. So I’m going to make this expected value be false. Okay. And then I’m going to run it. And I’m going to see that we got an error. Now I remember from reading the code that I thought this was pretty messed up. So let’s go look at it. Contains a substring container and contains. 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 than and not
14:17 — less than or equal to because that’s where we’re failing right now. We have Apple passes that and then of course it’s in it. Um, yeah. So I think that’s our that’s our bug fix there. I’m going to explain that of course to my interviewer that because we agreed that a word cannot contain itself then the contain word should always be strictly shorter than the container. And let me run again and I passed. So, seems like we we might have found and fixed the first bug, but let’s see if anything else comes up there. Um,
14:48 — def contains longer word. Oh, look at this. This is this is the example that we added up here. So, I guess we’re one step ahead. So, does app contains apple? No. This is why we have that less than check and we don’t just do the in, right? So, this should return false 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. Test valid
15:18 — word empty. Interesting. Okay. So the empty string is the empty string a word according to this test. No. Uh I don’t think I don’t remember if our code tested for that. I don’t think it did. Yeah. Okay. So we need to go look at is valid word. It looks like the expectation is that is valid word is false for an empty string. Uh and so if we go back to word list, we have is valid word which just checks spaces right now.
15:48 — So if there’s a space in the word or word equals equals empty string then return false. I don’t really like this return false. Return true anyway. We can make this a turnary or excuse me not a turnary. can just do return of the inverse of this. I’m not going to I’m not going to mess with it too much. Okay. Um, still passing. Cool. What else do we have here? Test valid valid word. No spaces.
16:18 — Yeah. So, this should be false because there’s a space in the word. Our words have to be non- empty string and they have to have a space. Right. We’ve learned this so far. Passes. What about this one? We instantiate a word list with apple. Normal word. Empty string. Nope. Banana. Good. Hello world. Oh, cherry. And so word count. Well, the word count should be three. And it is. Okay. Bing. Okay. Well, we fixed the two bugs. Um, the bugs were pretty straightforward. The bugs are often
16:48 — times pretty straightforward. Maybe in this case, they were a little a little on the easier side. Um, but especially if there’s more code to understand like and you’re nervous in an interview, you know, I may be I may be making this look easier than it is even I think with that exercise. But nonetheless, I wanted to fly through that a little bit. Um, that still ended up taking us about 15 minutes. Is that true? Yeah, I guess including the introduction before we clicked anything. So, um, let’s go back to our instructions. We fixed the bugs. Now, we need to implement solver. So,
17:19 — complete five, uh, find containers in the solve class. Okay, so we have the solve class. We have our test solver. Looks like we’ll have some test cases to work through here. So, let’s implement this first. Okay. Um, let’s talk about good and bad AI usage. A candidate could see this and they could come right over to the AI and they could say, “Implement solver.” That’s bad, right? Um, don’t do that. What is your C, what is your interviewer going to learn from you if you do that? They’re going to learn you know how to type implement solver. All right? So, that’s not the greatest. Instead, what
17:49 — we want to see you do as interviewers is 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. We’ll certainly engage the AI to write 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. So I would talk to my interviewer here for a second and I would say immediately out of the gate, I see a pretty obvious brute force solution. And that brute force solution
18:20 — would probably look something like this. I’m going to write it down both for myself, but so the interviewer can see it too. is that I’m just going to say for each word check every other word okay and that see if contains if yes add it to you know list to return whatever so it’s just a nested for loop that nested for loop is going to for every single word check every other word it’s going to call that helper function that we had
18:51 — what was it contains as substring 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 now. In the interview, you don’t necessarily have to go with the naive brute force solution. I think it’s useful to build your way up. It kind of gives you time to build your intuition, too. And that’s what I’m going to do here. So, I’m going to say I’m going to put it in edit mode. These things always
19:21 — have ask and edit mode, by the way. Edit allows it to make changes directly to the file. Asks means it won’t change the file, but it’ll give you code here. So, if you’re just brainstorming and you want it to give you code without writing it, put it in ask. If you want it to actually uh be able to edit, put it over here. So, I’m going to be kind of explicit here and I am going to say implement find containers using the helpers in wordless.py. just do brute force nested for loops.
19:56 — Okay. Um, so that should then go implement our simple solution as that’s going. Okay. It was pretty quick, but I’ll be talking to my my interviewer again about the solution, what I’m expecting to see as it comes out. Now, here’s the key. Any code that the AI gives you, you’re going to want to be able to make sense of. I’ve seen a lot of candidates like read line for line and like narrate line for line. And it’s like as an interviewer, I’m kind of rolling my eyes. I don’t care. I want to hear your two to three sentence summary of what’s happening. And I want to see that you checked it and you understand that it’s
20:26 — working the way you expected it to. 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 we end up returning. It’s all good so far. Words. Get the words from the word list. Straightforward 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 contain words in words, that’s our nested for loops. If contain word does not equal contained word, it’s fine, but I don’t need that, right?
20:56 — Um because remember in contains a substring, we do the length thing. So that was just kind of unnecessary. Um if self.word list contains a substring container, remember container first then contained and containers.append the container. This break here is great, right? So if we had I think we had an example here where banana has nan and ban and nana by the time we find out ban let’s just break there’s no reason to keep going. Um, so this looks good. This looks like it works to me time complexitywise, right? This is O of N. This is
21:29 — uh O of N. And then this itself, this contains as substring does in, right? Does N. So that’s another O of N, right? Uh, I think so. Um, so that’s another O of N. No, no, no. M, sorry. Where M is the length of the word. What am I saying? 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 n^ squ* m. So I’m talking that to my
21:59 — interviewer. But let me come here and say what is the time complexity if n is num words and m average length of word. Now this is really important. I’m going to reiterate this a couple times here. My last one I was pretty explicit because I wanted the brute force one. But by and large I’m explaining to my interview what I think it is. But then I’m asking the AI with not being overly specific. I’m not saying is it n^ squ* m, right? I’m letting it do it um so that I haven’t biased it so it’s not going to be sick
22:30 — ofantic and so I can see if it actually agrees with me. And in this case m for each contains so it looks like we nailed it. n^2* m. Okay cool. Let’s this looks good to me. Um let’s see if it works. And so this first test that we have instantiates a word list with cat and dog. We instantiate solver solver. Actually the very first thing I want to do is let me go run that main because that looked pretty useful, right? So main apple banana application details apple contains app and it contains
23:01 — application. Cool. Okay, I got a little tripped up here because it returned application twice. Um but fortunately uh the container word still just has it once. So that 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 the result is a list that we would expect. Um 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
23:33 — expected. So this was our canonical example. We expect apple and banana. Then does the order matter? No, they’re sorted. Okay. Apple, banana. That looks good. Let’s see. Cool. Um Oh, I’m running the wrong test. I’m like, why is it returning so many tests here? Test solver. Okay, both of those pass. Silly. Okay. Um test no
24:03 — containers. So, we have cat, dog, and bird and fish. Find containers. None of those contain each other. So, empty list. Let’s see. Cool. Um, next one. And I’m doing tests one by one like this, right? I I see candidates uncomment all tests and then run them and then they’re just like they’re so overwhelmed by everything that they have to do and they end up commenting them all out and leaving just the one that failed anyway. So, save yourself the headache. Go one by one here, right? Multiple words contained.
24:34 — So we have work, worker, yes. Rework, yes. Working, yes. Homework, yes. So these three are what I’m going to return. Expected count. I assert equals. We want count this time. Okay, cool. Uh maybe this is minor, honestly. But like if I was in an interview, I would be like, you know, it’s so I wouldn’t blame a candidate. If they put the list here, they’d run it and they’d figure it out. But like cool, I caught myself. I I I was moving quick. I read it. I saw it actually once count. Um so kind of just
25:04 — shows my code reading comprehension maybe. Um so that one worked. Test nested containers and yes ant rant grant. So same thing all four of them have a obviously ant also has and so on. Count again. Um so let me do four there. Okay cool. So far brute force is crushing it and test from small file. So we get them from that small file. Find containers. Assert that it’s a
25:34 — list. Expected minimum. So I could just make that one and it’ll pass. Seems kind of stupid. Okay. Um 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 small. So how many should this have? Apple. Yes. So, one, two, three, four, five, six, 7,
26:06 — 8, 9, 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. Um, so I’m going to do assert equals length of result is expected. Oh, what did I mess up? Oh, my little face goes in the way. Oh, okay. Cool. Um, cool. So, that was interesting there. Um, in the interview, like there’s
26:36 — probably no expectation on you to change tests, but I think it would look really good. If a candidate did that to me, I’d be like, “Okay, great.” Like writing this down and a positive on their verification. Um, they were unsatisfied with the the written test, whether 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, I think that that was a good move. Um, test medium word list. What does this do? This test looks different. Get the words. Find the containers. Elapse time. So, we started a timer. So,
27:06 — we’re timing how long find containers takes. Um, assert is instance. Sure. Expected time 1 second. 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. This should 500 words should happen in under a second. Our brute force probably fails. No, our brute force is still stupid fast. Okay, it’s getting farther than I thought it would. Uh, what about this one? Large words. Now we got 5,000 words. So, order magnitude higher. Um,
27:36 — and it should be half a second. Failed. Okay. So, that’s where the brute force breaks us, right? So, we’re close. 0.55 seconds. Um, but we were slow and so we need to optimize. It requires optimization to pass in time. Yeah. Okay. uh basically it’s telling us that. So let’s think here now. Again, I could go right to the AI and I could say like I need an optimization. Give me 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
28:06 — but I’m not saying you’re going to fail you for doing that if you understand all the code that comes out of it. But let’s just take some time to actually think through this. And so I have this O of N squ. 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 clear first optimization. It kind of
28:37 — sucks that that’s O of M to be honest. Like I that should be I can make that O of one I imagine. Um, also the O squ. So what could I do? If I use this set here to make this O of one, I could have a set with all of the words. I could have a set with all of the words and then I could try each substring of a given word against that set, right? Okay. Yeah. So if I had, so let’s just
29:09 — say I had rework a 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, whoa, whatever. You get the point. Um, all the way until we get up to we were, and E work, and finally rework. So, I can try all those substrings. And now if there was like work also in the list then in the
29:40 — middle here you know dot dot dot comma work I would have work as a substring and if I check this substring into the set I would get an O of one. Okay. And so creating all of these substrings, this is O of N squared, right? But then I get O of one on the lookup. Okay. So I think that’s I think that
30:11 — sounds decent. I think that’s what I’m going to do. Um, yeah. So, now what I’m going to do actually is that instead of just going ahead and telling the AI to do that like I did before, and this is a common mistake and pro tip here, big pro tip. If you tell the AI to do something, it’s going to do it and it’s going to sophantically say like, “Yeah, you were right. You were so smart. That was so great.” So, don’t do that. Um, what I’m actually going to do here is I’m going to be cautious. I’m going to keep this in my paste in case I need to come back to it, but I’m going to delete that so the AI can’t even see that old version.
30:42 — Um, I’m also going to clear messages, I think. Yeah, I’m going to start a new chat here so I’m not biased with the previous junk. And what I’m going to say is, um, give me a concise list of options to optimize find containers um, beyond the brute force solution. So had you just written this and never talked to the interviewer beforehand,
31:12 — it’s again like it’s okay. It’s not bad but it’s okay. But what I did here is I had maintaining two conversations. I’m talking to the interviewer about what I think is going to be a good approach that said approach. But instead of coming to the eye and saying like is the set approach good, I’m telling it to give me all the possible approaches cuz maybe there’s something better that I didn’t think about and even if mine is the best like I want it to validate 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 um based on the current brute force solution still knows that
31:49 — okay let’s read this so a try I didn’t think of that but a try to efficiently find all words that are substrings of a given word suffix array process words in suffix structure with fast substring queries hashbased grouping group words by length Sounds like a heristic algorithm options early termination birectional rolling hash the string match. Okay.
32:23 — All right. This this try approach sounds pretty interesting. I have a feeling that’s going to end up being our most optimal. Um, should I jump right to it? Okay, maybe in an interview I I might just kind of take the suggestion here and go in that direction. But I I think that this set thing is also viable and I kind of want to try it first. So what about if we had a set with all the words and then iterated
32:54 — over all sub substrings checking against the set. So many spelling mistakes but good thing AI smart. Uh that’s actually a very clever solution. Okay. Never trust it when it tells you that. Instead of checking every word against ON squared, you do create a set for each word. Generate all its substrings. Check each substring against the set. If found mark the original word as a container time complexity current root force is O of n^2 * m yes
33:26 — this approach would be n * m 2 * 1 significantly faster. Okay. Um gosh bad spelling. implement that approach, please. I’m going to put it back in edit mode. So again, I’ve been clear with my interviewer. They understand that I understand what I’m talking about here. I’m going to create a substring for each
33:57 — word. I’m going to check all of those substrings against the set. The creation of that substring is M squ. And then uh the set is O of one. We do it for every word. So N * M^2. Okay, let’s let’s look at the code here. We got the words. Word set. I mean, this is fine. This is minor. Didn’t we see here that it had something for that? Get word set. I don’t know. Honestly, kind of kind of silly, but word set. Yeah, kind of
34:28 — silly, but I want my interviewer to know that I’m paying attention. Um, so self do word list.getword set. Wasn’t there get words too? What is it doing here? Come on, dude. Okay, so these are minor things, but like these are showing well in the interview. You want to be careful changing too much of the AI code. I see a lot of candidates who like get over eager and are changing a lot of things and then make it break. Frankly, I might have just done that. We might hit run and it might break. Um, but it’s nice to
34:59 — show that you understand these things. Now, for word in words. Okay, so that’s R O. It’s R O. Generate I for range and length of word. Okay, for J in range I + one, length of word, this needs to be plus one, right? Sub, okay, the plus one’s here. Okay, substring equals uh so we get the substring check if the substring is in
35:29 — the word set. If it is, append the word, right? And then early break. Good. Um else continue. Okay, let me let me start by running it. So this makes sense. This is this is our O of M squared. Uh we get the substring. We check in the set. That’s our O of one. We break if we already found one. What’s this else? Continue for break the outer loop, too. Okay. Return
35:59 — containers. Yeah, we’re still in the containers. All right, let’s run and see what happens. Got it wrong. It got it wrong. Oh boy. Oh boy. Yeah, I still think this is the issue. The hell is this? You want to go till the end of the words, right? No. What happened here? Oh, so word sub. I’m going to have to
36:30 — actually analyze this. This is annoying. for I in range length of words statements to debug this. I want to look at the substring and the word set. Run it again. Oh boy, that’s annoying. So I’m going to run main.
37:01 — Wait, sorry. I want the substring in the word. So, let me do container and then contained consistent with what we’ve been doing. Ah. Ah, you see that we’re overounting 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:31 — Yeah. Okay. Okay. Okay. Okay. Phew. Okay. And it all passes. And it’s damn quick. 06. Okay. Wait. So, what about this one? Was it the same? It’s the same thing. No. Yeah. Okay. So, I was right about that, too. Okay. Wow. The AI really screwed us there. That was dangerous. Okay. That was dangerous. Um, 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. Um,
38:03 — 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, but wow, that was interesting. 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 was able to see what ended up going wrong and as a result was able to kind of appropriately debug it. So
38:33 — yeah, we got uh we got lucky there, I guess. Um okay, now here’s what I’m going to do. I’m going to remove what did we say this was? We said this was O of M squared times N, right? And that’s because this is the O of N. This is the M squ. What about this word I J? Certainly in Python, we’re splicing a word, which means we’re allocating new
39:03 — memory for it and moving it over there up to length M. Average M and a a half M. This is M cubed. This is M cubed because that’s M. M N. It’s just wicked fast because so long as the word is small. This is M cube. It’s only wicked fast because so long as the list is longer than the words are long, this is a good solution. Otherwise, it’s a bad solution. Hold up. Let me confirm
39:33 — that. So again, 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 find containers where n is uh known words and m average length of words. I’m right there. Right? You guys are probably looking at this watching this knowing something I don’t. But yeah, look at that. N * m cub. So I’m right. I thought it was going to be m^2.
40:03 — I didn’t think about this. So we have n mmm. So it’s m cube. So lesson here. Long words are going to not work. Um and I bet that’s where we go next in the test if anything. Let’s see. Oh, test solver. Okay. So to pick back up, we’re passing. We’re flying. So sick. Huge word list. What does this one look like? Okay. So this is a big N.
40:34 — small ends. So, it should fly. Yeah, it’s fast. A little a little slower here. Um, okay. Now, this last one. Yep. This is where it’s going to get us. It even says requires optimization. Stupid. Um, just making sure. Same code. Yeah. Now, we’re testing long. Yeah. Look at this. These aren’t even words. So, we’re going to be screwed. These are
41:04 — super long words. And so, the reason that we’re going to be screwed is because we’re doing M cubed on every single one of these. We’re trying every single one of its substrings. And to do that, um, you know, we’re finding a, I, and J. We’re moving for each I, we’re moving 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. Yeah, we got crushed. Took 5 seconds. It needed to be one. So, we need to get even smarter here. Okay. Well, I mean,
41:38 — earlier it told us that a try solution was probably going to be good, right? So, I’ve kind of been tipped off to that, which is why me asking that question about like what are some good optimizations was a great thing to ask. And we know we could have jumped right to the try potentially. I’m glad we took this solution. It got us pretty far. And I think the interviewer would appreciate this evolution. Um, but I know a try solution is probably going to be what’s next. So, let me just think about what this would be. Uh maybe just quickly for anybody who’s watching this who doesn’t know what a try is, a try is a tree for which each
42:08 — node is a letter. The edge is 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 try that word rework. Then we would add r e w 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 here, A R D. And so if you wanted to check if
42:38 — reward was in this try, you would just walk it reward and you would get there and you would find out that it’s in the tree or in the try. Um, so that’s what a try is. Um, how do we construct this try? So it’s that M cube that is killing us. How do we make that not be m cubed?
43:10 — So the issue I remember we don’t have this anymore unfortunately but remember we were writing out all of the different substrings of rework and it was just so long. There were so many substrings n^2 or m^2. We don’t need most of those. How do we what do we need? I guess in tri world just a suffix just a suffix is sufficient. Like let’s say
43:40 — let’s say I needed the word re. Let’s say rew was a word. Obviously it’s not. But I would walk rew. And then I got to W. So I know, wait a minute, this is contained in something. And then I just need to walk to the end of the word to find out what the actual word is, right? Let’s try that out. Rew would walk all the way through this. And so then my tests that I need to be testing are just
44:10 — the suffixes. They’re just the suffixes. Yeah. So, it’s the other way around. So, these are going to be I’m going to I’m going to create a try with all of the different words. So create a try with every single word and then for every word check all of its suffixes because if any suffix gets to the end without you know having a mismatch then
44:40 — that word is the container. Yeah. Then that word is the container. Concrete example. Okay. Um, concrete example would be that if we had, let’s say that we had I’m just going to make this easy on myself and do spaces. Let’s say we had banana and then we also had nana. Those are two words.
45:11 — And now we’re going to work through each of these checking just their selves. So we built the tree. That’s the tree. And then now for banana. I’m going to try uh I’m going to try banana and it’s going to match but it’s the same word so it doesn’t matter. Then I’m going to try the next thing which is just anana. Banana just banana. There’s no a a root node so nothing. Then I’m going to try nana match. So I know that banana the word I was trying all of its suffixes. And the key
45:41 — here is that to try just the suffixes is O M. It’s not OM squared because we’re just trying BNA Nana Anna Na as opposed to all of them. All right, you guys are watching me walk through this. Let me let me take a break. In a real interview, you probably don’t have to go into this much detail. Like you could jump over to the AI and start asking you questions to understand it. I’m I maybe I was I was having a 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 try solution. Again, I’ve communicated to my interviewer what I think it is. Construct a try with all the words. For each word, try all of its suffixes. If there’s a match, add that word for which you were trying it suffixes to the containers. But I’m not going to say that explicitly to the AI. I think there’s a try solution. Explain it to me. Um let’s just see if if it agrees, right? But I don’t want to like force it to do the same thing as me. So I’ll explain how find containers. Try solution. A try prefix tree. Prefix.
46:47 — Have I been saying suffix when aren’t they suffixes? Uh can reduce the o of n * m squ? Yep. By eliminating the tree creation older head. Build a tree for each word. Traverse all possible substrings of the tree. No, no, no, no. We don’t need to traverse all substrings, just the suffixes, right? Like for rework. God, I shouldn’t have said it right.
47:19 — Um, validate, be skeptical. Is this true? We don’t need to traverse all substrings, just the suffixes. So for rework we only test e work work. Okay, you’re absolutely right. I’m skeptical. I made an error in my analysis. Okay. So either it’s being sick of fantic and
47:50 — we’ll find out or the was stupid again. Um, this generates all possible substrings, not suffixes for rework time complexity. What? No, I don’t need all of that.
48:22 — Not sorry out loud. I’m saying I think we only need to check suffixes. Suffixes. So for each word it’s m and not m squared. Um how can I make it not just agree with me? Can you disprove this or is it right? It’s probably not the best to be honest, but you’re absolutely right to question this. Looking at the problem, we want to find all pairs
49:03 — Whoa, whoa, whoa. The problem. We missed finding the rework contains Ryu. You’re right. That’s right. Oh boy. Uh, that’s right. Ru is a prefix of rework, not suffix, but only check suffixes of rework. We only check counter example. Hello. Hello.
49:38 — Wait, real should check on rework. So if I have if I have ru if I have ru rework and I have ru they’re both in my tree then when I’m testing rework oh yeah that would be then backwards conclusion we need to check all substrings.
50:08 — So all we’re doing is avoiding that substring creation thing. Yeah. Okay. All right. So, what it’s what it’s saying is that the construction of the tree is going to allow us to not have that uh this part, which is going to get rid of 1 m, which is going to make it m squared, which is what we wanted to land on. Anyway, I guess I was wrong about the suffix thing. And I see why here. It has to be all. I still feel like there’s a
50:38 — way to get that to work. Let’s see. I’m gonna have it implemented go. So find containers gets the words containers build the try. So create a try node. Try node just has children and
51:08 — then the terminal is word for car and words for car not in node. Okay, so we’re just building the tree. No big or the try. No big deal. For word and words found container equals false. For i and range length of word if found word break otherwise for j and length of i length of word which are not in node. No more valid words. Found a valid substring. if node is word. Okay, so we’re still doing this, but we’re only doing it if we found the valid substring
51:39 — found container equals true. Okay, passes with flying colors.136. Um, I did a lot of explanations there. This ended up being longer than I wanted it to. I’m so sorry. Um, you can see what the final solution is here. It’s a try where for the try, we put every single word into the try and then we check all possible substrings. This avoids us from doing the splicing um for every single substring and only we do it only on the ones that that we need to um
52:09 — because we’re walking the tree or the try for each one. So, it’s a little bit faster and thus it’s an optimization for when we have really large words. Um it’s almost certainly the case that this is going to be slower when you have a large n but a lower m than our other one. The set lookup would have been faster. But you can see how these problems are con um constructed. They’re constructed in such a way almost like that the AI is I don’t know somehow just like eager to lead you the wrong way. And you want to be really careful as you’re leading it
52:40 — to allow it room to push back on you and to not just be so sick of fantic which it’s always eager to do. Clear context. Make sure that your old work isn’t necessarily always um you know on the screen for it to be able to Wait, did I even uncomment the last test? Yeah. Okay, so everything’s passing. 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. Um, so there’s a pretty good example there of me saying the clock, feeling the pressure, not wanting to let this video get too long, just like a real
53:10 — interview, and ultimately letting the AI bully me. But in any case, hopefully you found that useful. You can try that problem as well as dozens of others at hello.com. And most importantly, good luck with your upcoming interviews. Take care.