We helped write the sequel to "Cracking the Coding Interview". Read 9 chapters for free

Go Interview with a FAANG engineer

Watch someone solve the generate valid strings problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Generate Valid Strings

Interview question

Write a program to generate all "valid strings" up to a certain length. A valid string is a string that starts with an "allowed starting character", and in which every character is followed by an "allowed" character. You are given a list of starting allowed characters and a dictionary mapping each character to a list of allowed characters that can follow it in valid strings. You are also given an integer n > 0 and you should generate all valid strings up to and including length n.

Interview Feedback

Feedback about Cunning Bathrobe (the interviewee)

Advance this person to the next round?

Yes

How were their technical skills?

4/4

How was their problem solving ability?

4/4

What about their communication ability?

3/4

Overall solid performance! You understood the problem very quickly and immediately mentioned BFS which showed you are very sharp and comfortable with basics of computer science and algorithms. The initial solution was the non-trivial BFS solution and was correct and working right on first attempt. Most of the feedback provided was aimed at polishing your performance to make sure you provide as much high-quality senior+ level signal as you can to any interviewer. I'll summarize the suggestions below: - Practicing being somewhat more expressive while coding. Explaining your thought process and the code you're writing as you go will be helpful (as mentioned, some interviewers tend to dislike long periods of silence and the candidate coding in silence for various reasons). - Using comments and/or more expressive variable names to help with readability and maintainability of the code (goes with better expressiveness mentioned in previous suggestion) - Making sure efficient data structures are used and that you are aware of the underlying implications of your choices (for example using an array for a queue in BFS is going to be either memory or runtime inefficient, or both). - The discussion of runtime and space complexity was solid. I do recommend practicing that type of analysis more and becoming more comfortable with doing basic mathematical analysis and derivation of big-O notation conclusions. As mentioned, overall solid performance. As is, this was a pass in my book for a senior engineer role and with some polishing it could easily be a strong hire decision. Best of luck with everything! PS: The word I was looking for was "symmetric"! If a = b implies b = a then the relation is symmetric. Equality is always symmetric but the big-O notation "abuses" the equality sign and is not in fact symmetric, meaning O(f(n)) = O(g(n)) does NOT imply O(g(n)) = O(f(n)). You can read more about this here: https://en.wikipedia.org/wiki/Big_O_notation#Equals_sign (In the interview I mentioned "reflexive", which is a different property of relations, and in equality it's that a = a, which big-O notation also obviously has!).

Feedback about Stateless Samurai (the interviewer)

Would you want to work with this person?

Yes

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

Interview Transcript

Stateless Samurai: I saw that you're fairly experienced. In the profile it said, I think 12 years of experience. Is that right?

Cunning Bathrobe: Yes, like around 13 years of experience.

Stateless Samurai: 13 years of experience. Okay, sounds good. Let me start a document here. So I'm going to write notes as we go so I can give you good feedback at the end. And so if you hear me typing, that's what's going on. I'm not being distracted. Cool. Okay, so 12, 13, almost 13 years of experience. And is that all as a software engineer?

Cunning Bathrobe: Yes. Like primarily software engineers. Yeah.

Stateless Samurai: Perfect. Okay. And could you give me a little bit of understanding? Are there specific things you'd like to focus on?

Cunning Bathrobe: Yeah, so I am currently, like, looking more of, like at my level. I'm going to get more design interviews. So that's where I am, like more practicing for coding interviews. I think maybe medium category of problem will come to me. So looking from that perspective.

Stateless Samurai: Got it. And are there specific companies you're looking to focus on?

Cunning Bathrobe: So I'm trying to get L7 role. So L7 role in some companies like Copang or Airbnb. So all those basically are targets.

Stateless Samurai: Sorry, what was the first company you.

Cunning Bathrobe: Said Previously I was in Microsoft and now I am in Uber.

Stateless Samurai: Oh, nice. Very cool. Okay, sounds good. So a little bit of background. I have about 10 years of experience. Most of it was at Google and Meta, and I've interviewed probably at this point, easily several hundred people, I think, for those two companies combined. I have interviewed with quite a few big tech companies that have gotten offers from them too, including Airbnb. So I have a little bit of experience with them as well. I got offer, an offer, but I didn't end up taking it. Cool. Perfect. Any questions before we get started?

Cunning Bathrobe: I think I'm good for now. Yeah.

