Google Coding Interview With A Competitive Programmer

what's up everybody how's it goin in this video I paired up with my friend Camille who goes by the name Erik toh online and we decided to do a coding interview where I interviewed him over Google Hangouts on a Google Doc now the cool thing about this is that Erik toe or Camille is a competitive programmer he is super good at the types of problems that coding interviews test you on he was I think second place at the Google Code Jam competition back in 2018 he has his own YouTube channel which I'll put a link to in the description in comments below and you might have even seen him in a video interview of him on YouTube that a month ago and got a ton of views so I think this video is gonna be really insightful because you'll be able to see how someone like him who's so good at coding interview problems approaches and solves a problem in real time under pressure I want to add but this is exactly the type of coding interview that you could expect to get at a big tech company like Google I interviewed dozens of candidates at Google and this is really how I conduct interviews minus the fact that here I know Camille so maybe there were a few moments where you know we exchanged a little bit of banter that I wouldn't do otherwise with a real candidate but it really is how I conduct interviews so I think you'll find it valuable on top of that the question here is a very hard one it's actually a question that we have on algo expert by the way if you're preparing for coding interviews check out algo expert audio my company uses the promo code cleanse elem for a discount on the platform but so it'll be really interesting for you to see how Camille solved this problem in a way that I had actually never seen before at the end of the video we have a short debrief session where we talked about how the interview went and on top of that I just filmed a very small commentary that I added in the middle of the interview just to kind of share my thoughts about how he did during the first half of the interview with that enjoy the video okay so Camille I just started the 45-minute timer and we're gonna dive right into the coding interview question so I want you to imagine an XY coordinate plane right you've got the x-axis you've got the y-axis and you've got coordinates on the plane does that make sense so far did okay and I can handle two dimensions you can edit you can handle two dimensions so I we've we've like 11 need to be comes right up until 10 it's okay but at 11 it becomes difficult exactly so I'm gonna give you a list of XY coordinates to Cartesian coordinate coordinates on the plane and I want you to write a function that is gonna tell me how many rectangles are formed on the plane by these coordinates so for instance if I give you this you see how I copy/paste it like six dots right you can imagine that the the XY axes are maybe like here at the the left side that's the y axis and then the the x axis it doesn't really matter and you could imagine that here there are three rectangles that are formed right there's one that's sort of like this first square there are two squares the left one the right one and there is the big rectangle the big rectangle exactly so I want you to write a function that takes in these points and that tells me how many rectangles there are there are two little caveats first of all a rectangle has to have four corners on the on the plane to be considered a rectangle so for instance if I delete this one then you lose quite a see I think you you lose two of the rectangles and and then the second thing is for now we're just gonna deal with rectangles that are parallel to the X and Y axis yes so there this was going to me right question what would happen if I added around here and now would that this four points would they create a correct angle that I should count so friendly I guess for now we don't for now we don't and now we don't okay well I don't know if you're aware of that but I'm quite good in computational geometry so it's up to you if you want to leave this problem as it is let's leave the problem as it is and we'll see if we can improve it soon that's right okay so we want you want to count rectangles made of four farce of points from here they should be parallel to access I guess the professional work for that is like eyes optic if there is a word for that I don't remem yeah there is one word and it's something with eye anyway I would say that we're looking for such quadruples X I X Y then the other point has the same carrier decks but different why does some different X Y X 2 y 2 yes and now I I will also make my screen bigger and we are looking for far of soft points like that where accent x2 are different because otherwise we would count the degenerated rectangles of like zero area yeah and Y is not y2 and this is our goal what makes sense is to iterate for sure otherwise one point so I'm not yet sure what I'm going to do fully but some pseudocode would be that I iterate over one point in points and this will be my accent Y right if I was able for example to iterate over the second point with the same X in brute force way it would be P let's say above in point as well if px is equal P above dot X and not to over count something let's make this P above to be indeed above so y-coordinate will be bigger if that then we continue and what I found is a pair of points that is one is above each other like this path right and I need to find matching pair that is on the same level if here I would just increase some counter by one I would count like vertical lines that can be created and instead here I will say that what matters our variables P Y and B above y also I hope that writing in C++ like count is fine let's start with Anya we have P Y and P up of Y I want to count the number of other pairs that produce the same pair my idea is to here increase the count for a pair P Y P above Y where this is say a map or a hash map for now in C++ I would start with a head I'm up from pair to hint right called it count this is count our wipers like this way this way and this way coordinated right kind of count vertical lines this would give me logarithm in complexity what I could also do is put a hash map here an unordered map and then to make it work in C++ I would need to define some hash value of a map I think it isn't there by default at least in C++ but for now it isn't important for the logic this way I count that and maybe just before I would say unsurfaced equal count of upside so not to repeat something I will assuming that coordinates are in this pair of Y I will make per divide the above why let's not make it ugly and here increase the answer by count of that and increase the count of despair so babies way first this was sorry to cut you off just to just to make sure that I'm following correctly basically you are iterating through all the points here then for all the other points they're looking for points that are directly above it your your if statement right and here you're saying okay I've got one vertical line and which is this pair and then you're gonna say we're gonna count all the other vertical lines that are exactly on the same level yeah and thanks to the fact that I do it in this order at this moment for line with a surplus equal I up to the answer the number of pairs that the vertical lines that were already processed and then only I increase the count by one so if it happens that first I some pair appears then for a moment discount is 0 so it is answer plus equal to 0 only then I increase the count by one and if later on the left or right doesn't matter for now let's say this will be used the account will be I mean count is already one and then I get answer plus equal one when I get to this second vertical like that I'm not sure about this whoever maybe I double count like when I'm on left line I count the right one and the other way but then I think this is disorder disorder prevents from that why does the order whenever I meet the first pair only then I increase the count by one and later no matter if the other Paris on the left or right I will increase the answer by one right I see are you when you are when you are look when you're I guess we should we should explore what this make pair function looks like right yeah it's just at Apple because this is orders I didn't then we should oh I see I see Isis is also correct just I could paste that here and there and that's it it's just not to repeat code right okay okay okay so okay so key so keep going keep going from here then yeah and I think this way those two for loops together they iterate over all the pairs of this way I check if I have a vertical line so here if I wanted to print those that were here this thing could print all the vertical lines but I don't want to print I want to count pairs of those vertical lines that are on the same level I see vertical line is defined by pair Y and I want to count bars that are sine like some alternative for that would be just to do this like not to increase answer here and later if I know that there are say 10 pairs on the same level I could use some simple math formula to say what is the number of rectangles from that I think it would be time to stew which is like 10 times 9/2 right I find this one to be more elegant and here answer all right you do have the answer from here now I now I understand what you're doing at first for some reason I thought the make pair you were right that was a function and forgive my c++ I thought that was a function you were kind of going through and counting all the pairs now I understand so wait this walked me through them this example because because yes you're right because of the ordering of when you increment the count it works because you are basically you're only ever going to find a rectangle when you are on the right side of that rectangle right exactly assuming that I go four points from left to right and the cool thing is that thanks to this order like I don't actually care left or right I count it when I meet the latter of two vertical lines which is in whichever order I go right like if I went through a set of numbers say 5 7 5 2 4 2 7 5 and I wanted to count pairs of equal numbers I could go do that from left to right and for every like this 5 add to the answer the number of already 5s in the set but if I did that in some scrambled order like 5 to 7 5 5 and so on it would be the same thing all right and indeed let's go through the example it it is sometimes dangerous but for now let's say that the order is like that but my color does third points and I claimed that the order does it matter if I do it like that and first B is 1 then the only actually PF non-p above will be valid here because I'm looking at point that is above but you would never get an A you skipped the F statement would never never pass exactly this would be never be satisfied but when P is 2 when this is the second point on your drawing then here 1 will be a valid point above ya the x-coordinate is same py so second point is below why I assume that y-coordinate grows up so this is true then I go here we create a pair of wait coordinates that are like this y and then that way yeah and first your map first has just zeros as values yet so this does nothing and in some languages I would maybe need to put explicitly 0 here but the purpose it isn't important that's final and then I say there is a vertical line like that if you ever again meet vertical line that is with exactly the same word y above and below then you have a rectangle from that right ok so this is what happened the count of this pair of wise is 1 and what happens later when P is 4 then P above us free again will satisfy the condition before that if P is free nothing is above yet so Michael shouldn't find anything here yep yeah the work done we do the pair Y is the same Paris before because the Y creates our side yeah so this will do answer plus equal 1 and then we increase count even more so how it becomes 2 yet was one before I think there is that's now County stir and eventually when we are at five not five six five nothing happens again this one is five exactly so five is skipped and four six and five the same pair of wise is their answer is plus equal additional two and later count would be increased even more to free yeah but I don't care about it anymore because that's it and the answer is sick guys free one plus two as we expected okay so if I wanted to be more careful with that I would just check on so what happens in a different order I guess yeah that's what I was gonna ask does this break if your thing is the thing is I never compare x coordinate like if I say that this is one two three and four my count like the first pair that will be encountered will be this one and two just in different order yeah but in the the below is 1 this one is 2 but what happens here with answer and count is the same thing nothing is different at all the y coordinate our design here I do not compare X never so I don't distinguish and it just about the order and a pair one two I will increase the count by one for free for later the answer will be increased by one thanks to them yeah yeah yeah so in sum I don't care what order I go for all the vertical lines and also for each new vertical line I need the number of previous vertical lines that were at the same level above and below right so I'm quite confident now with this solution and the complexity will be an x + 4 because there are two for loops if n is the number of points x inside pessimistically every time i can go inside the safe I guess it's possible if everything is on one vertical line and here is a map that in C++ is lock so this thing is of N squared times log of N and well log of n square but this is in math the same as log of n it's all a constant like two goes before the law guard the market that is comparative law Gert yeah okay Lagarde miss coming from C++ map well I think some other languages already have that by default constant yes about just changing this to unordered map and writing some small piece of code to to handle pairs there xe+ persisted about it sir yeah yeah we don't we don't need time to get into that I and here we go i I have n square solution for now I have no idea how I would speed this up if I need or should I think about it I'm not sure though I don't think we can we need to go to that I'm not sure that you could mainly because you ultimately like there's a worst case where the rectangles are let's say all on the same line and any any ops or sorry not the rectangles all the points are all in the same line and any optimization that you might try to do you would end up having to iterate through every point and for every point iterating through every other point I don't think that you could do better than N squared let's not dive into that as far as space complexity it's also so o of and I think here right because you would have what do I put I have a map the with those percents specifically of all the purse will be different so for even a bunch of n random points I have an square so write N squared because you have very few times okay so I think there there might be a way to improve the space we actually have a solution on on algo expert for this problem with oath and space but I don't think that that's super interesting here I'm not too concerned about that we can talk about that maybe later what I do want to explore since we do have time if you still have like 25 minutes you have 27 minutes super quick pause I just want to share my thoughts on the first half of the interview as you saw Camille did very well as far as the coding and algorithm design part of the interview is concerned he came up with a solution that was very good he did it very fast he was able to actually code it out to really fantastic job on his part from that point of view the one little piece of constructive criticism that I would give here is that he was so good at this that he kind of forgot to communicate a little bit more his thought process since I had never seen the solution that he actually came up with I kind of got lost in the middle you kind of saw that when when I wasn't quite following what he was saying and I had to kind of catch up to him and so here I think that he just could have communicated a tiny bit more voiced his thought process a tiny bit more but otherwise he did a fantastic job and now as you'll see during the second half of the interview this is where I really tried to challenge him with something much harder and this is something that interviewers will often do when they're dealing with such a strong candidate they'll give them a problem or a tougher variation of the current problem that they don't even expect the candidate to find a solution to they just kind of want to see how does this candidate who's obviously really good deal with a complex problem something that they're probably not going to be able to solve and so this is what you're about to see and going I want to explore what we said at the beginning of what if now we have rectangles that are that can be diagonal so something like this let's put you know seven eight nine whoops and here like you pointed out there's a rectangle there's for example this one yeah I'll put it in reverse something that is smart tilted that isn't very irregular so that the viewers can understand what we mean yes exactly what you said this rectangle in green here is sort of diagonal it's not horizontal or vertical or whatever the word is and how do you compute that so this is part that maybe normally I would need to think about but I'm good in computational geometry so I know what are like the vectors and cross products that and the thing is that then like before we could define this way when I've went four points create a rectangle now we need to modify that quite a lot I will just move the first solution below to work here with example more that if let's say for a moment that the first point of a rectangle is zero zero yeah we can later put something more complicated here and then if the other is X Y and some third point is x2 y2 then if if those two are neighbors of zero zero then I want a right angle between them the 90 degrees right and there is a formula for that that is cross product it will be x times y 2 is equal Y times X 2 which basically is also possible to figure out without knowing the terms because I remember that I used to like when I needed something like that and I didn't know the formula I would just draw an example I have such a rectangle a right angle and if you put like point five one then you try to match which point would create indeed a right angle and then you see that like that for example the 1 5 so this is that point and minus 5 1 those two would create a right angle with 0 0 and from that you can figure out what needs to be called all right if you put it this way the distance doesn't matter so that's one part now I'm already able with formula to count the right triangles I need triangles that have the right angle right so it one half of the right angle yeah what do we need I think this pink allows me for first of two the fork solution where I would iterate over all the first of points and I would check some formulas so I need to check the right angles plus some other thing or maybe I yeah if I check all the far angles then that's it because something that has four sides and four right angles I think is a rectangle yeah I wanted to say that I also checked some distances but it doesn't sound necessary and so that that would be just for loop polit I found a point B for loop point C for the D if and here a lot of ifs for those for this stuff Plus this doesn't have to be zero zero band then I can shift the drawing to put the point in zero zero okay subtract things or just think about the vectors not about points about vectors that decides for now do I go in the correct direction so it's interesting because I've actually never done I've not really never solved this version of the problem I just had it in the back of my mind as a way to like making this problem much more difficult that I wanted to explore with you but I don't know how to solve this problem so I'm finding it interesting that you're going with this approach in my mind I was thinking maybe we could solve it by by figuring out like that you need you need the same like rise over run right you need the same what's it what's the name of that slope slope yeah I haven't done math and so on in the same slope on off on like the two parallel sides and you know so I might I might want to try that in a moment because I don't know where I'm going by the way if if I got something very hard and in that I would be stressed then also I would take that like five minutes of thinking before jumping into like going for everything right even with the first version I tried to just not make a pause in the instead to just dive into it I thought that yeah I will likely get a good complexity here I'm are like blind and we'll see where it goes so I can think later about like what to put here but I am able to check for the right angle if you ask me later I will call some fork or something for that it uses this formula right but then like one technique I like for speeding up on the middle solution if you have a lot of Phillips is to just remove the last for loop and the thing is if you have three points and they create a right angle you should know where the fourth point is yeah that's true and like because if you decide they are a ABCD in this order then vector a B let's call let's mark it this way is equal to vector side D see the two sides are parallel and equal so vectors are the same but even and even like just to put it even in simpler terms without even vectors like if you have three points then you can deduce the x and y coordinate of the fourth point based on those three points right yeah yeah we've some like computation with coordinates yeah so here that in other words is B minus a is d minus C so I get the is C plus B minus a what means that point D is C dot X plus B dot X minus radio docks come out the same for Y and this this must be point D and to check if such a point exists I can use a hash map hash that actually it's just to check if something exists at that position yeah of course one more thing to keep in mind no I got rid of that one more thing to keep in mind just like with previous solution is not to over count something like I don't want to count the same rectangle four times or if I understand that I do at the end I can divide the answer before printing by far in when counting is done not on whiteboard but with like computer then I would usually implement something see the answer and if it's the big / whatever I need to / right here after coding some code for this I would just analyze it to see if I overcome then I will handle like just like with previous problems right and we have now n cube but to go to go even faster yeah the question is like is there way to make again I think we established in the first solution that I don't think there's a way to beat N squared I don't think you can beat polynomial time for for this problem but can we get that and Q down to N squared with the diagonal diagonal expansion thing I I have some ideas one is what you set about slope well it wasn't my idea but this is something let's call it idea number three slope and Sam tomorrow our first one is from points a and B figure out where C should be so get rid also of this for loop right if you have n to be here then C should be somewhere on this line but it would be hard like I cannot iterate over that C and the thing is the thing is here in the example that we have we're dealing with actually a very edge case example where I would say yes yes it can be tilted tomorrow we know that yes so that's something second thing is this is something that I would I would never come up without saying first that we can consider the middle point of segment say I see yeah this will be a crazy idea but it might just work the the thing is if I see is diagonal of this rectangle then I can iterate over all the pairs of points consider hey maybe this is diagonal of a rectangle what are what are the properties of diagonals of rectangles that are interesting you they always I think is they think is that two diagonals intersect exactly in the middle they do right yeah I it is possible that what I will get from this approach from this idea is not a rectangle but let's I ramp rhombus I don't know words in English right because there are other shapes where the there are other shapes worth the two diagonals intersect in the middle that are not rectangles right I would need to think now we're getting is alike but there might be a way to like find these these I'm gonna call them hacky solutions that rely on the underlying like math principles but I wonder if like I wonder it's an idea number one or number three that's sort of more accessible in a way I feel like there's two is very random and you cannot just get that by thinking I just remembered that I saw some problem that uses this right maybe even this problem to be honest because some of them are similar so let's investigate one or three I think one in three are actually kind of similar right it's the idea that you you've got the first two points maybe you use the fact that they have a given slope how do you find C and then D from there yeah okay so I I will try a because I will try the first one because it was my idea maybe I can manage to solve this problem later I can try slope so four points a and B figure out where it's you should be I I'm not able to iterate over C be like then I have iteration of our three points maybe tomorrow Isis in some very magic way I don't think so instead I would I would write down some thoughts made so let me denote vector V but denote from A to B then that V prime denote vector of direction direction perpendicular to V so from this direction I would get this one and I know C must be somewhere around there a monk points C that are on Direction V Prime from a yes I so from a I want to go along that direction like not necessarily within the same distance V prime is just like perpendicular direction yeah necessarily within some distance I want to count those that have a matching point D such that C DS is so if from A to B I went let's say two units up then also from that C that is somewhere else I want to go to means up yeah but to be honest to be honest Camille I think here I think you just you just did it the key is the perpendicular if you can find the perpendicular ones in like constant time or something you've got your solution because once you find all the points C on the perpendicular vector then D is just a matter of storing all the points in a hashmap and finding the D that has the correct XY coordinates right that fourth point worried about very strange tests where maybe like I think I am able to find quickly those C but if I iterate over those to see what should be the matching D I think then the complexities and again and cubed let's try anyway need that so I will say that too much to sit to find those see what I do is for every point a in points point a in points for point c in points and now this will be let's call it deer map from from at Apple that contains a and get vector of from A to C for a moment let's say plus plus just to count all right and this get vector it should not only compute the vector like from A to C but also I care about Direction not about distance there is a way to handle that like let's say I create a vector function yeah don't point A to point C then X is CX minus I X Y we see Y minus y this is the vector but I I don't want to distinguish vector 1 1 from vector 1010 I care about direction right don't think here would be to compute the angle but that's always a bad idea because of precision issue stuff like that but in short it's good to take its to normalize this way but don't you want to distinguish you do want to distinguish them no wait the thing is I will finish that in one second okay there's a return point made of x over G and Phi over G and this is not working for zeroes or negative further the thing is I I will use it for that for a I want to find all the points see that are in this direction let's say in Direction one one but also point that is 10 10 from here is okay I care about direction that the example would be that side that B is minus 1 1 is 0 0 so now I'm looking for all the points that are like the the valid point C are like 5 5 13 13 and so on my house will create this is left up this is right up I want to find all of those and if I don't do that then in a map I would start only a point 1 1 like I want to those are fine too so after I do my think we've got vector I will move the whole thing to another page to have it on me like in one place yeah after I have this deer map link when I iterate over a litter it over B then I can do what I wrote down above that that V prime denote a vector Direction perpendicular to V so I do that with some formulas the right the prime is perpendicular of from A to B something and then I read deer map actually perpendicular of get vector Phi B so get vector finds me a normalized vector between a and B perpendicular rotated by 90 degrees and then here use deer map from a with this direction right because that will now find all those that are here yeah for now I'm not even close to counting rectangles because I cannot iterate over elements here because then it's a field for first for loop well it depends though cuz what if you you can pre-compute a the for a B right can't you can pre-compute all of the lines that go from eight you could recompute all the vectors a B yeah I can in N squared time but then you have you pre compute them in N squared time oh but wait you then do you have and no you don't have N squared whines then wait like I I can find them in n square and now I need to I think modify in some way the deer map in some way feeling that if you have you you can pre-compute all the lines that go from a point in the bottom left to the upper right in N squared time right you can pre-compute all the a B's in go then squared and so then for every a be right for every a B and there they're there as many a B's or fewer than the number of points so they're there at most o of n a B's for every a B you can do your your get vector a B your perpendicular thing right which is gonna be also o then so so for a B I'm writing really pseudocode for a B do get perp and this is also it's like n n n wines a B that dune action of oh then so n wines a B is it like there can be N squared force instantly right well no because you would you would have at most n lines like you would have because we're only dealing with wines at least maybe I missed that thing from you but in my mind you only deal with lines that go from a bottom left point to an upper right point I mean we can deal just with those where the both x-coordinate increases and y-coordinate increases yeah not necessarily 45 degrees but then still pessimistic leader and square of them just if you put a bunch of lines that go round along the line y is equal x oh yes and the words came in the worst case there and squared yes yes in the worst case so my guess for now is kind of maybe intuition is that yeah I want to use that but also to consider for ins D in some way so the deer map is not just this from I think that this thing now would count the number of triangles with right angle and if I want this vein and if I want the number of rectangles so how so to consider the v-belt iterating over C because I'm afraid that would be an Q unless maybe there is some amortized complexity going on then when I create your map so from A to C I need to add this moment curves in some way about points D that are perpendicular to AC that is overwhelming well D do you do you need to do you need to do that or can't you just at the end at that at that point just decide based on coordinates you've collected where that point D would be the thing is that here right now my dear map only stores the count rare in an emergency I could hear inside this dot append or push back in C++ C then here I would be able to iterate over matching point C but then and Q yeah okay one more idea that it's kind of like related to this normalization thing it's not maybe it's better to think for a moment about that previous count the one that solves the easier this is your version of a problem so iterate over all the pairs say a B yeah and let's say I want to achieve the same thing though just increase the counter for those pairs there I had the counter for pair y coordinate one y coordinate right just here it's not a pair of Y coordinates it's a vector let's say that that says it from A to B you go two up and the to two to the right and five up yeah you want to find marching with those but also at the same the same like not only matching vector because then if a B and C the are same but in some different positions you don't get a rectangle weight so if you go with that approach if you go with your program like the lines right what are the there are only two conditions that you need like the vector comes down to you need matching lines of the same slope and you need matching lines of the same length right sounds like I will get I will get what is called order of the legwork in Pawleys let go good that parallelogram more sighted think that has like both pairs of sides are parallel to each other yeah you will get parallelograms as he tilted rectangle but I think I have a solution here so I will type the like two sentences and then work with that okay by the way just as a side note we only have two minutes left so in the effort okay keeping this you know easy for every so for every vector a B I want to normalize it in some way so I want to increase the counter of the vector V and where Point a is with respect to perpendicular humvee I will explain that in a moment and that normalize think what it should do it should the pseudo-code of that is let's say while a X is greater than 0 a - equal vector I think that does the job and now what I hope it does is the zone Lyle function yeah so this is a function that and this is a pseudo code for that but also I can do a formula that is constant time and this works assuming that like x coordinates are positive what I mean is if you have a be like a segment that is somewhere what I want to do is I want to push it let's say somewhere around point 0 0 if I is say free free and B is 3/7 so this is like a vertical line by the way but I don't care about it from that I want to normalize it so that I want to get this I want to shift shift it so that this would be true so I will get 0 3 and 0 7 and then if I is for example 10 free and B is 10 7 to normalize it to this thing I will get the same stuff so by normalizing I first change every pair to such a normalized one and then I claim if two things gave me the same normalized part they create a rectangle and this is extension of our first version of a problem I think right we're here I just shifted my vector perpendicular to I B and here because I had vertical line what I did is I shifted by horizontal line just to the left yeah so I think that this gives us an square solution yeah this would be interesting to code out well now we ran out of time so I think we were gonna and also in an effort to keep this video contained and you know to make a coding interview we're gonna stop but this would be really interesting I wanted to do a very quick debrief with you Camille so first of all great job I think this is exhibiting this is a perfect example of a really the the kind of real coding interview that you could get at a company like Google and it's a perfect example of a question that first of all is very difficult I think the first part of the question was very difficult and most candidates would struggle through that first part during most of the interview but here we were able to kind of or Camille rather was able to kind of stretch the question and dive into a part of it that's just really really difficult and really knew where the you know he's working to kind of try to find a solution the interviewer is not expecting a perfect solution for the second part we're just kind of looking to see how this candidate can can solve a problem or try to solve a problem so really great job from that point of view and also I want to say Camille your solution to the first problem I can't find it any more at this point but the one with the lines it's funny it's actually different than the three solutions that we have to this problem on our go expert we came up with three solutions that are all three different than the NIR solution so that was kind of cool to see okay that's interesting I find it finally I find it funny by the way about the second version that at sample moments we were we just worked together with that because it was a interesting hard problem I had you also for some moments like also tried maybe this works maybe this worked with that one also the slope idea of course I didn't investigate that much yeah but it I think also helps that interviewer doesn't just watch but he should give hints and also be some kind of sanity check help yeah I think if I've said something very very stupid there would be at least the question why is that that noise I could go into that direction and waste half an hour definitely and I think it's for these for these kinds of problems that are hard again I think that this is a problem even the first solution or the first version that is quite difficult it is gonna be expected that this is gonna be kind of a problem that you're almost solving with the interviewer you just happen to be the person kind of leading the interview they're just there to kind of give you you know little hints here and there but overall you're the one leading it would be strange if it was the other way around of course but awesome that's that's gonna be it I think for the for the interview Camille any last thoughts on your end I thank you for geometric problem because then as I said I'm good in geometry so I think now people will treat me better than I am actually because this is my area of interest it was problem was hard enough the second version ended in a lot of problems including the first version it's just that I already knew problem that is similar enough because I solved thousands of problems my life and here the second version maybe the middle point would work immediately I'm not sure now about it because I saw a similar thing with that solution and it was nice to investigate something for half an hour get some help from you and indeed show I guess how coding interview should look like yeah and I guess we show you by the way just tear what you just said about the first version that if you practice enough and if you do enough of these problems you will be able to do even very difficult problems like this one pretty easily like Camille just said he had hadn't seen necessarily this particular problem but he's seen similar one similar patterns and so he was kind of able to nail it that's true and by the way you don't need to self like thousands of problems because you don't need to solve a Google interview problem in seconds like to know a solution in seconds of course an interview of course again like here here I think you you did fantastically in the interview especially in the parts of like algorithm and design and data structures these kinds of parts he really did fantastic but I I want to make it clear to the audience that you not have to do this well in the algorithm and in finding a correct solution to pass the interview in fact again for this particular problem for the first version I probably wouldn't even expect the candidate to code out a fully working solution so just to put things into perspective that here you know Camille is really performing super well but he's also like a competitive programmer I'm kind of professional in solving problems and the other people who practice is for I guess a few weeks that's such a bad at subway image of describing yourself like you're a professional problem solver yeah that's a nice way to put it all right well that's gonna be it I think for for the video thanks so much for being here Camille and if you enjoyed this video make sure to give it a like and to subscribe and also we filmed another video on Camille's channel where he interviewed me not in a coding interview but more kind of getting to know me and asking me questions about you know my math background and these kinds of things so if you're interested I'll put the link in the description and in the comments below be sure to show them some love and I'll see you in the next video

Channel: Clément Mihailescu

Views: 2,450,997

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, facebook coding interview, amazon coding interview, technical interview with a google engineer, interviewing.io, Errichto, errichto interview, algorithm interview questions, google coding interview python, real coding interview, google software engineer interview, AlgoExpert, Joma

Id: EuPSibuIKIg

Length: 54min 16sec (3256 seconds)

Published: Sat Sep 28 2019