Python Interview with a Facebook engineer

Watch someone solve the xml parser problem in an interview with a Facebook engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

XML Parser

Interview question

1) Given a string, determine how many characters it would take for it to become an anagram of a palindrome. 2) Write a class to tokenize into XML.

Interview Feedback

Feedback about Redolent Broccoli (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

Overall you did really good Coding was good and clean Problem Solving ability is good but can be better by understanding how the states change when the code is running and how you can optimize for it. For the 1st problem, you did these things right 1. Clarification ahead of time 2. Explained the Algorithm 3. Defined the time and space complexity 4. Did a dry run of your code before saying you were comfortable with the solution. Please follow this in your real interview and you should be golden. All the best for your interviews.

Feedback about Mighty Jaguar (the interviewer)

Would you want to work with this person?

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

Questions were challenging and taught me new ways of thinking about certain types of problems. Interviewer was generous with hints and asked follow-up questions that tested my critical thinking ability.

Interview Transcript

Mighty Jaguar: Hello.

Redolent Broccoli : Hello.

Mighty Jaguar: Yeah. Hi.

Redolent Broccoli : How are you?

Mighty Jaguar: I'm good. How are you?

Redolent Broccoli : I'm doing well.

Mighty Jaguar: Okay, let's get started. Can you... alright? So let's do one thing first. Can you tell me a little bit about your background on like, what? And what you're targeting? Currently, like which companies you're targeting?

Redolent Broccoli : Are you can finished?

Mighty Jaguar: Yeah. So then I can ask the question accordingly.

Redolent Broccoli : Alright. Well, I am a recent graduate. I've been working for the past few months at a university lab working on their core services, mostly working with Python. And right now, I'm targeting large blue chip companies. For my next job. I'll I'm awaiting, I just interviewed with Google, I'm waiting on a response from them, which should come next week. I'm in the pipeline with Microsoft. And next month, I plan on applying to Amazon and if none of those pan out all I think I'll wait a bit and then do another round of applications.

Mighty Jaguar: Okay. Perfect. So, let's get started. We'll try to solve a couple of questions. Right, and, and, basically, we'll take it from there, like, how we solve it and this kind of thing. Alright. So that's the first question.

Redolent Broccoli : All right. We're going one at a time.

Mighty Jaguar: Yeah. All right.

Redolent Broccoli : Let's see, write a function to count the number of minimum characters needed to make a string an anagram of a palindrome? Ha. Alright. By minimum characters needed. Does that mean minimum character additions?

Mighty Jaguar: And additions. Yes. All right.

Redolent Broccoli : Well, I'll I guess I'll clarify some assumptions first. Can we have null or empty input?

Mighty Jaguar: Okay, if we had that, what would you return?

Redolent Broccoli : I guess I would might you know, if I got another empty input, then I would return probably an output of zero. Because if we assume that an empty string is a palindrome, you wouldn't need to add any characters to make it a palindrome.

Mighty Jaguar: So let's do that.

Redolent Broccoli : All right. Any other assumptions? Let's see. Is there a maximum length of the input?

Mighty Jaguar: It would fit in the memory.

Redolent Broccoli : All right. All right. Nothing else is coming to mind. In terms of assumptions, I'm assuming the input will be in string form. So I'll write the function signature and then I'll do the rest in pseudocode before I write any more code. Just let's see. We'll just call it minChars. Okay. And we'll have our input the word that will return an int. nNw I'm in terms of strategy for this problem, the number of minimum characters needed to make a string anagram of a palindrome.

Mighty Jaguar: So essentially, what I'm taking from that is, does it have you know, the right combination of character frequencies needed to be an anagram of palindrome? Since we know but a palindrome if you were to count for each character, the number of times that occurs in the string, a palindrome is going to have all of its characters having even value like an even amount of each character, or all of them even except one, which is odd. And that depends on the length of the palindrome itself, whether you need an odd, you know, value for one of the characters or not, though, in this case where we're adding characters, so we don't have to worry about... it'll end up... so essentially, what I'm thinking is in order to know that I needed to make anagrams of a palindrome count all the characters are getting the counts of all the words and essentially, find out how many odd values there are. Numbers of occurrences showing that right? Yeah, all right. Odd number of occurrences. And add one to output for all except one, unless there's only one character with an odd number of occurrences. And, output zero. Um, so in terms of time complexity, this solution is going to be, we need O(n) time to create the counter. We can use a dictionary as a counter. O(k) space... I suppose O(1) in this case for the counter? You know, it'll, it'll have additional memory, but at most, there's going to be 26 keys.

Redolent Broccoli : So then the index query you're making?

Mighty Jaguar: And I guess I should clarify yet what what can the input be composed of? Can it? Is it just lowercase letters? Any character?

Redolent Broccoli : Yeah.

Mighty Jaguar: All right. So in that case, I suppose you know, like any ASCII character, or any either way, it's... Naively, it's O(1) either way. Because, you know, there's going to be a maximum number of unique characters that can be a string, but it can get large, if you have, you know, that big can become very large. So O(1) space for the counter. Well, I like I just said, there's, you know, if we're counting characters, there's always going to be a maximum number of characters, or a number of unique characters you can have, like, if you're just working with letters of the alphabet, you can have a maximum of 26 If you have, you know, if you're using ASCII, I think actually has like a bit over 100 characters. If it's Unicode, then that's, you know, potentially 1000s and 1000s. But either way, it is a fixed maximum, that, you know, one probably doesn't necessarily scale with the length of the input.

Redolent Broccoli : I mean, you know, I guess, with the length of the input, but you never know what, how much memory you will be using. It won't be always constant. Like I could have just like one string, one character string, or I could have like, you know, 10,000 times A string by in those 10,000 characters, I could have key different characters, so it won't be because when you're storing it in the dictionary, the spaces counted by the storage of that dictionary that you have not with the number of a total number of characters that would be constant. You're not using each and every one, you're not creating an array. Like let's say, if I change it to Unicode, you wouldn't be creating an array for that Unicode completely, you are basically creating a dictionary. So alright. Yeah.

Mighty Jaguar: I guess I say constant. Because I feel it wouldn't be correct to say that the space complexity, the dictionary necessarily scales linearly with the size of the input, I could have an input that's, you know, 3000 characters, but have them all be the same character.

Redolent Broccoli : Yeah. So it would be O(k) where k is defined number of unique characters.

Mighty Jaguar: Alright. So we're defining it, I guess, you know, if that makes sense. All right. Let's see. Alright, guys, like I said, that makes sense. It's just at least when I'm working with like, just letters of the alphabet, I'm used to seeing the space complexity is O(1), because there's a maximum of 26. And 26 isn't a super big number, when it comes to, you know, computer memory. But I guess if we have an expanded character set, then it's, you know, it's more useful to say, O(k). All right. Let's see where we are 12 minutes in. So I'll speed it up a little bit. Alright, so create the counter O(n) time, then find out how many characters have odd numbers of occurrences that'll be O(k) time. Because we can iterate through the counter. And then another, and then we say, if you know, the number of characters that have odd numbers of occurrences is one, then return zero. So we return zero if there's only one pair with odd occurrences.

Redolent Broccoli : What happened if there's none?

Mighty Jaguar: Um, if there is none, then we can also return to zero in that case, and we don't have to make any changes. You're right. Or zero pairs. At most one, right. Yeah, at most one, we can say that. Otherwise, return num of chars with odd occurrences minus one. And that is the number of additions you have to make the even out all of those characters. And so I'm, uh, let's see, I'm comfortable coding this up if you're comfortable moving forward with it. All right. So, create counter, we're gonna have to...

Redolent Broccoli : Don't use the counter method in Python.

Mighty Jaguar: Okay, I'll just use a can I use a default dict? Yeah. All right. I mean, the counter is essentially a default because the default is zero. I think there's a few numbers.

Redolent Broccoli : But it also counts the character count, right?

Mighty Jaguar: Yeah, it does. Oh, and I just to put a bow on it. Its final time and space complexity is always adding. Alright, um, so minimum characters create our default dictionary. So I'll call it counter. Oh, find the name and I'm about to define it. And then our default dict. It's going to be lambda x zero. And we just return zero as our default. Oh, getting a warning sign, but never use I'm about to use it. And now we're a character in word. Counter plus character plus equals one. Now, um, find out how many characters have an odd number of occurrences. So we'll call this for odd pairs. Initialize it to zero. And then for pair in counter, and this will iterate over the keys, counter pair mod zero, or two equals one was one then return zero, num odd shares is less than or equal to one. Else pairs minus one. All right, I'm gonna skim that over, maybe we can run it on an example. So abbs. So here we're gonna initialize our counter, our counter is going to be a just one instance of a it's going to be two instances of b. One instance of s. So num, odd pairs after we go through this loop. For charactering, counter a, pairs equals one, B, we don't increment s, we do increment. And then we're going to return one or turn them on care to minus one. All right, this looks good to you. To me, it looks good.

Redolent Broccoli : Okay, all right. Can you do one optimization?

Mighty Jaguar: Anything?

Redolent Broccoli : Oh, when we? First thing in the first assumption that you find non redundant data? I don't think...

Mighty Jaguar: We need to add in that as a corner case you're correct. My mind which we can actually just turn into a ternary statement. Actually, we can't keep with me. That's right. And then any more optimized? No. Oh, you're right. In that case, this will catch both of them none and and empty case if not word return zero. All right. Now it's optimizations? I don't think there's much... Well, I mean, perhaps there's a way of doing this that doesn't include a counter. Let's see. ABBS well, that we're working with a I could you know potentially I could think of you know a two pointers solution if we were adding characters to make it a palindrome but we want to make it an anagram of a palindrome.

Redolent Broccoli : You will need the dictionary.

Mighty Jaguar: I will need to dig in. Yeah. All right. I suspected as much I was just checking. Thinking about potential solutions that don't include it.

Redolent Broccoli : So I say just make sure that the dictionary only has odd characters and not even.

Mighty Jaguar: You're right. Or can I make sure that it only has odd characters? Well, I could. Well, for me to know if a numbers final count is going to be odd. I mean, I could remove even characters, as I'm iterating over the counter, but we've already used that space, it would just be kind of destroying part of the counter early. So not a super good optimization there. It doesn't change our complexities.

Redolent Broccoli : No, no, I mean, the complexity, the complexity, we're doing the same. Alright, well, do you think it would. So right now you're doing a tool, it will remove that second.

Mighty Jaguar: Or I'm removed the second loop. Oh, I see. We keep account, we keep a count or running count of how many odd characters are in the counter. If a character's value becomes odd, when we add to it, we remove from the count of odd characters if it becomes or if it becomes odd when we add to it, we actually count of odd characters, if it becomes even when we add to it, we subtract from the catalog characters, and that saves us an extra iteration over the dictionary. Is that what you had in mind?

Redolent Broccoli : Yeah, I mean, when we have so that is one optimization can do the other way of doing that is when you're adding it to the character to the counter. You can check if the character already existed, if it existed, you remove the character if it did not exist and the character in that way you would only be our characters you don't even need anything.

Mighty Jaguar: I see and in that case, I would use a set because we're not storing... all right and then at the end I just do the same jazz here but with the length of the set so we'll call it on equals set now for character in word if they're clean there's there's not rooms odd pairs odd pairs and we remove all this replaces the length of on odd pairs. Alright, so that doesn't change the time complexity. I suppose we could redefine k to be the number. Well, I mean, I mean, to say the least.

Redolent Broccoli : So the number of odd characters. So I mean, today we have a sorry, what was that? While you're iterating? Yes, you will be temporarily storing odd num, like even characters. But then at the end of the loop is when you will only be storing the characters that KR characters. All right.

Mighty Jaguar: But I mean, I feel like our space complexity is still going to be k the number of unique characters because say we have a situation where you know you have every unique character appears once before anything else, then you're going to have a point where the size of the set is the number of unique characters and that would affect the space complexity because you need that amount of space to be able to run the algorithm I that's at least that's my understanding.

Redolent Broccoli : I mean, you would you'd only have to make, let's say, if every character in the string is unique, and we said the string can be in memory, then you wouldn't have to worry about the space complexity in that scenario. All right.

Mighty Jaguar: That makes sense. Yeah, I guess still. So you still you still think that it's okay. where k is the number of even characters? These names are sorry. Yeah. odd characters. mixed it up. All right. Then yeah, in that case, I'm comfortable with this solution to the follow up you gave me it seems pretty optimal.

Redolent Broccoli : Okay. Yeah, I think this looks good. Okay, let's go to the next question.

Mighty Jaguar: All right. If you're able to tell me... Well, this be the last question. Are there three?

Redolent Broccoli : No, this would be the last question. All right.

Mighty Jaguar: All right. Excellent. Now

Redolent Broccoli : So basically, just anyone normally asking Java so I can give you this. Do you write the method?

Mighty Jaguar: It would just be class tokenizer. If it's not inheriting from anything else, then it's calling and then the body of the class. Okay. There is no access specifier.

Redolent Broccoli : Yes. Okay. So I'm not used to Python, it's fine. I don't know how to put them into it. Just can you share it anyway? How do you write the method is?

Mighty Jaguar: The method if it's a method, do you need to include the self as a parameter? Okay. Yeah. And then return types aren't explicitly specified either, though, you can add inside depth is nexttoken. And then you don't need the there's, you can add the return type through an annotation which is optional. And isn't enforced by language. I think it'll just warn.

Redolent Broccoli : This one combined, so just wanted to...

Mighty Jaguar: The instincts I say. You don't need to specify the types for... there. It's you. Would you typically you want. Does token only include variables in it? Are there any methods? Yeah. No. All right, no methods. In that case, you can just do this. You can add a data class decorator. And then what that gives you is it'll, you don't need to specify a constructor. You just say what attributes you want. And their type. So what type is actual? That's which would be just in Python would just be str? And does it have a default value?

Redolent Broccoli : Oh, no. I mean, I don't even have a default value like, we are not.

Mighty Jaguar: Alright, all right. Yeah, in that case, you can just specify, you just specify all the attributes like that. So like action string, if you were to add, like another one value, and then its type. And so what the data class decorator does is it takes those annotations right there, the auto generates your constructor, so you don't have to write it yourself. And it also implements a bunch of other, you know, automatic functionality that we probably won't be using, but is really useful.

Redolent Broccoli : Okay. Why is it highlighted?

Mighty Jaguar: I'm not sure. I think value is a built in Python. Is it? Okay, if I check? All right. Let's see. It may not be... Yeah, it's not, I'm not sure why it's highlighted. Okay, I think this editor might just not be used to the data class syntax, too, though.

Redolent Broccoli : This will be what do you want to watch? Alright. So you have a tokenizer, which should create a token like, which will tell you like, okay, whether there is a next token or, or not. And so the process that we are saying is like, we are getting a lot of XML from this, and we want to tokenize them, like you might have integrated with multiple systems. So if we are integrating with multiple systems, we get a lot of elements that they form, we get it as tokenized. And we want to pass it into an object. So first, we need to define the subject, because that's the object that the sponsor will return. All right. How will you be present adopted?

Mighty Jaguar: Well, if it's XML, I have XML, I think it's it's tricky if we're just working with what you have here, where we just have, you know, nested objects that just have, you know, identifiers, and then values if we if we don't have to deal with like, you know, additional attributes or things like that, then we could just use a dict to represent the XML.

Redolent Broccoli : Yeah, but like, instead of a dictionary, because in the dictionary, if you want to preserve the hierarchy, you won't be able to do them.

Mighty Jaguar: Sorry, what was that?

Redolent Broccoli : If you wanted to preserve the hierarchy? So in this case, technically, this is, it would look like if you re formatted the XML?

Mighty Jaguar: Well, I mean, you could if you use the nested dictionary.

Redolent Broccoli : Yeah, I mean, it's not clean, that's all I'm saying.

Mighty Jaguar: All right, then that, then I suppose you would use a tree? Okay. Yeah. So you you'd say, you know, A has two children, B and D.

Redolent Broccoli : You can you can create your own class. That's what I'm saying. It played a role. What would that be? Like? How would you store the information in that class? If you had a class called some XML normal or something like that, what would be different things that you would have?

Mighty Jaguar: I would have a I suppose I would have. It's the the name of the node. So like a or b. And then I would have a solution. Do we want to add in functions that would make it easier to parse the XML so save I had, you know, I wanted to search through its children by name.

Redolent Broccoli : We don't care about. So we are just preserving that. That structure, we don't care about how it is the US. If you basically you can search it, like, we don't get about uncovered as they used to be. All right.

Mighty Jaguar: In that case, I mean, for me, at least it comes back to a dictionary being the best way to store it. So each XML node would have a name. And then a dictionary of its children, which each have their name is the key. And then XML node as their value?

Redolent Broccoli : Why would you need a dictionary for them?

Mighty Jaguar: Just because it's the best way to have you know, O(1) access to each of its children, I could, you know, have a list of its children.

Redolent Broccoli : But then I have to the earlier thing is, again, we are not optimizing for any kind of time. Alright, we are not, you're not storing, I mean, we're just basically gonna store might not gonna optimize.

Mighty Jaguar: Alright, so if we want the most efficient storage, then...

Redolent Broccoli : Yeah, just like, Okay, if you just want to store the empty, instead of a dictionary, what do we use for children?

Mighty Jaguar: Well, it would save space, if we use a list that takes less space than a dictionary. So you would have the name of the node and then a list of all its children. Okay. All right. So you want me to write that down? Or? Yeah. All right. Then. And string children lists, we could make it a data class.

Redolent Broccoli : Yeah, I mean, so you have I mean, you have a list of children. What about the values? Like, how do we store I?

Mighty Jaguar: Well, I how do we store why? You're correct. I, for a moment there, I forgot that there's a distinction between nodes as children of an object, or have a node, and then the value that a node can take distinct from its name. So each child, so I guess each node would additionally store a list, or I guess just a value a string representing its value, the potential values it can take. All right. Then I believe that at least for this example, I believe that covers it.

Redolent Broccoli : Okay. Yeah, I mean, we would have, you can assume that you would have XML in this format. So multiple nested things, but we would only have it in this format. Even... All right. So are you comfortable with that?

Mighty Jaguar: Yeah, I believe I am. I'll see if well, because I'm assuming you want me to write a function to parse this into an object. Alright. Well, yeah, we'll see. If you know, maybe there's a way to change its its structure to make the parsing more efficient once I figured out the parsing algorithm, but for now, this you know, this basically lays out the basics and what we need...

Redolent Broccoli : Sounds good. Soon, all right. So then this return type, we can see it is an XML right? Yeah.

Mighty Jaguar: Pardon me if I missed this, but what is the action in the token?

Redolent Broccoli : So yeah, that is Line 62. Do the same.

Mighty Jaguar: Oh, I mean...

Redolent Broccoli : Actions would have three basically three values only three types of string one is begin one is value minus n. What does that mean is the beginning of the tag and it will give you the tag name. Alright, the value value would basically say if it is a value or not like value of the tag. So, value between the tag and end would say it is the end time. So if we were to write this about this so it will look something we can be and do...

Mighty Jaguar: All right and a clarifying assumptions here each objects that we get, it's only going to consist of one root object right? You wouldn't say have you know a and then you know, if I were to put the you know, that's a different object if I were to put another node down there, alright.

Redolent Broccoli : You can assume that for the simplicity of this problem, it would only have one top level object.

Mighty Jaguar: Alright? And it's okay if I go to the restroom real quick just 30 seconds all right. All right, so let's look, action value. So let's see. Well, essentially what we're doing here is it's kind of recursive. Yeah, essentially. But I mean, I'll see if there's a way I can do it. Perhaps iteratively as well.

Redolent Broccoli : I mean, in recursion, how would you do it?

Mighty Jaguar: Um, if I were to do this recursively just rough idea is every time I open a node or I opened a node that would be a recursive call to fill out its children. Or it's about to fill out its value and children. And then once I encounter a closing node, I just returned that object.

Redolent Broccoli : So you think you can do it recursively can you lay down the code?

Mighty Jaguar: The pseudocode. All right, well are basically.

Redolent Broccoli : Just a high level overview of like, okay, how would you do that? Recursion would be really tough.

Mighty Jaguar: You think recursion would be tough? Well, my base case would be a closing node. At least one of my base cases. Let's see our inputs would be well, you're correct. I don't think, yeah, recursion would be hard. Because it's not like we're given, you know, the packages. Actually, let me... Let me gather my thoughts for a second. I guess... it wouldn't necessarily be the I guess it would be unnecessary. And not necessarily given that we're being given the input just as a stream. It's not ideal for recursion. Okay. It's not like we're being given, you know, objects that then have children that are their own nodes. And then, you know, the, the recurrent, the, the eventual structure of the object we're making is recursive, but the way we're being given that object is not...

Redolent Broccoli : Exactly. Alright. Right.

Mighty Jaguar: So we're, since we're being given it iteratively. I'll do it iteratively. So we, I mean, we're gonna start with four token in the tokenizer. Or I guess, a while.

Redolent Broccoli : So what data structure?

Mighty Jaguar: That XML node data structure that we just talked about?

Redolent Broccoli : No, no, no, for creating that node? That's the object that you're creating. In the, in the parser? What data structure are we coming to use to create that?

Mighty Jaguar: Well, while I need to use a string, I need to first create strings representing the name and value. And then I have to create a string representing it, or a list representing its children. If that's what you were asking, and then those compose the XML node.

Redolent Broccoli : No, I'm not asking that. But let's say think about that. You have that? If you look at on line 72. All right, one action at a time. So you know, when the tag is beginning, when the tag is closing, and what the value is. Alright, so once a tag is begin, after that, if you see a begin, you know that it's such a child of that, right. Yeah.

Mighty Jaguar: So all right. The... Well, I should we go back to the the general gist flow of the solution, because I understand what you're saying.

Redolent Broccoli : Yeah, basically, for that only I was talking with you, just to get you much like giving you hints on that.

Mighty Jaguar: Alright. Okay. So we're for each day, essentially, while the tokenizer the I'm assuming that the basic you know, our top level control structure is going to be a while loop in a while. There are tokens lesson tokenizer. We can there's essentially two the you know, we can either get a begin an end or a value so there are three cases. So case one is a begin. Case two is and I would use a switch statement, but there are none in Python, at least in 3.9 I think there is in like betas and three point 11 But I'm not familiar with it yet.

Redolent Broccoli : Isn't next month fine? I don't care about that. All right.

Mighty Jaguar: Now let's see case one begin. If we get a begin token, and what we're going to want to do is init a name, and we might want to use a stack here.

Redolent Broccoli : Because we're, you know, we could have to construct another node, while we're in the process of constructing, you know, a top level node, we need to, we might need to construct, you know, one of the two children. So I'm, there's probably going to be a stack involved at some point. But I'll save that for later. If we get to begin it, we won't be let's just not think about blackbox. This not thinking about the recursive structure yet. In the case, we get to begin, we emit a name. And then if we get a value, we're assuming that we've already gotten a begin. In a name, empty value. If we get a value action, then we define our value stream. If we get an end, then we make current node named value. And then now how do we handle the stack aspect? What I'm thinking is, every time we end a node, we create our current node, we push it onto this stack. And then once we we create, to now we... will be getting... we can emit a children a list of children.

Mighty Jaguar: So what's your question? Yeah, I mean, when you when you can create a list of children, all I'm asking is like, if you do it at the end, and put it in a stack? How would you make in our current example itself? How would you, like store a, b, and then c? And then when you're creating c, you're basically then putting it in a stack? Which I mean, like, how, where do you store a and b?

Redolent Broccoli : Well, I guess we could sort on the same stack, but that we would have to know, you know, after we're done, you know, once we've moved up a level, essentially, we need to know how many children we need to pop from that stack. Which I unless we keep track. That's, you know, we wouldn't know. So I'm thinking we might need a different structure. If I can, I have a notebook in front of me if I could run through an example on that notebook.

Mighty Jaguar: We need a stack and I do need to...

Redolent Broccoli : Alright, well, at least I'll run through how we're going to use the stack. So got our stack. We begin a current name and value push to stack. Your name and value and then I'll just run through the example. Alright, so we begin a, we init its name, an empty value. And then we begin B. So now we, if we I would say let's see what happens say if we push to the stack. If we get another begin statement before we've encountered an end statement for the node we're constructing. And then so we get a as a we begin with a and then we get... That begins statement for B, so we push a onto the stack. Then, and now we have the, you know, and its value is our current, you know, values we're working with, then we see C, so we push into the stack as well, we push b to the stack and then we get C's value, y and then we get end for c. So we... let's actually distort value by not seeing the whole pushing. We push when we get in n and, and we'll know if we didn't push when we get to begin. Or if we didn't push when we get another begin while we're working with a certain node, then we would override the values for working with, you know, the more top level values with the values of its children. And that's not good. I suppose in that case, we every time we encounter a begin, we have to know the value how many children that node has. So we would want to keep count.

Mighty Jaguar: No, you don't need actually. So alright, just in the interest of time, and maybe the solution randomly, you when you begin, you first check the stack itself. If you have a if you have a node in a stack, you basically. So when you enter it, the node with a name and empty value and an initialize list, you basically pop the current value if there is any, and then add that, add this in it as one of the children. And then push both, actually, you don't need to pop, you can just have like a top or a peak. And then add that add the current node that you have into that and then push push it on top of the stack. When you get an end, you just pop out of the stack. If it is, if the stack is empty, just remove it and define string. You just basically take the top and then make the value at the current one. That's it.

Redolent Broccoli : All right.

Mighty Jaguar: Um, can you do that? To make sure to just need one variable called root so when you hit the end of the stack, we just assign that the value of that pop something only when that when presented and then district on. I see.

Redolent Broccoli : Let's see... I'll all admit I'm gonna have to look over this for maybe a minute or two later to really, truly understand it. But thanks for the explanation. Do you have any more follow ups or should we do?

Mighty Jaguar: I think? Yeah, and then we are good. Yeah, I mean, the way you solved the first question, I first thought that you'd have seen that question. So that's why I was... That's why I gave you this question. This question I normally asked the seniors and I actually gave you a little bit more than what I normally ask them. Like? Yeah, this question is mainly for the senior. But I've actually, like only given you just two parts. Just to define the class and to implement the parser. The parser is for normally anyone. But to defining the class and normally the seniors, I normally ask them to give me trade offs. Okay API, you have an XML node, you can have children, like the, the one that you created, is a generalized, like denormalized list type. But you can also have like a hierarchy, like, you know, you can have XML node and have a children have a parent and those kinds of things.

Redolent Broccoli : Alright, do you think that if I had been more familiar with doing a breadth first search with a stack that maybe would have come more intuitively? Because that's I'm getting that impression? That essentially what we're doing is just we're being given the values of a BFS through the... Actually we're not? It's more DFS? The I mean, yeah, I'll just look at it later. I'll say so the first question, I haven't seen it before, what I have done is, I've done you know, palindrome related problems. So I knew that property of palindromes that you need, you know, every character to either have an even number of occurrences or just have one character with an odd number. So that's the only part I knew in advance.

Mighty Jaguar: Yeah. I mean, that's what I thought. But normally, people hear that, okay, I've seen this question so that don't ask this question kind of thing. But I wasn't sure. So I was like, Okay, let me test them out. So that's why I gave you a little bit harder problem. Come back to your level. But it was mainly to, like, I think you can, if you practice a little bit more like you would be able to solve these, as well. And this is this is basically, like a normal stack problem, you would you would have been see it. And if you look, if you correlate it, it's normally, like, if you get an exception or something, you get a stack. Which kind of that kind of a problem. So okay, how does the value go in? When, when it is out when it is in? So if you look at it properly, you wouldn't start D without closing b? Because if you did, basically, that's missed a connection. So, you did not have to worry about like, you know, you were basically thinking about like, Okay, how do I find out all the children, you did not have to worry about all the children, basically.

Redolent Broccoli : All right, because we just added the children to the one that's at the top of the stack.

Mighty Jaguar: It's not it is basically, whatever we I mean, whatever it is that the what is the current top of the stack, we decided to capture that as a child. That's it. You don't worry about you know, so is like for a you do not have to worry about like, Okay, you have to first find out B and D both, you can actually go while you're doing it. Alright.

Redolent Broccoli : Let me see if I may copy this into my notes. So that will actually I'll have the recording for later. So never mind that.

Mighty Jaguar: Yeah. I mean, if you want a copy, you can copy it. Okay. So so yeah, I mean, I wasn't expecting my time, I wanted to really get a feel of like, okay, what your problem solving skills are and those kinds of things. So you have good problem solving skills, just try to understand the problem a little bit more, and then you would be able to do it. So the first random as I said, like you did really fast and you are on point, and those kinds of things. So I know the optimization was like, neat thing. No, it's, yeah, it's not like that. All right.

Redolent Broccoli : I mean, but at the same time, given that it's, you know, we're dealing with odd and even, you know, there's really only two states that I have to keep track of, rather than keeping track of the actual count, so it makes sense that you would do an optimization like that. I just didn't see it.

Mighty Jaguar: Yeah, that's perfect at all. Even even what you had was, like, because it doesn't change the complexity and other things. So in what you had was correct. So yeah, I mean, in the real interview, they wouldn't, they would be fine with whatever what the solution is you had previously, what would be fine. Alright, I just wanted to show them that. Okay. These are the different ways you can think about a problem like that. When you haven't, when you understand that, okay, how biggest? How do you consider different states? And how do you how can you optimize them? In your coding algorithm as well. That's why I showed you that. Alright..

Redolent Broccoli : And yeah, it made perfect sense. So thanks for that.

Mighty Jaguar: And for the second problem, as I said, like, decision making be further senior. But the reason why, and I just gave you particularly very particular points, that you would be able to at least, show me how you were thinking, and that's all I was looking for, I wasn't even thinking about that you would be able to code if you have core code in it, it would have been awesome. And I would have told you that. You might be like, even if you start as a junior right now, you might be getting promoted very soon. Yeah. But the whole idea there is that was that I just wanted to understand how you were thinking. And, yeah, I mean, you're thinking in the right direction, just try to embrace the columns basically. Take a step back and see whether like you what are the different things that you are trying to while different things that you're trying to connect? So let's say in the previous one, you had the even an odd state that you are trying to connect, basically trying to find out like, which one was even which or not, in this one, you are trying to connect the child with the with that parent, basically, like if I summarize, that is what you were trying to connect. And, and, yeah, I mean, the only the only thing was that you did not take a step back, I would say like, if you're trying to solve the problem, take a step back, and try to see, not in an interview. Like, you don't have to wait till the interview. But basically, when now you're practicing, try to take a step back and see whether how you're imagining the problem.

Redolent Broccoli : I think, what are what I was doing in my notebook, you know, actually kind of working with an example. I should have done that earlier. And I should have also asked, you know, will we get a value action? Will we ever get it after we've defined a nodes children? Because if I had known that we're only getting that value, right after the begin statement, then I would have you know, if I had come up with that stack solution that you talked about, you know, I would have immediately known that was correct. I wouldn't have had to, you know, I might have, there might have been some confusion about me being like, Oh, well, what if the value comes after? You know, we've defined the node's children. But, you know, so I guess, other stuff I should have thought about?

Mighty Jaguar: Yeah, no, no, no. I just, yeah, I mean, just make sure that take a step back, if you have like, in the first question, you have certain assumptions, try to ask them. And you should be good, you will be able to solve it much faster, much quicker and in a much optimized way. That things that I liked was basically the first question, everything you did, like you had all the modifications ahead of time. What algorithm you're going to use, what was this complexity? Then after coding, you ran through, like you verify whether your code works or not. And and yeah, I mean, you kind of handle all mostly all the edge cases except one. And yeah so... So what I did was good. Just if I mean, just when you're practicing, try to take a step back and look at the problem, because if something came came up, like I'm assuming they're doing the code day in, day out. So if something came up unknowing something like, you know, out of the box, you would be able to solve that much easier.

Redolent Broccoli : Or I would, or wouldn't.

Mighty Jaguar: You would you take a step back and make, you know, even when you're trying to, like, now practice with any of the lead code problems? If you take a step back and see, okay, how does? How does things go? Like you mentioned in your notebook? That you're basically taking notes on like, okay, yeah, imagining how the process would happen. Basically, that's what I'm talking about, like taking a step back, trying to imagine how the structures can be how, how the data is, knowing how the state change likely will help you in solving any random problem. Much faster.

Redolent Broccoli : All right. Changes of state. I'll write that down. Yeah. All right. That understood, definitely. Is there any any other feedback you want to give?

Mighty Jaguar: No. Any feedback for me? Did you enjoy?

Redolent Broccoli : I yeah, I enjoyed myself, have good things to write in the in the form when I fill it out. So yeah, I mean, thanks for a great session. This is definitely really helpful.

Mighty Jaguar: Yeah. All right. All right. All the best and have a wonderful rest of the Sunday.

Redolent Broccoli : All right. Thank you. Bye.

Mighty Jaguar: Bye.