Stateless Samurai: Okay, great. And what language are you using to code?

Cunning Bathrobe: Bolang.

Stateless Samurai: Perfect. Okay, so let's switch to that. Cool. Okay, so I'm going to. Actually, let's. Let's just delete all of that. There we go. And so what I'll do is paste the question. By the way, we'll spend the next 45 minutes roughly on the interview. Actually closer to 40 minutes to keep it realistic to most actual coding interviews. But we'll spend 40 minutes on coding and then we'll have about 15 minutes at the end to discuss. So if you have any questions, I'm starting now. We'll just basically assume that or pretend that this is a real interview. And so starting now, real interview. So here's the question. I just pasted it in. I can let you read it and then we can look at the two examples and then we can go from there.

Cunning Bathrobe: Sure. So I'm just reading it loud. Write a program to generate all valid strings up to a certain length. A valid string is a string that starts with an allowed static character and in which every character is followed by an allowed character. So so far there are a bunch of allowed character and we have to create strings basically based on those. So you are given a list of str starting allowed characters and a dictionary mapping each character to a list of allowed character that can follow it in a valid string. Got it. And you are also given an integer and greater than zero, you should generate all the listing up to the including length. Got it. So it's basically stating that there are a bunch of starting characters and then for each character a bunch of like mapped or possible next character. And then we have to generate starting from starting character. So for example, I start with A and then there are two possibilities there, A, B and ac. And then let's say we go above. Then there's another possibility of ABA like this. So it's kind of like BFS style problem. So we have like this bunch of start nodes ABC and then this assuming like the map represents the edges between like like from those character to another character. So it's basically kind of like a BFS version of like iterating through and generating the strings. So that's like my initial thought. I just want to check couple of things whether I need to do unique strings or something. Yeah. So unique strings. I guess the question doesn't specifically says that, but there are different starting characters, so it should be unique that way. I think I'll just recapture. I'll do basically BFS implementation and put start node and then just navigate to the map. Basically. Yeah. Okay. Got it. Okay, I can start writing. Just zooming. It's completing. So what's the output is list of. So I'm assuming output is list of string.

Stateless Samurai: It.

Cunning Bathrobe: Yeah. So just assuming and this will give back. Okay, so BFS Q it. It's it. So every time I just put my. Just get something from Q and then.

Stateless Samurai: Could you. Sorry. For the output. Could you just print them instead of putting them in a list?

Cunning Bathrobe: Sure. So you. So that's basically anything coming out of Q. Basically we just print it. That's base case and then we check the last character. And we check if this control. So if you already met the size of the string. So we just like don't process it otherwise. So we got the last map and then we just append. Yeah, so we just appended the new string and just continue. So one other thing with BFS is we keep track of what is visited, what is like not visited. So in this case, I'm trying to make sense of whether that's needed or not needed. So we start with this. Yeah, in this case it's not needed because we can come back to the previous character. For example, Aba. Yeah. So at line number 31 it says Aba. Will this mean like we cannot do aba B, Something like that?

Stateless Samurai: No, you could. I just. So Lane, you see line 34 to 36 I just put. So I didn't actually use all the inputs, but yeah, no, you could have. As you can see, I have line 37. I have caca as the last one.

Cunning Bathrobe: Got it. Okay. Yeah, so that was my impression as well. So that's why this is not keeping like the track of basically is visited because it can go back.

Stateless Samurai: Okay.

Cunning Bathrobe: Okay. Yeah, I think that's the. For some reason it's complaining about this. I think it's expecting main.

Stateless Samurai: I think it's expecting a package.

Cunning Bathrobe: Okay. So just to test the same case.

Stateless Samurai: It'S.

Cunning Bathrobe: B and C. And then. Yeah, there are a bunch of. Just compile things. I am collecting. Okay, so it's complaining about. I cannot concatenate. I think I can do like this. Yeah, think now seems to be fine. Let me run this. It's. I think I have to print line. I just clear it once. So abc, abac, ba cac. Yeah, seems like it's picking up here.

Stateless Samurai: Okay.

Cunning Bathrobe: Yeah, so that's. I can run a couple of more test cases.

Stateless Samurai: Yeah, try any post four and see.

Cunning Bathrobe: Sure. Yeah.

Stateless Samurai: Okay. Yeah.

Cunning Bathrobe: Cool.

Stateless Samurai: All right. Are you thinking of.

