---
title: 'AI Coding Interview with a Meta Staff Engineer'
source: 'https://youtube.com/watch?v=A1kX8fJx53c'
video_id: 'A1kX8fJx53c'
date: 2026-08-04
duration_sec: 3202
---

# AI Coding Interview with a Meta Staff Engineer

> Source: [AI Coding Interview with a Meta Staff Engineer](https://youtube.com/watch?v=A1kX8fJx53c)

## Summary

In this video, a former Meta staff engineer and co-founder of Hello Interview walks through an AI-assisted coding interview question in real time. He demonstrates how to approach the problem, use AI effectively, and avoid common pitfalls, while providing practical tips for candidates.

### Key Points

- **Introduction to AI Coding Interview** [00:01] — The video is a one-take walkthrough of an AI coding interview question, showing the thought process, mistakes, and how to stand out.
- **Hello Interview Platform** [00:42] — The platform offers AI coding problems with answer keys, and users can practice for free, with premium features for more.
- **Choosing the Problem** [01:50] — The problem chosen is 'word container', which the presenter is less familiar with, to show real-time thinking.
- **Sandbox Mode** [02:15] — Sandbox mode simulates a real interview with no AI assistance, and the presenter will play all roles.
- **Problem Explanation** [03:20] — The problem: given a list of words, return the subset of words that are containers (contain another word from the list).
- **Three Phases of AI Interviews** [04:40] — AI interviews typically have three phases: understanding the codebase, fixing bugs, and implementing/optimizing the core solution.
- **Key Tip: Use AI** [05:34] — The number one mistake is being too hesitant to use AI. These questions are intentionally difficult, and using AI is part of the evaluation.
- **Understanding the Codebase** [06:44] — The presenter starts by reading the main function and key classes to understand the structure.
- **Two Approaches to Understand Code** [09:04] — Add comments to functions or ask AI for a bulleted list of key functions. Both are effective.
- **Working Backwards from Tests** [11:09] — Running test cases helps understand the code and identify bugs.
- **First Bug Fix** [14:05] — The bug in 'contains_as_substring' was that it allowed equal lengths, so it was changed to strictly shorter.
- **Second Bug Fix** [15:32] — The 'is_valid_word' function needed to reject empty strings, not just words with spaces.
- **Implementing Solver** [17:20] — The presenter discusses good and bad AI usage, emphasizing explaining your approach before asking AI to implement.
- **Brute Force Solution** [18:25] — The brute force approach: for each word, check every other word using 'contains_as_substring'.
- **Using AI to Implement** [19:20] — The presenter asks AI to implement the brute force solution, then reviews the code carefully.
- **Time Complexity Analysis** [21:47] — The brute force solution is O(N^2 * M) where N is number of words and M is average word length.
- **Testing Brute Force** [22:46] — The solution passes all tests, including the large word list, but is slow on the large test.
- **Optimization Discussion** [27:55] — The presenter thinks about optimizing the 'contains_as_substring' to O(1) using a set of substrings.
- **Asking AI for Options** [30:19] — Instead of telling AI the solution, the presenter asks for a list of optimization options to avoid bias.
- **Set Approach Implementation** [33:05] — The set approach: for each word, generate all substrings and check against a set of all words.
- **Debugging AI Code** [36:13] — The AI code had a bug: it didn't exclude the word itself. The presenter debugged by adding print statements.
- **Complexity of Set Approach** [38:51] — The set approach is O(N * M^3) due to substring splicing, which is bad for long words.
- **Trie Solution** [41:30] — The presenter considers a trie to avoid substring splicing and reduce complexity to O(N * M^2).
- **What is a Trie?** [42:07] — A trie is a tree where each node is a letter, and edges connect subsequent letters in words.
- **Trie Approach** [44:21] — Build a trie with all words, then for each word check all suffixes (or substrings) against the trie.
- **Asking AI About Trie** [46:42] — The presenter asks AI to explain a trie solution, but AI initially suggests checking all substrings, not just suffixes.
- **Realization: Need All Substrings** [49:05] — The presenter realizes that checking only suffixes misses cases like 'rew' in 'rework', so all substrings are needed.
- **Final Trie Implementation** [50:43] — The final solution uses a trie to check all substrings, avoiding splicing and achieving O(N * M^2).
- **Final Testing** [51:43] — The trie solution passes all tests, including the large word list, with a time of 0.136 seconds.
- **Lessons Learned** [52:38] — AI can lead you astray; it's important to have a clear understanding and let AI push back. Also, clear context and don't let AI bully you.

### Conclusion

The video demonstrates a complete AI coding interview, emphasizing the importance of using AI as a tool while maintaining control and understanding. The key takeaway is to communicate your thought process, verify AI-generated code, and be prepared to debug and optimize.

## Transcript

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
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
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
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.
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,
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
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.
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
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.
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 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.
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
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
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
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.
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
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.
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 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.
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
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
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
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
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,
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
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
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
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
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
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
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
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
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
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?
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.
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.
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
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.
Uh that might be our bug. We'll have that later. Uh words it Okay, just loads. files. And it returns the list.
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
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
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
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
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,
that's what we discussed. Uh Did you freeze on me, buddy? Hello.
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
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
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
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.
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.
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.
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.
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
looking at. Now, assert true contains as substring apple app. Okay, let me just validate contains as substring. Again, container, shorter one second. Um
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.
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
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
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,
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
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
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
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.
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
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
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.
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
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.
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.
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
spaces right now. So, if there's a space in the word or word equals equals empty string, then return false.
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.
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.
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.
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
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
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
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
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
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.
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.
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.
Is that I'm just going to say, "For each word, every other word, okay, and then see if contains
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.
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
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
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
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
Just do brute force nested for loops. Okay. Um so, that should then go implement our simple solution.
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
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
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.
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
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,
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
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.
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.
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
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.
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.
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.
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
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
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
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.
So, this was our canonical example. We expect apple and banana. And they're sorted. Okay. see. Cool.
Cool. Um like, why is it returning so many tests here? Test solver. Okay, both of those passed. Silly. Okay. Um test no containers.
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
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.
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.
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,
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
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.
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.
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
small. So how many should this have? Apple, yes, so one, two, three, three, four, five, six, seven,
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.
Um so I'm going to do assert equals the length of result is expected. cool. Um
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
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
words, find the containers. So, we're timing how long find containers takes. Um assert is instance here. So, I put the
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.
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.
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,
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
if you understand all the code that comes out of it. But let's just take some time to actually think through this and
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
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
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
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
w o Whatever, you get the point. Um all the way until we get up to rewer and ework and finally rework.
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.
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.
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
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."
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
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,
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
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.
Based on the current brute force solution, solution, still knows that.
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
length. Sounds like a heuristic. Algorithm options, early termination, Algorithm options, early termination, bidirection, hash. The string match uh okay.
pretty interesting. I have a feeling that's going to end up being our most optimal. Um should I jump right to it? Uh
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
and then iterated over all sub substrings checking against the set. So many spelling mistakes, but good thing AI is smart.
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.
times M. Yes. This approach would be N times M squared. times one Significantly faster.
Okay. Um Gosh, bad spelling. Implement that approach, please.
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
uh the set is O of one. We do it for every word, so N times M squared. We got the words. word set
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
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?
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
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
word. This needs to be plus one, right? Substring equals Uh so, we get the substring.
word set. If it is, appended the word, right? And Um else continue.
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
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.
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?
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
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.
So let me do container and then contained consistent with what we've been doing.
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?
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
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.
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
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, yeah, we got a we got lucky there, I guess.
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?
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
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.
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.
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 number of words and M average length of words. You guys are probably looking at this watching this knowing something I don't,
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.
lesson here, long words are going to not work. Um tests if anything. Let's see.
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
slower here. Um, It even says requires optimization, stupid. just making sure same code.
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.
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.
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
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
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
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
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
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
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.
How do we make that not be M cubed? remember we were writing out all of the different substrings of rework and it
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?
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
and then I just need to walk to the end of the word to find out what the actual word is. Right?
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.
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.
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.
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
nana. Those are two words. of these checking just their suffix. So we built And then now for banana, I'm going to try
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.
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.
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
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
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
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.
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
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.
Just the suffixes. Right? Like for rework God, I shouldn't have said it right. Um Hm. Be skeptical. Is it cool?
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.
Okay, so either it's being sycophantic and we'll find out or Um it generates all possible substrings, not suffixes for rework.
Time complexity. What? No, I don't need all of that.
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
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.
We missed finding the rework contains rew.
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.
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.
backwards. Conclusion, we need to check all substrings.
substring creation thing. Yeah. Yeah. Huh, huh, huh. tree is going to allow us to not have that uh this part.
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.
implement it. Mhm, mhm, mhm.
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.
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,
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.
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
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
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
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
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
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
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
good luck with your upcoming interviews. Take care.