Google Coding Interview With An Artificial Intelligence (ChatGPT)

no don't tell me it's doing the left to right and right to left solution what what's up everybody how's it going I am absolutely utterly speechless right now I just finished filming the video that you're about to watch where I gave a Google coding interview much like all the Google coding interviews that I've done on YouTube in the last few years much like all the real Google coding interviews that I've given in real life when I was a software engineer at Google I gave a Google coding interview not to a real person not to a real software engineer but to an artificial intelligence chat GPT which you may have heard of by now it was launched a couple of weeks ago by open AI open AI is a huge artificial intelligence research Hub and Chad GPT is a large language model that basically is like a chatbot artificial intelligence and I'm speechless watch the full video please don't skip any parts watch it all and get ready to get your mind blown I asked Chad GPT questions that uh you know I've asked in real Google coding interviews at Google questions that we have on algo expert my company that helps software Engineers prepare for technical interviews by the way if you're a software engineer check out I'll go expert go to algoexpert.io and use the promo code Clement CLM for discount on the platform speechless enjoy okay so I have no idea what to expect from chat GPT but I've gone ahead and prepared three coding interview questions of increasing difficulty we're going to start with a pretty easy one just to warm up this is the kind of question that I would ask a real Google interviewee just to have them warm up and then we're going to move on to a more difficult one and then if we have time an even more difficult one again I have no idea how Chad GPT is going to perform let's see if it can actually handle even just the easy question so we've got 45 minutes on the clock and let's dive into it I have prepared prompts for chat DPT before I even give it the question just so that it knows what it's doing so here I say you're a software engineer who's interviewing for a software engineering position at Google you're about to take a coding interview with me your interviewer and your goal is to perform as best as you can and to get a strong higher decision from me I really want chat TPT to know that it needs to do very well to impress me within the context of a Google coding interview you're going to be writing code in JavaScript and your question is the following so this is the easy question write a function that takes in a non-empty string and that returns a Boolean representing whether the string is a palindrome a palindrome is defined as a string that's written the same forward and backward note that Single Character strings are palindromes so this is exactly how the question is written on algo expert and let's see how it does so it immediately answers sure here's one way to write a function that checks if a given string is a palindrome is palindrome I think that's actually the name the exact name of the function that we have on algo expert takes in a string she's got a lot of comments we start by getting the length of the string if the length of the string is one it's a single character string so we immediately return true because we know it's palindrome and then we create two variables left and right that we'll use to keep track of the leftmost and the rightmost characters okay so it's creating like two pointers it's going to do a while loop we Loop through the string starting from the left and right ends and moving towards the center if the characters are not equal to each other we return false otherwise we increment the two indices and then we return true so this is literally the optimal solution that I was looking for there are a lot of different ways to check if a string is a palindrome but this is the optimal one because it runs in constant space you're not using any other space ah there's a network error but it was giving us um like examples on how to test it unfortunately I couldn't see them but if you pause the video you'll actually see them which is insane that it was doing that so I'm really impressed by open AI right now and by chat gpk let's see if I ask Chad GPT um can you tell me about uh or can you know what is the space time complexity analysis of this solution too many requests please Slow Down slow down oh it looks like Chad GPT might be going through some technical difficulties okay so we experienced a few technical difficulties there but that wasn't related to chat GPT itself I think it's just the infrastructure behind the language model that was just bugging out too many people are using this at once so I regained the prompt to Chad GPT just to restart it and it's interesting because a couple of times it gave me like two different implementations or two different solutions of this palindrome and this time they were worse they weren't the Optimal Solutions they were solutions that took you know linear space finally I got it to re-give the solution that we were looking at before interestingly though it's a different written solution like before it had a left pointer and a right pointer that kind of converged to the middle here it's a little bit different where it's got just one pointer that increments only to the halfway point of the string and then the it computes the other pointer kind of instantly you know at the same time in this for Loop so very interesting now this still runs in a constant space so it's still one of the Optimal Solutions it's a little bit worse than the other one in the sense that the other one was really well documented like there were comments about each step whereas here's this like a single comment and granted it's a pretty simple algorithm there isn't really much to say about it and then Chad GPT gives us a bunch of test cases that we can use to really test out the solution which is great that's what you would want in a coding interview this is even more test cases than we would ever expect in a coding interview and that's that so now I'm going to ask Chad TPT what I wanted to ask before which is what is the space-time complexity analysis of this solution let's see if it can tell us correctly that this runs in linear time and in constant space and let's see if it can explain that the constant space and all that properly that's what I'm really looking for because that's what we would be looking for in a real Google coding interview the space complexity of the solution is O of one so it knows that it's constant space since the size of the auxiliary space used by the function is constant and independent of the size of the input string very well said the time complexity of the solution is O of n where n is the length of the input string this is because of the function needs to iterate over the characters of the string up to the middle of the string and divided by two iterations and perform constant time operations on each iteration that's so well like explained since the number of iterations is directly proportional to the length of the input string the time complexity is linear we can also see that the solution is optimal in terms of time complexity oh so it's saying that it's optimal because it's not possible to determine whether a string is a palindrome without inspecting all its characters or at least up to the middle of the strings I love the little Nuance the little bit of nuance there any solution that doesn't inspect all the characters of the string would not be able to correctly identify all palindromes and therefore would not be a correct solution I Gotta Give it to chat GPT like this is amazing this is a great explanation very easy to understand very articulate and covers kind of all of the edge cases so here so far like very impressed with the chat GPT to be honest like this feels magical to me like I can't really put into words how crazy this is but granted it was a fairly easy question let's just uh confirm that this is actually correct so let's put this into algo expert so it's called is Palin's Roman algo expert as well I'm just going to copy paste the inside let's rename the parameter to Str and let's run the code to just confirm yep the code passes all the test case so this was correct okay so now let's move on to the second question so this is a tougher question this is actually the question that I failed uh when I went to uh when I interviewed at Lyft when I did a coding interview with Lyft a phone interview way back in the day before I worked at Google uh this is going to be the longest palindromic substring question so maybe I'll continue or I'll just create a new thread let's just create a new thread um or actually we can probably continue here so let's continue I'm just going to not repeat you're a software engineer I'm just going to say okay let's move on to a more difficult question you're still writing in JavaScript your question is the following okay write a function that given a string returns its longest palindromic substring a palindrome is defined as a string that's written the same forward and backwards same thing note that Single Character strings are palindromes so here this solution can be solved fairly easily in N Cube time n to the power of three you do two four loops and then you check that every substring is a palindrome or whether or not it's a palindrome or it can be solved optimally in O of N squared time so let's see here's a possible solution in JavaScript okay special case when the string has length less than one or less than or equal to one so then iterates through uh the um string once check for pound drones with odd length check for pound drones with even length Okay so it's using a helper method I think this is the optimal solution let's see what it does for the um helper method Returns the longest palindrome at a given Center Point yep you basically expand from a center point and um yeah you this is an O of N squared algorithm this is insane so it figured out immediately that you can do this in O of N squared like this is something that I couldn't figure out in my first interview with Lyft one of my very first uh coding interviews back in the day unbelievable and it even knows that with a solution you can't just like naively expand once at every character you have to expand twice for oh we got a network error no not a network error again but yeah you can't expand uh only once you have to expand twice because uh you can have you have to check odd length palindromes and even length palindromes so we're experiencing technical difficulties again I'm gonna just restart a new thread with Chad GPT try to get to the same point and then ask about the complexity analysis so it's redoing a similar solution or basically The Identical solution but it's naming things a little bit differently it's so interesting how like this is not just you know simple copy pasta every time no it's it's coming up with the algorithm every time like before it wasn't called expand around Center and by the way expand around Center is a very semantically accurate name for what is happening here like I said you are iterating through every character and then expanding from the center for every one of them um so absolutely incredible oh my God another network error my god um but it's just incredible that he can do this it's incredible that it can do this let's see if I can get it to spit out the full thing and then ask the time complexity analysis uh without a network error so right now I just paused the screen on the end of another solution that it gave me that was yet again a little bit different but ultimately the same like idea of expanding at the center you know as you iterate through the entire string I paused because I got a network error right after again but interestingly enough here it started telling me about the time complexity and you can see that it said N squared I wish I could see the full explanation but I'm just not going to bother right now clearly like there's there aren't enough infra resources to support this right now but that's just mind-blowing it knows that it's an unsquared algorithm and again interestingly like every implementation of this question has been a little bit different like the the way it writes the code like at the very beginning it checked you know just a string of length one or less than one in a single if check then in the second uh you know attempt it checked a string of length zero so like an empty string or just no string at all like if you pass undefined to the function then it checked a string of length one and for both of those these were one line if sex in this version of the solution I think that there were they were like multi-line if checks you know if Open Bracket enter new line you know return which is interesting how it writes different code every time I don't know I'm mind blown this like all three solutions that it gave so far for this question were the optimal solution it found them basically instantly it documented its code clearly it knew the time complexity and it would have explained it to me very well I think seeing as how it explained the is palindrome time complexity and space complexity super well I'm gonna try running this one more time and quickly copy pasting the code that it spits out to see if it actually passes all the test cases on algo expert so I'll be right back okay so wait I am absolutely mind blown I've just rerun The Prompt twice with Chad TPT and he gave me two brand new completely different solutions the first one I'll pause the screen like halfway through it I got another network error unfortunately but this was a super interesting solution that used dynamic programming it's actually the basis of a very hard question that we have on algo expert called palindromic Min Cuts or minimum cuts to create palindromes in a string it's like a really difficult question that I was considering giving sad GPT and it basically found like the solution to that question where you you pre-compute everything in a two-dimensional dynamic programming array it did that there which is just like mind-blowing and I had never even thought of that solution for the longest pound zombie question but then it got a network error and now I got it to give me yet another different solution and here I didn't get a network error and this one is the less optimal solution so this one is the one where you you do two iterations through the string and then you check basically each substring whether it's a palindrome and that's an o n operation but it correctly tells me this solution has a Time complexity of of n cubed since the outer loop runs in oven time inner loop uh O then squared because it calls this pound Zone but it knows this is not the most efficient solution but it's simple and easy to understand that is so good like in a real Google coding interview I would love for the interviewer to tell me this to begin with so let's try to actually just copy paste this and see if that really works um in algo expert so I'll go to longest palindromic substring we're gonna copy all of this here and I'm just going to rename string to S because it named it s for this code and let's run yes it passes every test case let's see if we can continue here without a network error what if I say um okay great what about a more optimal optimal solution let's see if it can give me a more optimal solution okay we got a network error one more try okay I was able to get the the great solution with the expand around middle thing I copied the code let me put it in algo expert let's see we copy the code here put it here and looks like here it named it a string Str okay so let me just delete the first line let's run the code and it passes all the test cases oh my god look and we can compare this to the solution on algo expert like if the solution get longest pound drum from here expand around middle and you know you've got odd odd even even and then you you know you select the longest and the expansion is like great it's exactly kind of what we do I guess here it takes the substring whereas we return the two indices But ultimately it's the same thing um and yeah this is just absolutely insane like I'm just mind blown mind blown and it it puts comments where you would want to document your code like how let's see if it got okay it got a network error so we didn't see the time complexity analysis but at this point like I believe that it would get this right we saw earlier it said M squared for a split second so let's move on to the final question this is gonna be a hard question so here I'm really curious to see how it does this is a question that I used to ask at Google as an interviewer this was one of my go-to questions I categorize it as hard we have it as hard on algo expert the reason I'm very curious is that this is a pretty difficult question to explain like it's fairly simple input wise just one input array but to explain it is pretty difficult so let's see so let me copy paste it and read it to all of you so we again tell Chad GPT that it's a software engineer interviewing a Google here's the question imagine that you're a teacher who just created the you have a list of student scores that's your input array on the final exam in some particular order so the order matters but it's not necessarily sorted and you want to reward your students you decide to do so fairly by giving them arbitrary rewards following two rules okay so you see pretty complicated number one all students must receive at least one reward number two any given student must receive strictly more rewards than an adjacent student meaning a student to the left or to the right that has a lower score and must receive strictly fewer rewards than an adjacent student with a higher score write a function that takes in a list of scores and Returns the minimum number of rewards that you must give out to students to satisfy the two rules so again this is pretty tricky you kind of have to give an example otherwise it's hard for the candidate to really understand what's going on by the way you can assume that all students have different scores the scores are all unique so for example you could be given this list of scores so here this list that I'm highlighting right eight four one three six seven nine five user scores the minimum number of rewards that you would have to give out to the students to the to satisfy the two rules would be 25 and you would give out the following Rewards four three two one so you see here you've got eight four two one as scores so that means eight needs to get more rewards than four which needs to get more rewards than two which needs to get more rewards than one to four three two one and then two three four five because three six seven nine they're kind of incrementing so they need progressively more rewards and then nine is greater than the final score five so you can give one to the final score five because you wanna minimize the total rewards that you're giving and so if you add up all these numbers you get 25. so pretty complicated question it's got a very elegant solution in linear time where you do two Loops one from left to right one from right to left let's see what happens okay I'm not gonna be like disappointed it's sadly okay it immediately found something no there's no way it figures this out I was gonna say I'm not gonna be disappointed if it doesn't figure this out because this is like very complicated no don't tell me it's doing the left to right and right to left solution what what is doing the optimal solution that I told you about no no no way no way please no network error please no network error please no network error okay let me quickly copy the code just so we can try it but I know this is correct I've seen that I've done this question so many times at Google very few people got this elegant of a solution like very few and usually it takes like this is a single question that I give in a 45 minute interview oh no and it was walking me through the steps it was walking me through an actual desk case let okay let's paste the code some Min Rewards reward students let's call it Min rewards and delete the initial function no way no way that was a difficult question both to like grok to understand and this is a very difficult algorithm to come up with like it's a it's non-trivial like look you iterate once from left to right and you get the best rewards from left to right but then you go back from right to left and you take like here yeah math.max it's exactly look it's our third solution that we have on algo expert it's our third solution runs an event time and O then space it's exactly that solution except it's better documented because we don't document it in the code on algo expert and then there's another solution that runs in the same space-time complexity but it's much more complicated this is the solution that most candidates like converge towards after you know 30 minutes the solution I'm not going to walk you through it but you can tell just from the left side of the screen here it's much more complicated um there's much more involved you know it's not as like elegant and clever and then there's another solution that's less optimal and you know N squared time but how how that's incredible I genuinely I genuinely thought that it was like gonna completely flip out here and not know how to solve this question like I thought that it was going to misunderstand The Prompt um I I can't be the only one who's speechless right now I can't be the only one who's speechless right now right oh first try not even like no hesitation and I know that when it takes a while to come up with the answer I think it's because of like the infra and how there's so many people using chat GPT right now but here it didn't even do that like it just spat it out instantly okay this is terrifying this is scary this is scary this is a little bit scary at this point I know that it would have given me the correct time complexity analysis like if it knows the correct time complexion analysis for the palindrome stuff with the DP dynamic programming all that like it would have known it here it was gonna walk me through like a test case and like step by step who's gonna walk me through that and it knows to do that see like I told it that it needs to do like a good Google coding interview get a strong hire it knows to document its code it knows to handle edge cases it knows to tell me how it's going to test its code the only thing that I can reproach it is that it doesn't ask clarifying questions that's the only thing that I've noticed maybe that's because I give it like most of the data that it needs because I'm copy pasting from algo expert where we we always provide as much information as we can in the prompt because this is not like a live interview but also I think just Chad DPT like it doesn't wanna it doesn't wanna like ask you questions it doesn't want to interact with you in that way so I can't really blame it for that but I I opened up um the the rubric that we usually use uh for for Google coding interviews at Google and we have it on on algo expert for mock interviews so if I had to grade GPT on algorithms I would have to give four the best score right candidate came up with one or multiple optimal algorithms to solve the question no not the question the three question and it came up with different solutions with little to no help from the interviewer that's true and it demonstrated a clear Mastery of algorithms and data structures unequivocally yes like I have to give a four here I can't not give a four when coding um candidate effortlessly transcribed an algorithm into working and readable code candidate abstracted repeated logic into helper methods and named variables descriptively and used idiomatic language syntax again here I have to give it a four like yes there was I think one solution or maybe two in the longest palindrome thing where you know it named variables like L and R but that was not even on purpose like I think it was it already was passing in left and right so it had to kind of come up with new names where it just named an array like DP okay that wasn't great but most of the solution is really good like you know expand from Center um reward students uh you know odd length palindrome the longest pound drone even length pound drum and like the JavaScript code was great it was using es6 syntax oh I I can't not give it a four I have to give it a four communication this is where it's a tiny bit tricky because candidate communicated clearly and Ambiguously throughout the interviewer or throughout the interview candidate voice to their thought process explain trade-offs between approaches and it was overall easy to follow I mean I kind of have to give it a four what's three three candidate communicated well throughout most of the interviewer interview I got candidate may have been prompted to voice their thought process and to better explain their approach at times but overall did so clearly no I don't even think I needed to ask it like it was documented code all the time it was telling me like why the time complexity was one way why the space complexity was one way it preemptively told me but this is not the most efficient solution but it's very clear and understandable it's very readable I gotta give it a four I gotta give it a four and then problem solving let's see what four is Canada approached the problem in a very logical and rigorous manner candidate ask clarifying questions divided the problem into logical sub problems and navigated it effortlessly so that's probably the one category where like it's it's hard to judge that that's the one category where it's hard to judge based on the code and the way it was laid out and the way it was documented that does seem very logical and rigorous but on the other hand like like I said it didn't ask clarifying questions but that's maybe because of the way it was designed but it's hard to like tell whether it was just copy pasting things that it already knew somehow but no because we had to run the same question multiple times and it came up with different solutions with different like code implementations different syntax different variable names so no like I have to give it a four here too and it did navigate the interview effortlessly this is insane I don't think I've ever given four fours at Google when I was at Google or maybe like once and when I gave four fours at Google it wasn't like this effortless it was maybe because I gave that last question and rewards as the only question in the interview and the candidate ended up getting to that third solution in the 45 minutes and was like very good maybe they got a hint or two here it went through three questions and it's not even been 45 minutes I'm pretty sure that it's been like like 20 minutes total not even it's probably been less because I'm just talking I'm like narrating this so yeah I have to give it a strong hire I would fight to get this candidate hired like if I didn't know that this was an AI if I thought that this was someone you know across another screen from me who just couldn't speak to me they were just typing I would fight to get this candidate hired right now they performed exceptionally well and they should be hired this is insane I'm mind blown and yeah I I I'm very curious to know if you you are all mind blown like I am um obviously like you know if I if I put my sort of rational hat on and I don't get drunk with cold water I understand that you know Chad GPT might be really good at this particular type of sort of situation problem but then it might you know fail at other things I've seen online people you know prompted things where it gets them wronged and it it messes up but still like this is this is just incredible it's incredible and um yeah especially since like Google coding interviews I know that they're very controversial some people hate them some people love them blah blah whether you like them or not they do have a lot of Merit like they do test certain things like these four attributes quite well and they're particularly good at like eliminating false positives in other words they might uh you know you might lose very good candidates who mess up but you'll rarely get bad candidates who pass these kinds of interviews and so like Chad TPT just like nailed this interview I don't know what to say I don't know what to say I'm speechless I hope that you all enjoyed this video let me know in the comments below if you're as speechless as I am not a GPD um yeah if you want to become as good as chat GPT you better go on algo expert go to algo expert Idaho news promo code clam celem for a discount on the platform we also released voxan expert recently so check it out if you want to learn blockchain development machine learning expert ml expert if you want to learn machine learning become you know the developer behind strategy BT and uh don't forget to smash the like button if you enjoy the video subscribe to the channel if you haven't already follow me on LinkedIn Twitter if you enjoy story short form written content Instagram if you like pictures and I will see you in the next video

Channel: Clément Mihailescu

Views: 226,455

Keywords: google coding interview, google coding interview questions, google coding interview preparation, coding interview google, coding interview, coding interview questions and answers, mock coding interview, technical interview with a google engineer, algorithm interview questions, real coding interview, google software engineer interview, google coding interview with an artificial intelligence, google coding interview with an AI, google coding interview with chatgpt, chatgpt

Id: gOf2SQVMUL0

Length: 31min 5sec (1865 seconds)

Published: Tue Dec 13 2022