Cunning Bathrobe: Yeah, I'm running the example too.

Stateless Samurai: Okay, sure. Yeah, sounds good. Cool. Okay, great. All right, so let's look at the code here. Maybe a good first question is. So this is a working first solution, but looking at it, does anything stand out as an immediate hopefully somewhat easy optimization? What do you think is inefficient in this code?

Cunning Bathrobe: Yeah, I think I am keeping full string basically. So I am keeping basically full strings in my queue. So thinking about whether there's something I can do about it.

Stateless Samurai: Okay, so why don't we keep track of this. So keeping full strings in the queue. Okay, but is there something. So that's. That's a good observation. There might be something to do with something that we could do to improve things there. But is there something hopefully easier to attack? Like just looking at this, does anything else stand out as an immediate opportunity to improve that hopefully will be maybe easier than. Than this one.

Cunning Bathrobe: Got it. Let me think.

Stateless Samurai: Maybe I'll ask Height is what kind of data structure is the key?

Cunning Bathrobe: Yeah. So this one basically so, so this one is fine in golang because slices are fine to. To use this like this. If I, if I compare with like Java and something. So I could use list structure. But because of Golang I think it's fine. Like the how slices works in golang, would you.

Stateless Samurai: In my case, my understanding of Go is not super deep. Like I know basics of it, but could you break down line 102? Like what happens when you run this? What's the more specific, like what is the big old runtime?

Cunning Bathrobe: Yeah. So in golang it's constant time, basically average constant time. So it just adjust the pointer. So that's why I, I am using slice.

Stateless Samurai: Okay. Yeah, this is, this is.

Cunning Bathrobe: Average average time. Yeah.

Stateless Samurai: Okay, so what when is it not 01? If it's average, then o1.

Cunning Bathrobe: It does resizing and all. So when there is a size is half, basically like what is the capacity? Like it has capacity and when half the capacity is met, it will create like two times more capacity.

Stateless Samurai: Okay, so then in that case you're sacrificing something else. What do you think you're sacrificing?

Cunning Bathrobe: Sacrificing in the sense.

Stateless Samurai: So let's talk about something else then what is the. If we're thinking of memory usage, of the solution, what is the. Where are we accumulating the most memory?

Cunning Bathrobe: So we are accumulating the most memory in the queue.

Stateless Samurai: Yes, and that's exactly why I actually said let's just print them. Because if you print them, then we can actually try to optimize memory usage. If you're adding everything to a list, then you're already accumulating everything anyways. But in this case, since we're printing them as we go, then we can optimize this. So you're right. So the queue keeps growing. Right. And then what you're telling me is that. So this line is runtime usually efficient, but then that does mean that as you pop stuff off the queue, they're not getting deallocated, so the queue is getting even larger than it needs to be. Right?

Cunning Bathrobe: Yeah.

Stateless Samurai: Okay, so what can we. So I guess my point is either this queue implementation is slow or it's memory. And there is. So I guess the question is, can we do something that's neither of those.

Cunning Bathrobe: Sure, let me think about it. So in this case, basically what we really need is. So if I really see. So we start with start character and then we go. So I think what I am thinking in this case is to control the memory if it makes sense to do dfs. So you start with one character and then DFS style, basically. So you generate, you continue to go. In that case, basically you are not keeping anything in the queue. You just keep like one string at a time.

Stateless Samurai: Okay, sorry, one second. So I like that idea. That would be my next question. But let's say we care about the order, right? Because if you switch to dfs, the order of the output changes, right?

Cunning Bathrobe: Yes.

Stateless Samurai: Right. But let's say for now we do care about the order. We want them in this order sorted by length first. So the question is, can we improve this solution? This exact solution.

Cunning Bathrobe: Got it.

Stateless Samurai: By making the queue so that it's both efficient to pop from and also make sure that it's memory efficient.

Cunning Bathrobe: Got it. So the pop one is straightforward. Basically the slice can be changed to list. So that is essentially doubling list. So that's change of data structure. Like in terms of algorithm, it will probably stay same, but I think. So that will solve, I think the first part, the second part, where I was originally thinking of what's the alternative of keeping all the strings in memory? Like keeping all the strings in queue.

Stateless Samurai: So I'm not talking about. So I like the DFS solution, but again that's a slightly different thing. The question is you're using a queue for bfs, but I'd like whenever you pop something, I want to make sure that item is deallocated immediately.

