Python Interview with a FAANG engineer

Watch someone solve the longest palindromic substring 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

Longest Palindromic Substring

Interview question

Given a string s, return the longest palindromic substring in s.

Interview Feedback

Feedback about Tea-Smoked Gyro (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?

2/4

You did much better than last time and keep improving your communication skills, good luck!!

Feedback about Occam's Unicorn (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

He gave some great feedback and guided me to the solution, especially the second problem. I was lost in my implementation as to why my code was working as expected and he suggested to make some changes to the helper method. I felt he was in a hurry as i don't have enough time to think through the followup and this was evidence when writing the code as he corrected that he was expecting the actual strings and not length

Interview Transcript

Occam's Unicorn: Hello. Hey, how are you?

Tea-Smoked Gyro: I'm fine. How are you?

Occam's Unicorn: I'm good. I think. I interviewed you, right? Like a couple of days ago.

Tea-Smoked Gyro: Yes, I believe so.

Occam's Unicorn: Awesome. Awesome. So, do you have any interviews coming up soon?

Tea-Smoked Gyro: So currently, I don't have any more I've just been applying and just preparing.

Occam's Unicorn: Okay. Let's solve some problems today. We'll see if you done this or or not have. Have you done palindromic substrings?

Tea-Smoked Gyro: So, before?

Occam's Unicorn: Do you want to solve it? Okay, let's do that. So, you're given a string and we want to find the number of palindromic substrings. What do I mean by that is like if your input is ABC, you have like ABC is not a palindrome right? You have a is a palindrome, b is a palindrome, c is a palindrome. So, output is going to be... again example two say if your input is going to be AAA then your palindromes are going to be a and also aa and aaa. Yeah, there are going to be six palindromes.

Tea-Smoked Gyro: You can assume that the input is valid, not to be an empty string?

Occam's Unicorn: You can assume that it is not empty.

Tea-Smoked Gyro: So, you can assume that is not empty. Can I write on line 14?

Occam's Unicorn: Yep.

Tea-Smoked Gyro: So, one thing I'm thinking about is this approach. So, we can use you can use your question. So, basically we're going to start from the first and we like the first input in my five. ABC for string. If A cannot be taken out through before we iterate further. Do we have I over here. We have j over here as well. So the palindrome so they will do like a recursion recursive call to expand a little bit to the end. So we added into our outputs so we return it if is true as a palindrome. So it is true. If it's false it's going to return null, the time 0 must be false one must be true. So this word that is then interested a little bit more to see what sounds like true for them.As compared to A and B and C.

Occam's Unicorn: So what is the time complexity and space complexity going to be for this?

Tea-Smoked Gyro: The time complexity is going to be exponential, because it's going to depend on how many branches we created, O(2^n)? And that will be dependent on the branches you created. What is find?

Occam's Unicorn: Can you explain why it's exponential? I don't think this is exponential, exponential is I mean... And power and or like n power or something? I don't think this is exponential. Because it's polynomial.

Tea-Smoked Gyro: I mean. So when I say exponential...

Occam's Unicorn: What is that O(n) raised to?

Tea-Smoked Gyro: O(2^n)?

Occam's Unicorn: Can you write it down?

Tea-Smoked Gyro: Yes. Oh, so as we enter the depths of the branch we created?

Occam's Unicorn: Are you sure it's going to be O(2^n)~`? I did not understand what you're saying. So you're saying for every i, you're going to check every j? Whether it is a palindrome or not, right? So your I goes from? i goes from zero to 10, right?

Tea-Smoked Gyro: I go from zero to n, if n is the length, right?

Occam's Unicorn: So for every I your j goes from, again 0 to n, right? And then for every palindrome you're going to you're you have to check for every i and j you have to check whether it is a palindrome or not? So this is also going to be worst case it's going to be n right? So like you have three levels there is going to be O(n^3) right?

Tea-Smoked Gyro: So I'm going to go into support three, is it each of the eligible.

Occam's Unicorn: Right yeah, so n cubed is not exponential it's a polynomial and cube is less than two power and so... Okay, can we do any better than that?

Tea-Smoked Gyro: The other approach I can think of is to use... So the approach you can try to use to program the main program. So basically their program a lot of this is because toppled beginning over such as fun. So can always expand both left and right. I see is because one thing we can we can notice for this question is for the first line 5, if you have a is a palindrome b is a palindrome c is a palindrome. This as line seven, so you can always expand from wherever it is. And whoever the b is and expand. I say out loud, actually followed by the palindrome.

Occam's Unicorn: Can you can you write that, write that down, whatever you're saying?

Tea-Smoked Gyro: Good is so colorful, and we have to follow to learn to follow. So secondly... From the class center from the classes. Contrast is you can spend all your time on both left and right sizes so you can learn. So for the current contract is dependent on if you can go. So based on this, so if we can go forward to the end of the inputs array, they will always know for no credit on this palindrome, they will always go the real estate is as an example to have a the first one to get out for sale, which is tough for me. So we'll come to the second a what's the point of actually one go to the left go to the right. And joyfulness. So for the beginning I went out good with side. And this is part in right side. So this I thought we'd go on about what is just points on a bunch of second A. So from there, you can have a different lens on the prism, you've currently really fun and we can always increment our five minutes.

Occam's Unicorn: Okay, so much difficult for me to understand. So like, do you want to go ahead and code it you're good with this approach. Or before that let me ask like what is the time complexity going to be with this?

Tea-Smoked Gyro: The time complexity is going to be O(n^2). Okay. This is compressible.

Occam's Unicorn: Space complexity is going to be constant? So you're not going to populate dynamic DP Table?

Tea-Smoked Gyro: No, then we don't need to actually.

Occam's Unicorn: Okay, let's then let's do one thing like let's. Why don't we go ahead and code this up and we can problem solve by record.

Tea-Smoked Gyro: Okay awesome. So currently we've selected a programming language okay. I have to wait for it to function two strings we can have our string soup our string this has to be so wonderful to just be at industry substring then on a substring. Okay, so far, we have done this too. So follow this test. What good responses before to another good face what are the different because I even went on levels just in the cities with the. It was gone for the induction. The company that we discuss next and finish it before we move on to. So this is a really updated day. First good Bose system what does it do for you? Good substring of a string index we have this true then at the end of this. So now let's create a function second function is the function shouldn't have get. So this substring this substring is going to be funny but you wouldn't add forces that have... This is true. Okay, so we'll set the talents so what I'm gonna do searches and so what this is with less than good angles to zero, is that true x firstly is to x must be close to true facts of the case one of the users return but as soon as I guess so just totally can starts inputs are n both substring substring assistant equal leg length x. So can I work with example nice?

Occam's Unicorn: Yep, let's do it.

Tea-Smoked Gyro: So visiting research lab for a 300 the inlet for a phone number of good traditional full five because it is not at ABC. So in line 48. So the length, so that's 3, good the status pretty soon. So our index resume index. So let's go to one index 000, I'll be in the fifth corners function we get softer portion the contour contour this, but it's not as tough to start to zero in zero. So the left one zero for now for the worst part is good and equal to zero. This is true because our ft that I got a zero message tonight. And I observed and mentally which is pretty. So the contract certified. They will typically use a string of thought, which is a, the ecosystem of entities a token, a gift is not going to return to Sunday. So there are consequences to seven to after one in stocks, the cost to the end has to be close to one. So welcome up to the while loop minus two to three to the last part that I got to do, which is true because now our start is minus one. So, to begin, we're going to return total length. So that you want to not to be the ones who are opposed to, to the one to a question. So a kind of string question. As to why we didn't need this wave will not flow. Well, with a nesting depth map for each nested one. There is no need to go to yet because now it's now zero. So of course, if he finds a choice, they will put information on our index plus one, so this will be zero. They will constantly other partners function continents. So I'll start with zero and the one to the left is zero, they said the worst part is gonna go to zero and end their string, which is true, because that is zero. And the end is one, which is true. So in essence, the system will check the strongest part, which is a, the Z equals string of n, which is B does not equal because A is equal to b. So when I return the full length, which is zero. So now our polished substring will be still one as line 43. There, we're going to import our index. Now for a scientist to do one continent is to one, two indices, one on one. But a request function.

Occam's Unicorn: Can I do one thing? Can we run the test cases that I've given you?

Tea-Smoked Gyro: Yes.

Occam's Unicorn: I think I understood what you're doing. Let's let's run the test cases that I've given. And then maybe we'll run more, but let's run the test cases that I gave you.

Tea-Smoked Gyro: Now ABC as it is a test case.

Occam's Unicorn: Awesome. Awesome. So yeah, let's do another problem which is similar to this. Let's find, what is the maximum substring palindrome, or longest substring palindrome?

Tea-Smoked Gyro: So one way we can try to find the longer palindrome is to say this, this is the same question or just adding it. We're going to add it. So there is this item. So can I write my first one?

Occam's Unicorn: Well, yeah, yeah.

Tea-Smoked Gyro: But no one to learn to be equal to this or not. So the because of this for now, so at the end of this, because the remarks were actually probably getting much bigger. Have I dismissed because I just index this index is going to break out when it is out of the loop? So what's the one thing for the day so over a year? So it can I can condense this list. So what are the different lists? Honestly most palindrome because max of the ones we're planning on palindrome substring. So we'll do the opposite of relevant then over here, so having different resources, you don't need a system which really does the mass palindrome say to these fools, you will get infinity for not because the first time will come out of the truth, it is. So over you most wanted before we look at the difference returning from you don't return. One of the default is the city. This returns.

Occam's Unicorn: Now, we want to return the string itself. Not just palindromic substring.

Tea-Smoked Gyro: Once it's done is returned itself, okay?

Occam's Unicorn: Yep. Okay. Whatever is the longest palindrome we want to return the string, not the length.

Tea-Smoked Gyro: Okay, so let me think through so we don't want to line 58. So if you want to learn for the first time, then over here, evidently, we don't need this anymore. So we can just do something from this place. So without only this, so because this index, this index is the midpoint of the midpoint of our span, both left all right. So I mean, just put in this, I don't want this to end. So one thing I can do for me too.

Occam's Unicorn: So I'd like 27 are you going to read on start and then?

Tea-Smoked Gyro: I'm going to fill gaps in the fields as you can see on this looking at line 58. So, from this we have the starting index route, which is this, then we have the index which is a so because we also... Okay, I see. So, for me, we are this therefore displays what not to do, because we are the middle. So, if you are the middle, you kind of get mine out of this out because by this time this has gone to us and this will have gone to else. So go for by and live by up. Next do too. So I can just return off of this. And as described in this manner the else. That will give me the left side, I have one on this address, it's on this in this close up of this. So what I've seen is advantageously so I have this one thing out for me it's super hard have the site. Let's say we go to index minus index divided by two because this would give me the left half my array getting to this point in this video. All right so they want to have this so what are the differences okay so here's my right side when I was at this when the left side this is good must be done then we're after the form is up palindrome must know the cause to strength over less safe to recycle isn't suddenly the last index therefore diverse max length close to side by side well you wouldn't need this so they are what are the formulas the city let me share my max length so we probably don't need then this isn't supposed to an empty string for max length this semester then overusing this displays the marks. Okay, so... You want to enter the form is that we don't want to return total length anymore to the left we can just return then the independent answer in so then then you can move disk come up this upward. Hello.

Occam's Unicorn: Hello. Yeah, I'm here.

Tea-Smoked Gyro: Okay. So come on this output on circuit.

Occam's Unicorn: Yeah, like you still need to return something here. Right? Line 77.

Tea-Smoked Gyro: So this is after we've gone through the loop. So I mean, no, so we currently talk on displays. So because it's on our n minus stuff. So because now we've gone through the standard output loops, so then we start minus one which one example to see some of the... So I select this font or one of the district and G the g a b? No.

Occam's Unicorn: You can try running it. If you want to check, you can debug by running it, running your functions.

Tea-Smoked Gyro: Okay. So this is done in motion. Don't be shy. Don't be you should have a only an a or b of course the feet the a doesn't call that edge.

Occam's Unicorn: So like see what you're doing here is you're taking the idx and then you're not doing anything right here. So you're just running this kind of like you're not using it here in anywhere. Does that make sense? So you're you're running this function you're getting something from here, but you're not using it here at all. But is that I'm not able to understand you.

Tea-Smoked Gyro: I mean really the way you went into one line?

Occam's Unicorn: The line 53. You're running line 53 and 55. But how are you using poly substring one poly substring two?

Tea-Smoked Gyro: So what do you want to definitely so what are the formulas to see the decision so according to the DB according to the length the eventual length limit closely for them so when I evaluate an eventual entry friends get a map from each of their remarks so we're gonna continue max should be the max length because max length are linked so now max length so from this there is now also check force if the is a max length you know my status is good and because math is gonna work out I'm gonna call it out. Good on it as well I have my with this so I don't need this I don't need this oh max length but because I don't think I needed this so even my local max has done this so what are the left right it goes to my max length because my is it has a length forget the midpoint backward after the midpoint forward so what must miss minus max length divided by two so this gives me backwards then the right to be the index plus do it backwards to getting back on as soon as a program first off okay so how this stuff is a must palindrome? People aren't you is equals to string s for the left to my right. My right inclusive performed because the policy must length the equals to max length.

Occam's Unicorn: Okay, so let's run this.

Tea-Smoked Gyro: One thing to consider doing is use, I think a no brainer. It was green because over here it is non sciences I know. So that's no that's how to do this.

Occam's Unicorn: So you want to return zero here?

Tea-Smoked Gyro: Now I want to present because even it may be insightful to say while loop at going forward as well. Okay a visual we're gonna look now across to this and this because this is another equal decree will start going away when does the equals anymore under the return must start with cause law there will be but it will be out of bounds you should try. Okay this is the the first one I suppose would be I suppose you're on a triple A's...

Occam's Unicorn: So why not? Why don't why don't do return and then start here other than the length itself and then you figure out instead of doing this calculation and then this is messing it up. So, if you return and and start and then you can use to see if that is which one is bigger and then directly get your left and right? Does that make sense?

Tea-Smoked Gyro: So, this will return this. So then...

Occam's Unicorn: You might have to return n minus one and stack plus one right?

Tea-Smoked Gyro: Well if I return n plus one, so now to be removed.

Occam's Unicorn: So, here like whenever you do your loop is going to exit with n plus one and minus one. So you will have to return n minus minus stack plus one right? Oops. Okay, gotcha. Yeah, let and then you can do yeah, left comma. Significant All right. All right, comma, left. Is it right comma, left or left comma, right? Because you're returning and then start... Awesome.

Tea-Smoked Gyro: So, what are these two were produced to be just copy this and the sad truth. So we are this so there is no there will just so one thought to get from this list to get a max length somehow. Okay. So I don't need this right. Yep, I see. Even length. Eventually coming to people learn to right side one minus left side this way. And I say ordinance. Right side. This side.

Occam's Unicorn: Too, right?

Tea-Smoked Gyro: So now, this is true. So what are the different cases. So basically, if the density is given length is good. Yep. I know that the current max length the equals to the entrepreneur from blue to green flash. So we don't need this. Okay, so we can so what else must because to augment this tool? So what are the familiar asking? Max length and max length, right? So for your if you check. So the check is true. Now I'm dealing with my event for us. So we don't probably don't need this, we're not doing this. So the year... Okay, so we're going to get our string right, from the start from our right left side. So one cannot undo even the left side, one right. To my right side one. So one plus one sometimes good enough in the extra. Yep. So else? Well, after that, I guess, check else my check is not true, then I can just do this. So we'll know how to do this. We'll do we want to awesome.

Occam's Unicorn: Awesome. Yep. Good man. I think I have similar feedback to what I had last time. That is you're good at problem solving and coding it up, but I think you should, you should figure out a way where you can communicate in a better way. What I mean is like, you need to write down as much as you can, and explain your thought process in writing down. Whatever you're thinking through your head.

Tea-Smoked Gyro: Okay.

Occam's Unicorn: Yeah, that is you need to still practice on that a lot more. I would say. At the end of the day, it is like, Yeah, one thing is the one thing you need to solve the problem that is for sure, we'll have to do it. Then there is like the other things that are like, Are you clear in your communication? Are you are you if you're not clear, I mean, like not everybody is good at communication. And like, we don't have to take that as a as a bad way. But we can find a way where you can communicate. For your case, you need to find a way or figure out a way where you can communicate better to your interviewer, like writing down whatever you're thinking through, or some some form, like if you can do like, go to drawing more, do the drawing to tell them like what you're thinking through. That that will give you like, even better points than they're not doing that at all. So you try to do this here. But I would do even more like I would write down a lot more. So when you're when you're doing this, I write down the recursion here, what is the recursion that you're going to quickly write down the recursion. And then you're like, quickly write down the pseudocode to tell them what you're thinking or some way like not just use the example that I gave or use some complicated example. Or like if you're expanding from the center, like how are you expanding on the center? Sort of sounds like I would try to explain that. Even more. For me, it was difficult to understand the approach to a little bit. So that's why I asked you to go ahead and code it. But when you're coding, I got that. So if you could avoid that thing. That will be really good reading really great job today. Got much better than last time.

Tea-Smoked Gyro: Thank you. Sure. I mean, that's why I'm practicing as well. Okay, because of the communication because you have been slowed down a couple of times. So those precedents improve on it.

Occam's Unicorn: Yeah. So there is nothing wrong. I'm not saying that you are wrong, but I would say like, Do not try to change who you are trying to communicate better. Like, try to write down things. You can use other media like you have. You have technology to use use technology to communicate. That's what I meant. Okay, awesome, man. Good job today. Well have a good rest of your day and weekend.

Tea-Smoked Gyro: Thank you.

Occam's Unicorn: Bye bye.