Mock Google interview (for Software Engineer job) - coding & algorithms tips

hi and welcome back to another episode of the T bleed it's good T bleed now I thought what I would do for you guys today by popular demand is give a mock Google interview now I've done about a hundred of these interviews at Google and I wanted to present you what it would actually be like and to give you a real question that I asked so let's just get right into it you walk in I agree - hi my name is Patrick great to meet you everything going ok are you you need a cup of water you need the bathroom break and as I mentioned before if you don't really need a drink or a bathroom break that just refuses so you have as much time as possible for the interview and then I generally give you a little bit of background about myself tell you what I've been working on so that you can calibrate your conversation for me and basically by giving you some of my background it helps you understand how technically deep you can go in your own conversations or what areas I might be interested in knowing about and being able to comprehend so I've been working here at this number of years I've been on this team I used to work at this company I have this background now I would like to hear about you tell me about yourself with your story and this is kind of where you may need to have something prepared I probably haven't even read your resume completely at this point I may have stand it and all I know is I've been scheduled to chat with you and basically this is your chance to shine talk about any interesting project that you've done you can go broad and just say like you graduated from this school that you went to this internship and with this company and you did this project and that's okay but you really do want to at some point go deeper into some project because what I would really like to hear is some technical challenge or leadership or something technically impressive that you may have done and it doesn't necessarily need to be impressive like you'd be surprised how little you need to do to actually do something that may sound impressive you know like if you can even set up a website and do basic back-end calls and connect to a database and bring in some users or something like that like that's already pretty good really and as I understand a lot of people may not even ask you for your story I personally like to ask for your story so that I'm not just giving you a whiteboard in question and if there's something interesting that you've done in your own spare time in some project or something unless you talk about that and that's the other thing is there's no real rule about the interview everyone conducts the interview however they want so I can tell you how I might do things but it's really not reflective about how anyone else may be doing things this is just the way I do it and basically if you can talk about things like technical challenges and complexity that you may have done like engineering efforts or technical leadership like managing people or initiating projects or about some sort of impact that you may have had like you were able to tackle this key area that was able to bring in lots of users or something like that like any of those three areas would be really great to hit and probably for junior people what you're really looking to show is some technical complexity and by that I mean like not just like creating a really complicated system where like there's a ton of for loops and a ton of if-else statements the technical complexity is more like good consideration of trade-offs pros and cons memory time maybe using MVC principles object-oriented design maybe hooking up a lot of different api's together would be interesting to hear about and you want to remember to show that impact because a lot of people will say some complicated thing that they've done and it's really hard to understand okay was what was this really about like was this real and if you could say yeah we got like 5,000 users or something you know then that kind of validates a lot of the work so I would recommend that any project we do try to figure out what was the impact of that and craft a story and be able to prepare that story so that you can talk about it as soon as somebody asks you tell me about yourself and then this portion I would recommend checking the interviewers reactions a bit and find out if they have questions for you like they may not be interested in your story at all they may think you are going in that direction that's not interesting they may be bored they may not understand the technical jargon that you may using and this key that you don't lose the interviewer here if you bewildered the interviewer at this stage you will be viewed as somebody who can't communicate clearly and not only that you would have made the interviewer bored and the interviewer would just be like yeah I don't know let's let's just move on to the white boredom because this doesn't make sense this is a waste of time and you basically lose your chance to shine in the qualitative portion don't make it too long but it might even be nice if you can get on the whiteboard and quickly draw a diagram of whatever you were building and just remember to keep it quick because you generally have about 45 minutes to complete the interview I like to spend the first 15 minutes on you telling me about yourself and then have that last 30 minutes on the after whiteboarding question so in the whole scheme of things just really not enough time like that time passes by really quickly now often when they Candida is still talking I will start drawing on the whiteboard because I know we're running short on time already and I would draw this picture so this is the question that I really like to ask and that is that given a grid find the maximum number of connected colors and you can see that in this picture it is five those five blue it is those five blue boxes at the bottom now this is a question that I asked very often because it gives me a very good signal just in my own personal experience and in fact it is very similar to this question called flood fill and flood fill is such a great question I think it's even been banned but the question I ask is a slight variation on that so I still asked it and in my opinion even if the question is considered banned because it is so commonly asked and people think that everyone knows the answer to this question because it is such a common interview question usually actually for me even when the candidate tells me that they've heard this question before I still like to ask you it's not really about if you can solve it most people can solve it it's really about how you solve it and I'd like to see how you solve it and that's what makes it such an interesting question because it will actually tackle things like data structures algorithms coding it touches a lot of different areas now over the years a lot of tech companies have started to phase out trick questions where you either have a ha moment and you get the answer or you basically fail because that really doesn't give any good signal and a lot of those questions have no real practical use in the industry this question I feel actually is a pretty good question because it's actually practical like this question basically involves something very similar to tree traversal and it's something that's actually done all the time like you may have like a tree of views and sub views and you want to be able to traverse every single view and sub view without necessarily duplicating each one or you may have a bunch of nodes that are connected and you want to be able to visit every single node you should also keep in mind that you're being evaluated on your ability to rise to become a senior engineer so you may not use some of these skills as a junior engineer but our junior engineers are expected to eventually get to that senior engineer level and if you can't make it there like you don't have the foundations to be able to become a senior engineer then there's no future for you at that company basically because you need to be able to get to that level and when you're interacting with senior engineers who may be putting out proposals for tree traversals and efficient data structures and things like that it would be great if you can be able to at least converse with them and not just ask completely amateurish questions like why are you using a hash table why not using their a it's like because the array is slow how do you traverse a tree structure what like how do you do that like that's anyway let me give you the solution and if you want to think about it yourself go ahead and pause the video but the solution is depth-first search in a double for loop so you have two for loops so you can iterate through every single cell in that grid and for each cell you issue a depth-first search and you know this could be a breadth-first search too it's pretty much the same and that's just going to visit every single neighbor and from there visit every other single neighbor and it's a recursive algorithm basically and it can also be done iteratively as well and what you also need to do is make sure that you don't revisit cells that you have already seen otherwise you will recurs forever going back and forth between two different neighbors so this may require two methods the first is a double for loop method that iterates through every single points and cause depth-first search on each point and then the second is at that first search function I like to leave it pretty open-ended so I can see what data structures you choose some people may choose to use actual data structure to represent each grid point and like they can have a grid data structure actually some people try to set up a connected group of nodes it may be simplest to just have it to the array of integers where each integer represents a color any of these is really fun and if it looks like the candidate is somewhat junior I'm going to push them to just do it to the array of integers that's probably the simplest also if the candidate is junior I might simplify the question and just say let me just give you a starting point so you don't have to iterate through every point you just start at the point and it's basically just at that first search function from there on now and the me of this algorithm is really going to be in that that first search function that's why I want to see you write and it really involves going to each point and from each point calling that first search recursively on each of the four neighbors and it's basically interesting to see how people will get those neighbors like like you could check each individual point like left top right bottom and the problem with that technique is you're going to have a lot of bounced checks like you're going to be doing edge checks all over the place for that and that can be a little messy and tedious to read and if you instead were to write methods like is valid or get neighbor or something like that that would actually help you delegate some of the edge cases to other methods other functions that you can later fill out if you have time but basically being able to save yourself as much time as possible it's going to be one key thing in this another thing I've seen some people do is they set up an array of coordinates like negative one zero zero one one zero and zero negative one and those represent the four neighbors and then to iterate through that list to compute the neighbors and I thought that was also a pretty neat way to generate the neighbors although that's really not all that necessary either like if you know it's perfectly fine to just write out than their purse manually but I think you do probably want a way to deadly get away the need to do bounce checks on all the neighbors because that's going to be somewhat time consuming to do one thing that people will need to do is to duplicate detection so each time you visit a cell you need to somehow remember that and the optimal day the structure for this is probably going to be like a hash map hash table type of thing and here's where I like to ask people as well like hey what happens if there's a collision was your hashing function and that kind of shows like do people understand the time-space complexity of a hash table how it works what that hashing function is so I think those are all great things to see some people will not use a hash table and just use an array and that's kind of a red flag because an array is a less efficient data structure and and by now personally I just like to see engineers know when to use hash tables like they should have that tool at their disposal and know when to use it clearly so usually candidates will write the recursive algorithm first and you know that's great but then what I like to do is ask them hey do you know about stack overflow from recursion and you know it's like oh yeah recursion generally uses stack space which is limited and that limit is going to be based on the maps that space you have but it's something like 10,000 iterations or something like that so this is where you probably should have asked the question how big is this great going to be and I would have said oh yeah the grid would have been like 10,000 by 10,000 or something and that's when you realize okay you should be using an iterative solution because the iterative algorithm is basically not going to be bound by a stack space but by actual memory size which will be like as much RAM as you've got the iterative solution basically involves using either like a stack or queue and pushing cells onto that stack or queue like you visit each cell and you take the four neighbors and push them onto a stack or queue and you basically just pop them off the stack and you process each one you take each one and you push their four neighbors onto the stack again and you just keep doing that until you hit every single cell and all the while you're making sure that you don't revisit cells that you've already seen and so this is the expansion of that problem and probably why you want to make sure that you have plenty of space on the whiteboard you're gonna want to at the top left corner and just write it in a small font not too small but not too big either and give yourself some space between each line in case you need to add statements between each line and what I like to do is I like to make sure that I bring my own pen just so that I'm not stuck with like a bad penny like just a red pen or like a pen that's out of ink like like a good black pen that's reliable it's great to have it and it's also why you want to make sure that before the after interview you do some practice on the whiteboard with an actual pen so that you have an idea of how you can write quickly what abbreviations you may want to make so that you can save yourself as much time as possible by the time you finish writing all of this stuff there's not going to be much time left right like it's gonna take you like probably 25 to 30 minutes to write all this stuff but you're not quite done because I need to hear what the time-space analysis for this stuff is and that is going to be a very key part to because it's not just about finishing the problem you need to be able to understand the trade-offs and ideally you could have told me the time-space analysis before you even begin like you could have just said hey yeah there's a recursive version and an iterative version and you know this is going to be done in linear time the hash table will be done in constant time and like you know the recursive algorithm is going to be simpler to read the iterative version is going to be a little bit more complex to read maybe but it will not be limited on recursive stack space like if you can give me all those trade-offs upfront if that's really going to be the best if I have to ask you at the end that kind of shows like we were just coding and we really had no idea about the runtime where we're going to do what the trade-offs were until we got to the very end and you know maybe at the end it was like just way too slow or something most people won't get the right answer at the end you know it's linear time and because you're doing duplicate detection so that you will only visit each cell just once so given the matrix that is size n you will visit an item's and that is your runtime but again it's not really about whether you get the answer or not most people do it's about whether you're confident about the answer and whether you can explain it so that would conclude my questions and then I would ask you to take a seat and you can answer any questions you have and some good questions keep it positive and remember that even if you feel that you did really poorly on the interview you may have been interfering with someone who is really not well calibrated like a beginner interviewer or someone like that and their feedback may not count as heavily as and more experienced interviewers so don't be too discouraged keep it positive and keep going do your best throughout the interview and I have one more tip which is when you do get a chance to go lunch like eat that lunch you know try to have a good time some people seem to not really be enjoying themselves and this is kind of your chance to enjoy yourself and because you're giving up a whole day for it and just make sure you have a good time the worst possible question you can ask is what was the answer to that question you know that's really a waste of time for both people like you you know you can just go home and research the answer like anyway they'll wrap it up for me if you want to get better at whiteboarding you might try going to web sites likely cocom where there's a bunch of different practice interview questions that you can go for but keep in mind that it's really not about getting the answer to that question like if i go to that website i don't even try to compile the answers i I'm just trying to get broad understanding of what type of questions there are and what type of algorithms I might need to have at my disposal but it's not really about the solution I think it's more about your thought process going through it the analysis the trade-offs being able to understand like time space complexity and just how to approach the problem and basically knowing the trade-offs between different data structures and algorithms as for the interviewer they'll be going back to write up a feedback report about how the interview went and it's going to be as non bias as possible it's just going to be a report of how you did and oftentimes the interviewer will even take a picture of the code that you wrote you will be evaluated on things like wizard coding good and that may involve like did you use object-oriented programming that was your code clean and well-structured algorithms data structures like did you know how to put together a recursive or iterative algorithm did you know the trade offs did you think about using hash tables arrays sets did you consider creating your own custom data structures if you needed that you may be evaluated on a whole range of different other metrics like how was your efficiency how was your speed were you a jerk and you should remember that yeah if you were like really smart and you did really well but you were a jerk and people didn't feel like they wanted to work with you then that's also going to be a reject India so and I would say especially for junior engineers if you can show that you are enthusiastic about learning and excited and you can take feedback that's going to be a key thing just showing that you are excited to learn because that's overall a valued skill so I hope you found that helpful good luck on the interview if you're going to be doing one soon give it a like and subscribe and I will see you next time bye

Channel: TechLead

Views: 811,414

Keywords: tips, facebook, tech, interview, coding, software engineer, techlead, whiteboard, google, programming, engineer, technology, amazon, developer, apple, googler, swe, software, computer science, cs, fb, software engineering, software engineer life, software engineer intern

Id: IWvbPIYQPFM

Length: 19min 19sec (1159 seconds)

Published: Tue Jun 12 2018