Cunning Bathrobe: Yeah, so that will be list basically. So I can change the data structure to the list. So that should be straightforward. Yeah, sure.

Stateless Samurai: And what's the underlying data structure that list uses?

Cunning Bathrobe: Doubly linked list.

Stateless Samurai: Ah, okay, great. That's what I wanted to hear. Good. Yeah. Because we don't need random access. Right. We just need to pop. We need to add to the end and pop from the beginning. Right. And the structure that makes that efficient is a doubly linked queue.

Cunning Bathrobe: It. So it got this. So that's pretty much it. Yeah, Just making sure I didn't miss anything. So we created list and then remove. We just go to connections, create new string and pushback and then we just fetch the toke element and remove it. Got it. So I'll just reset and quickly Run it. Yeah.

Stateless Samurai: Okay, great. Did that solve that problem? All right, so now let's, let's talk about. Let's do a little bit of big O runtime and space complexity analysis. But to do that I'm going to. So let's go to line. Actually, what I'm going to do is I'm going to copy, I'm going to rename your main to just main two, and I'm going to write a new main function and I'm going to give you a new input that's a little simpler and then hopefully it'll make the analysis a little simpler. Okay, so let's look at that input. Let's try one more. Yeah, cool. So you can see the output. What do you notice about this input? First and foremost. So line 88, that main function. Anything you notice about what's special about this input?

Cunning Bathrobe: So in this input, basically the start nodes are same as connections. So like you have a couple of nodes which is connected to themselves and connected to other one and it's.

Stateless Samurai: Yeah, okay, great. Yeah. So, but more specifically, what I'm doing here is I'm allowing everything. Right. Everything can follow everything. So you have a full graph. Everything is connected to everything thing. Yes, it's a complete graph. A complete graph. Okay, cool. So then the question is, for this particular input, how many strings are in the output for the given N? So you can either do big O notation or if you'd like, you can be precise.

Cunning Bathrobe: Sure. So in this case, so they. What we are essentially saying is number of strings with length one and then number of strings with length two and like this basically. And then addition of this everything to length N and number of string for length one. The base case here is. I'm just writing. So yeah, please do length one, base case is N. And then number of strings with. With length 2 is n into N. Sorry, what's N? So N is number of nodes, like number of distinct nodes which are connected. Everything is connected to every.

Stateless Samurai: Can we use a different letter? Because N we already used for the length of the string. Okay, okay, so let's not. Let me give you. Let's do eight.

Cunning Bathrobe: Yeah, eight. Okay. Number of nodes, basically. So this is a. And then this is a square. And then the third one would be, I think a cube. Yeah, third one would be cube. So like this it will go to a power N. So length N would be a power N.

Stateless Samurai: Okay, great. Okay, so what do you think the total is big O.

Cunning Bathrobe: Yeah, so it is big O of a power N. Okay. Because that's the highest exponential.

Stateless Samurai: Good, good. Great. Yeah. So it is exponential growth. Right. And then.

Cunning Bathrobe: Yeah.

Stateless Samurai: So in that case, what do you think the big O notation of. So the next question is what is the memory complexity of the solution?

Cunning Bathrobe: Yes, the memory capacity is at one point of time it's going to keep the previous level of number of string in the queue. So a raised to power N minus 1 based on capacity.

Stateless Samurai: It's a little trickier than that. So you're right that that's the number of strings, but that's not the full story. Right. Because we're not storing. How much are we storing per string.

Cunning Bathrobe: Got it. And then those will be n minus 1 multiplied because the number of character would be n minus 1.

Stateless Samurai: Do you mind writing all of this and then writing what the final big O notation will be?

Cunning Bathrobe: So it will be a power n minus 1 and compute would be a power N.

Stateless Samurai: Wait, sorry, I'm. So what happened to this times n minus 1?

Cunning Bathrobe: I think since it's exponential. So okay, I think that would be. Yeah.

Stateless Samurai: What is it plus?

Cunning Bathrobe: Yeah, I think. No, no. So a power n into n minus 1. So my understanding is since a power n minus 1 is going to be very big, so that's basically going to be the complexity. So. So that's why originally I didn't.

Stateless Samurai: I don't think you're wrong, but we could be more precise because you already have that here, so why not put it in the big O Because then you have a more precise big O estimate of the memory usage.

