# Python Interview with a Meta engineer #### Watch someone solve the xml parser problem in an interview with a Meta 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. **Read more about the questions** - [XML Parser](/content/questions/xml-parser/index.html) ### Interview Feedback **Feedback about Redolent Broccoli (the interviewee)** Advance this person to the next round? Yes 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? 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 > 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. ### Problem discussion 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. Alright. 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. ### Problem-solving process 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. Alright. 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. ### Complexity Analysis Mighty Jaguar: 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: Alright. 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. ### Conclusion Mighty Jaguar: 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. --- This content includes a detailed analysis of an interview practice scenario, covering topics related to technical assessment strategies and interview feedback. The interview also entails a conversation about various data structure utilization and optimization techniques in problem-solving.