Cunning Bathrobe: Sure.

Stateless Samurai: Yeah, There we go. Okay, cool. And yeah, so it's exponential and in a way worse than just regular exponential because we're not storing a constant number of stuff per item. The strings length grow too, but. So we keep storing more and more stuff. Ok, let's see. We've got five minutes. We could do. Why don't we. I don't think that's quite enough time to talk or to implement the DFS solution that you mentioned. But. So here we can see the memory complexity is not great. Right. We're using a lot of memory. So now if I tell you, look, order of the output doesn't matter. As long as we generate every string at some point we're happy. Then your DFS solution, you already mentioned that would be good. So can we walk through what the memory and runtime complexity. Let's start with memory memory complexity of a DFS solution would be.

Cunning Bathrobe: So the memory complexity would be. So it will be kind of like implemented in iterative dfs. So I'm not planning to use any stack. So it will be maximum length of the string.

Stateless Samurai: So that's how would you do iterative dfs. Do you think we could pseudocode or maybe even a basic implementation in about five minutes?

Cunning Bathrobe: Yeah, I can give it a try. Let's see. Might not be absolutely complete but I.

Stateless Samurai: Don'T worry, you get the gist of it. That's good.

Cunning Bathrobe: In this case let me write pseudocode actually string initialize to start. Okay. And then while string length of string is less than M so you pick the last char and then go through. So I have to call. Yeah, got it. So yeah, so that's where I think I was not accurate. So I have to keep the current thing. So which will make it should be implemented with stack because otherwise I will not get all the strings of that level. So yeah, so complexity from that perspective. So it will go. So it will go unlevel down and for each level it's keeping the string so it should be N squared.

Stateless Samurai: N squared. Okay, cool. Do you think there's a way to improve that memory wise so that it's less than that.

Cunning Bathrobe: So it's going N level down and it's keeping N length at that level? I. I believe it should be N scale. Yeah.

Stateless Samurai: Okay, sounds good. It's a little hard to discuss that without functioning. So I think we're about out of time anyways. Yeah, great. Actually yeah, why don't we leave it there. That gives us about 15 minutes to discuss. Cool, great. OK so now we're wrapping up the mocking preview portion. So let's talk about how to land. Let's first start by maybe you expressing how did you think it went. What are your thoughts?

Cunning Bathrobe: I think I should have used list from the beginning so that in the first part I think that that should have been like part of proposed solution. Other than that I think I took more time in memory and space complexity with the first part. I could be more spot on basically like I. I think you are giving some inputs and then I was trying to process. I had intuition but maybe I was trying to process that. So I would say improving from data structure like uses of data structure and then memory and space complexity like better little by fair.

Stateless Samurai: Yeah, yeah. Cool. Sorry, were you about to say something more?

Cunning Bathrobe: And the second solution it was not correct. Basically it was like I had like impression of DFS like on high level but the proposed solution was not correct. So definitely need to like maybe practice more.

Stateless Samurai: Yeah, yeah, no worries. I mean we were really short on time so that's okay. On that one. It's also interesting because a lot of people implement the DFS solution first, and then I have to talk to them about the order of output and then they may come up with dfs. But in this case it was interesting. You did it. You sort of went with the harder solution first and then. And then we had to go back to the simpler solution because the DFS solution is technically incorrect given the expected output, because it won't produce output in the same order. But a lot of people don't notice that. So it actually was good observation because you immediately mentioned DFS as soon as you understood the question. So going from the beginning, like, you understood the question really quickly. And I knew that because the moment you mentioned bfs, I knew you understood the question. You understood that it's effectively a graph problem and you're talking about the connections and nodes and stuff. So this was. That part was great. Very quick to understand the question. You obviously know the basics pretty well, basics of computer science and graphs and that sort of thing pretty well. So that was all good. Let's go to. Yeah. Where we got to writing the code. First observation I had was that you're a little on the quieter side when it comes to coding interviews. So as you're writing code, there wasn't a ton of explanation. Right. So it was long periods where it was just quiet. That's not a big problem. But I would recommend practicing just kicking it up a notch. Right. Like you don't want to go crazy, but just a little more, right. As you're writing the code, providing a little bit more information about what you're thinking through, what you're trying to do, what each chunk of code that you're writing is doing, just so that there aren't long pauses. Because some interviewers don't particularly like that. They want to know what you're thinking. And it's especially important because sometimes people might just not be on the right track at all. Right. And you don't want to find out, like 10 minutes into them writing code. So if you mention things as you go, we can sort of make sure you're. I mean, in this case, you were good, but some interviewers would like a little more expressiveness when it comes to that. Does that make sense?

Cunning Bathrobe: Yeah, it makes sense. I've got it.

Stateless Samurai: Yeah. Great. Another observation is, this one is a little tricky because you're writing go code and. And go in particular is mostly OK with very short, variable names like Q and C and so on. It's not ideal for coding interviews because what you want to do is make sure your code is readable. So my suggestion would be to even though for go, maybe it's not everyone does that in Google. I do recommend using more expressive variable names so that the code is a little easier to understand. Like probably okay, but things like T and top is okay. DNE it gets a little difficult to follow. So I would recommend writing more expressive, more readable and more descriptive variable names especially. I mean I for like that's fine. Usually like I for index is very common. N for length is usually very common. But things like C&NE and T& so on, like it starts to get a little difficult to follow. So I do recommend focusing on that. Your observation that picking the right data structure. Yeah, I definitely recommend paying attention to that in this case. Bfs. Generally speaking, if you're writing bfs, just go ahead and use a linked list implementation because then you get all one pop and insert time. Constant time, not even average, always constant. And it's memory efficient. As you insert and delete things, you're getting rid of them. So the standard thing is to use that. And so for other problems you might also just kind of keep that in mind. Like what is the especially past the first? Like if you want to write a quick implementation, that's usually okay, but if there's time and you want to improve things, it's always good to think through. Okay, what other data structure can I use to improve the runtime? Right? So you notice that and you fix it. And that was pretty well done. Let me see, what else did I write for feedback? Oh, I do recommend writing comments if something is non trivial, inserting some comments to improve the readability of the code. Especially if you're using very short variable names. So that's the other thing I was going to say. You do want to use the go style single letter variable. Then I would say inject some comments so that people can follow. Like in this case, like, I don't know, like, like what is any like new new string right? With with character attended. Something like that. Right, like something like that. Adding a little bit stuff like that, which also goes along with, with the recommendation of being a little more expressive as you code. And that's really good practice. I'd say like practice not only being more expressive in terms of explaining what it is that you're doing, but also write it down, add some comments. If you write, it's one thing especially since you're aiming for like you said, L7 if this was L3 fresh out of College, I wouldn't worry about that much. But in your case, what you want to do is get every advantage that you can in terms of coming across as a senior engineer. And one of the big differences between like a senior or staff and so on engineer versus like someone fresh out of college is that someone fresh out of college can write code that works and maybe even is good, but maybe it's not maintainable and readable. Right. And testable, but who's a senior engineer. I want to get signal that they write code that's not only, you know, working and hopefully efficient, but it's also readable and maintainable and testable and so on. Right. So paying attention with those things and comments can go a long way to help with that. Good. Variable names, comments, any gotchas, right? Like any, anything that you think might be non trivial or some reader might not notice or something you want to, you want to do that, right? Like maybe even like for example, like let's say online 127, you might even want to say something like, you know, use Linked list to make sure pops are efficient. Right? Something like that, right. It's not even that because then maybe some new engineer looking at this might be like, oh, I wonder why they're using that? And then the answer is immediately right there. Little, little things like that is always nice, shows that you're, you're a good coder, you understand data structures and algorithms, but you're also good at communicating things, right? And you're writing that's easy to read and understand, especially for let's say again, like you have a fresh out of college student or fresh out of college employee reading code you've written and they want to try to understand it like it's easier for them too, right? Cool, cool, cool. Oh yeah. So memory and runtime analysis. So let's go to line 101. So one thing I already mentioned was paying attention to the variable names. So make sure you're not reusing a variable that already is part of the problem where N is already a thing. So I had to mention that. But something to keep in mind, it's not usually in most interesting problems you have more than one variable that you have to do your analysis based on. So in this question you have the number of characters in the Alphabet basically, right. So which we called a. And then you have N which is the maximum length of string. And you want to make sure you're not conflating the two and using the same variable for two different things and so on. So I did really like this line 102, right? So defining your variables, right? So you write A. That's great, right? So in fact, I do recommend doing that. If the problem is not trivial, right? If the problem is trivial and you only have one variable and it's N, then just do it based on N. But if it's non trivial, you have multiple variables, like doing the first thing as we said, max, string. And then so now we have the two parameters that we need to do our analysis based on. And then this ling 1, 2, 2 pawn. Like this was good. I do recommend using for powers. I do recommend using that. It'll be just a lot simpler to type like the parrot symbol for powers. Even though obviously go and so on don't actually have that. But when you're talking about math, like in this case, in this world we're writing math, right? Like we're not writing go. And in math in the mathematical world, like this is usually fairly often done for ASCII representation of stuff. And it's really quick to type and it's readable. And then another thing, a super minor thing, but I also don't recommend switching to capital and lowercase. If you already decided in lowercase N is the variable, then let's think about that. So you want to write A to the N. Great. And then in addition to that, you could also say, so exponential in N if A is greater than one, right? Like, a little bit of extra commentary would be nice too, right? Because looking at this, you might not know, okay, what is that linear? What is it? But so it would be nice if you can sort of explain it too. You can look at that and say, oh, it's obviously exponential, right? And then this discussion here. Yeah, so this was good. But in terms of. So like, another thing I would recommend is practicing simplifying big O notation, right? So here what we have was effectively A to the power of n on n -1 times n -1, right? And this can easily be simplified to A to the power of N. And it just looks nicer. And the nice. And the thing you want with big O notation is simplicity, right? Now is this equal to that? I'm actually not 100% sure off the top of my head, which is why I was hesitating to say it is the other way. O of A to the N is like. And I know big. So you do know that big O notation is weird and that equality isn't. Reflects, isn't.

Cunning Bathrobe: Yeah, reflects again, like B.

Stateless Samurai: It doesn't mean B is equal. To A. Right. So because this obviously is sort of like less than equal to A to the power of N times N. Right. But so that does mean that I'm not sure if it goes the other way around too or not. If you can just ignore this was a constant like a C or like 5, then yes. But if because it's N, I'm not 100% sure. So it's maybe good to not get rid of it. And either way, even if it is cool, this is a nicer, more accurate description of the runtime. Right. So. And the more accurate we can be, the better. Right. And so I would recommend practicing this sort of thing more again, especially because you're looking at higher levels. Right. Like again, this was. If this was L3, L4, I wouldn't worry about this. Even if they just mentioned exponential, I'd be okay with it. Whereas L5, L6 and Clon. Like, I would like to see some sophistication in sort of being able to more precisely break down the sources of runtime or memory complexity and do so fairly efficiently and simplify it and so on and have a good understanding of all of that. So I do recommend practicing that a little bit more and especially writing it down like, like I want, ideally I want to see like actually somebody like literally doing like some basics of like, oh, it's equal to this and then that's equal to blah and so on. Like, and then like have some final answer so I can see how you're going about it. Which again also goes along with the whole sort of being expressive and commenting things. Right. So in this case you do want to show your work by literally writing down what you're thinking. The math side of it, which obviously you wouldn't like. Picture if this was a whiteboard interview, which Google used to do back in the day. But you would write these down. We could literally do some basic map on a whiteboard. So now you just do it in the comments, right. Like you just sort of go through all that. But I did want to say overall this was good. You had a working non trivial solution that involved bfs. You improved it. Especially as I was giving you some hints and feedback and suggestions. You fixed it and improved it quite well. It was correct. Almost immediately correct. It didn't really have any bugs, which was nice. And yeah. And overall fairly efficient. So I think with all the rest of the things that I said, overall this was a solid performance. So I think if you spend some time working on everything else that I mentioned, I think you.

Cunning Bathrobe: Know makes sense. I think these little things make big difference. So, yeah, I think in terms of polishing the explanation, policing, polishing, like, overall attempt. Probably my takeaway.

Stateless Samurai: Yeah, exactly. That's exactly how I would put it. Like, this was solid. You just want to polish it. Right. So. Which is why I gave you all the little things that you can do. But overall. Yeah. Solid performance.

Cunning Bathrobe: All right. Sounds good. Yeah, thanks. Thanks for your time here.

Stateless Samurai: Great. Any questions?

Cunning Bathrobe: I think I got very good feedback, so I improve.

Stateless Samurai: All right. Well, awesome. It's fun working on this problem with you, and best of luck with interviews and everything else coming up.

Cunning Bathrobe: Thanks.

Stateless Samurai: All right. Have a good day.