Cracking the Facebook Coding Interview The Approach

thank you for joining us today I'm here to talk about Facebook and how to do well in their coding interviews my name is Gayle LOC McDowell and I am a my background software engineer I worked for a while at Google also been at Microsoft and Apple did a lot of work at Google on the hiring committee doing interviews for especially for software engineers and then I wrote cracking and coding interview which I'm sure many you guys already have it's the major book that programmers get for interview prep and then I also do work to help coach people through interviews and as well as do work on the other side and help companies on their hiring process so I'm sure it came as a bit of a surprise to you guys that Facebook is prepping people for interviews that seems really counterintuitive a lot of times when I tell people I do this people are like well wait why does facebook do this that seems kind of weird so the reason why is essentially Facebook wants you to do well they want you to be prepared they want you to be comfortable they don't want you to struggle because you didn't know what to expect because you weren't you know because you didn't get the chance to learn the things you need to learn the reason why I'm telling you this is so that you understand that you know not only am i obviously on your side I really want you to do well but your recruiter in your interviews interviewers genuinely want you to do well they generally want you to do your best so that and that means that if you have questions you can ask your recruiter you can ask your interviewer the recruiter isn't trying to surprise you with you know how many interviews you're gonna get how long the process takes what kinds of things interviewers might want to ask so feel free to ask your recruiter any fault questions but also know that in the interview itself your interviewer is there as a resource and I'll talk about some specific examples later on but your interviewer is there you can you know you can ask them things like do you want me to start coding yet or not know that you you don't have to guess what the process and expectations are people are there to help you along the way so with that I also want to add that if you want to get it copy of these slides or look at them as you watch through the video you can get them at Gale comm which is my website click on events and then search for Facebook on the page there's also an auto response you can use if you send me an email at G at Gale comm with the subject FB prep one word you'll get a link to the slides a handout that I'll talk about later on and a few other resources so with that I'm into jump into the interview side so first what to expect I always hesitate to say this exact you know get into these specifics because some people will read this and think this is exactly what my process will be so and that's not what I mean so let me just put that disclaimer out there that this is a typical process it's not every single person has this exact process and again you can always ask your recruiter what to expect if you're not already told so as far as the number of interviews kind of general schedule things like that what you should expect is first interviewer an interview will generally be on the phone you'll have you know it'll often be kind of a coding and algorithms interview along with some questions about your background and some other things when you come on site very typically people will have two algorithm and coding interviews that focus primarily on that one design interview and then one interview that's kind of a mix of behavioral questions and some algorithms and coding but again this is just typical people with particular backgrounds might have more or less so I'm gonna hoot with you so one currently in college might not have any design someone who has much more experience or real specialty might have a bit more focus on design so you know yes this is what a typical person goes through but it's not every single person feel free to ask your recruiter what you should expect in a given interview like say coding interview what you'll generally see is a bit of chit chat at the beginning about your prior experience questions on your resume things like that a bit at the end where you get to ask the recruit the interviewer about the company the role things like that and then the middle of it will be technical questions please for a coding interview typically interviewers tend to ask two questions but this is not at all universal so don't think that just because you only got to finish one that that's a bad sign honestly when I interview I tend to ask very complex kind of multifaceted questions so I usually only get to one question no matter how good you are so this is typical most interviewers asked to but not everybody so yeah you can kind of expect to but don't think that just one means anything one way or the other okay so with that I'm gonna talk about different types of questions and how to do well in them first thing I'm going to talk about is behavioral questions so these are all the kind of questions about your prior background I'm gonna talk a bit about how to prepare for those one thing that's useful for most people to do is prepare a quick walkthrough of your resume so the structure I've found works well for almost everybody is the very first thing you say is kind of your headline I'm a soft fruit near you interviewer ask you something like tell me about your background walk them through your resume very first thing you say is I'm a software engineer or wherever your title is at such-and-such company then drop back to the beginning of your career usually College sometimes you might you might start off with talking about a particular job and then walk through chronologically from there you don't need to go overboard you don't need to spend a ton of time in any one area just give the brief little highlights this is not the time to go into detail in particular situations or accomplishments or things like that however there's a few things you can do to make your your kind of pitch stronger the first thing is telling the interviewer things that kind of demonstrate that you were successful so that can be you know features you builds it can be saying something like I scaled the system from 1 million to 10 million users some like that but it doesn't it's not always an accomplishment so I were interviewing somebody and I heard something like you and then I left company one when my old manager recruited me out to join his startup that's not an accomplishment being recruited out by your old manager but it does show that you are successful so think about those things that will make the interviewer say hmm they seem to have done a pretty good job there second thing to look for is something to think about is what do you want your interviewer to ask you about what are your interesting technical challenges or other stories you can kind of guide your interviewer there so you if you say that you know since the last three years at company a and been focusing on a lot of different things I've scaled the system from 1 million to 20 million users I've also done a major we are textured the data store it's natural for your interviewer to follow up with oh so tell me about that reaaahhr texture talking about that scaling so think about what do you want to talk about and guide your interviewer there it's a win for you and it's a win for the interviewer they want to understand your best accomplishments last thing here is hobbies realistically you know I've done a lot of interview coaching and when you get down to it most people don't have hobbies that they're that compelling in that that's fine it's not a you know don't think it's a bad thing if you don't have any hobbies like if you're busy with you know family friends and work fine but if you do have hobbies think about mixing them in it almost never hurts to say hobby so you can always you know when in doubt just just say what the hobby is but think about when you talk about your hobbies what's the best way to talk like them what how can you frame them in the most positive relevant light for example if you like to run so one person I was coaching interview coaching like to ride they're really into working out okay you know and you can say it won't hurt you why not but is it as I got into more discussion with him it turned out that he had signed up for 100-mile ultramarathon that's running a hundred miles I'm just insane and then but he actually quit a part of why he didn't actually tell me initially was he kind of thought it's a failure he had signed up for this hundred mile ultra marathon quit at Mile sixty though so he never finished it and the reason he quit was that he got injured at Mile thirty so he viewed this as kind of a failure but what I heard was wow that's that's incredible first of all you signed up for an incredibly hard challenge I mean running a marathon is hard enough he's running for marathons back-to-back that's an incredibly hard challenge so he's willing to take on obviously very hard challenges he did a huge amount of it I mean 60 miles yes you didn't complete the whole hundred miles the 60 miles is a lot so you actually pursued a really hard challenge you you know I signed up for but you did a lot of training to get there to be able to do 60 miles and he did those 60 miles half of which when he was injured so this is not you know it's obviously not a technical technical accomplishment but it is showing some very relevant things risk-taking is relevant persistence is relevant willingness to take on a credibly hard challenge that's absolutely relevant so think about your hobbies with that perspective what you know take the hobby and figure out is there something that is particularly relevant from it and try to reveal that information and certainly any technical hobby should be mentioned learning a new programming language you know oh I've been getting really interested outside of work in functional programming definitely relevant doing hackathons coding competitions building an iOS app even if you've never launched it even if it's a failure any technical accomplishment any technical hobby definitely mention that stuff then go through your pass work think about it and pick out a couple projects at least one maybe two three projects that you're gonna be particularly well prepared to talk about in detail find things where you were really central to some of the hard or cool parts and then go through your past work and all of your past work and be prepared you know especially those two projects but really all of it were you prepared to think about something normal follow-up technical questions people asked so what were the challenges what were the technical decisions made what were the implications of those why did you pick these technologies what were the hardest bugs etc be prepared to answer a lot of those technical questions but also think about the softer side of it so what was the teamwork situation like were you leading or you kind of a follow how did you lead if you led something what did you leave how did you show leadership what were the kind of interpersonal conflicts challenges things like that so think about not only the technical side of the project but also the softer side of that and then be very well to be very well to really be very well prepared to really talk about what you personally did and also think about what would you do differently so in that point it's kind of important I'll wrap up here talking about behavioral questions but it's really important to think about that Facebook wants to identify people who will perform well here so yes that's about people who are technically knowledgeable and passionate and and all these kind of things it's also about people who work effectively on teams and who you know people would enjoy working with and it he would be able to contribute good work so the people I interview when it was some when some people I interviewed they tell me that basically they thought the project was great they wouldn't do anything differently they you know they sometimes people will get very defensive when you ask them what would you do differently they're kind of defending every technical decision they made as perfect that personally starts to worry me a little bit because there's no way a project was done perfectly so if you're telling me it was perfect you're either unwilling to admit to mistakes or you're unaware of what those mistakes are either one is a problem I want to find people who yeah generally speaking do great work but they're also aware of the issues there so think about your projects from that perspective be open about the issues and the mistakes and the weaknesses it's far more impressive to me to hear somebody be open about the mistakes they made than to act like it's all perfect that's what I'll say about behavioral questions well now I'm going to move on to the technical side so the one other type of question that you should expect is design questions so I'm going to talk about design questions from the perspective of system design and scalability but understand that whatever your focus is you'll you'll probably get designed questions that focus a little bit more around that so if you're a front-end developer you're gonna make questions that are more about front-end architecture maybe I API is things like that so this is from perspective a system design for parallels with these other design questions we also an add-in here is that you'll you should expect design questions relevant to your background that doesn't mean identical to your background so if you've been spending a long time building say you're working on search products it doesn't mean you'll get a design question that is you know design a search engine so relevant but not identical to your background all right so I'm gonna talk about design questions now these questions intimidate a lot of people largely because they think there's some magic to them they are they think that to know a lot more than they do the way you should approach design questions is with this acronym would you what this means is just what would you do at work that's how you should approach them if I were your manager I said hey I need you to go build us a system like tinyurl or bitly hopefully you wouldn't say okay great and then run back to your office spend three weeks building it and then come back and say tada I'm done you know that would probably be disaster right it wouldn't be the right technologies it you know be like oh actually I need this be an internal API you never even built an API so hopefully in the real world you would take an approach that's more like this it's okay tell me a little bit more what do we need what are we building this for you'd scope the problem the Bunge then maybe you'd get an initial design of the system and then you think okay just this does this really work and you start going to in more detail really thinking through the different problems and then go about trying to solve the problem it'd be a very iterative process this first piece scoping is super important and something that far too many people just gloss over the scoping piece means stuff like if you're building tiny URL or bitly or you know service like that scoping piece means asking questions like is this a website or an API is this our you know are we going to allow people to have you know enter in their own little short URLs or are we going to you know just Auto generate all the URLs so scoping means stuff like that another question I often ask though is how would you build something like Amazon's product rank system so every product and Amazon has a best-seller rank associated with it so if you look at say a book you might see oh it's the 1050 third best-selling book how would you build that little component so scoping here means you would want to ask questions like is the rest of the system fully built presumably yes but it also means something you know you might also want to ask question like well what do we mean by bestsellers right when I've asked this question a lot of people just gloss over this they assume they know what best-selling means and they don't define it and that's a problem what if in the real world a customer your product manager or whoever said hey I need you to go build this best-selling thing and you didn't spend the time to figure out what they mean by that you could spend forever building this other thing and that's not really what what we need so what I tell somebody who asks is is no best-selling actually means over some window of time that's a very different design right define having a number that increments at every single sale for all of history is very different than a sum of some sliding window you might want to know things like over you know so they were what window of time is that best selling rank something like does the data have to be completely accurate or is it you know plus or minus ten percent and the ranks is enough does it have to be updated every single sale probably not so you want to ask these questions take that scoping part very very seriously then when you go on to the other components you're just starting to say okay well here's a naive idea of the system you know very simple very simplistic system might be we have a you know a front-end layer and API layer and then a datastore maybe an analytics engine over here and that's kind of like a brute force a naive system go to the whiteboard use the whiteboard to do this and then you start going into more and more and more detail think when you're doing this what are the complexities where are the simplifications where are the different challenges or trade-offs or bottlenecks you might be hitting so in the case of tiny RL or bitly if every single URL hits the data store to grab the you know associated URL that might create a little bit bottleneck so maybe you want to put in a caching layer in there so start going into it more and more and more detail think about the trade-offs the challenge is the bottlenecks and then go and fix those discuss this top-down it's not you know take one component and then just dive into in ton of detail you know I've seen people I interview who they get this initial sketch for this Amazon product rank and then they take one thing like the database and they start going into a ton of detail on all the different database tables and this and that and they don't go into the rest of stuff they kind of lose perspective a lot of what they design may not even be the right thing because they didn't think about it they didn't think about how these tables are actually tied into the rest of system so take a top-down a little bit of the time don't just take one component and dive into it in ton of detail the behavioral aspect here super important you want to strike this balance between driving the process and being a great teammate and there it's actually less a balancing act and more that they really go hand in hand driving means that you should fundamentally stay in charge you should kind of act like you're the senior engineer you're driving the discussion you're figuring out where to go into more detail you always have more things you can talk about you're open about the trade-offs so you're driving the process some people I interview I you know ask a question and then you know they give me a 30-second response and I feel like I have to just pull them through the problem and direct them at every single step along the way that's not it's not great I want someone who can really take technical leadership there's other people I interview who are kind of dismissive of me and they make me worry about what would would it be like to work with them on a team so I ask a question and they kind of brush it off they dismiss it a little bit they probably aren't trying to do it but they are being dismissive of the issues I raise I'm not saying here that you that every time I say won't be this be an issue you should say yes absolutely an interest immediately concede maybe it's not an issue with your design maybe maybe I'm wrong that I thought it was an issue or maybe I knew was an issue but I want to see if you're thinking through why it's not either way you know the point is not to concede to the things interviewer says but to really give it some careful thought and some analysis just like you would hope in the real world somebody would do I would hope in the real world if I were working on design with somebody that yeah they could hopefully lead the discussion but even if I weren't leading it even if I you know maybe I know a little less in them that they'll still take what I say seriously so strike that balance and again use the whiteboard some people sit in their chairs a whole bunch use a whiteboard it's there for a reason this by the way this discussion of bout of driving versus being a good teammate then you know I'm talking about this for system design but this is absolutely the case in algorithm questions as well you want to derive the discussion of algorithms but you also want to be very Sun stick to the things that interviewer says last thing here I'll talk about with design is preparation so preparation again this is from system design but whatever your you know focus area is in technology it parallels with that too one thing that's very useful to do is go read about the design of different systems so go read about you know Google's infrastructure and Twitter's and Korra's and and yes Facebook's the idea here is not to go and study and memorize the infrastructure of any of these companies including Facebook you don't really need to know like all about Facebook's infrastructure the idea here is just read these different things and start to identify the patterns really you know just memorizing this infrastructure the these different pieces of infrastructure won't help you that much what you want to do is really learn and think about them think about what is what are the fundamental differences in Google's problems versus Twitter's why have they chosen different architectures even for something for like say a datastore what how are they the same how are they different and one answer to that is okay you know Twitter has to be real-time in a very different way than Google search how does that influence what they're doing so the idea here is think about what they're doing not just memorizing what they're doing this would be very very analytical here and then you'll see a lot of patterns come up as you do this you'll start to see different ways of scaling large databases different ways of handling tasks use go use those as jumping-off points also learn about the different piece of a piece of infrastructure or technologies relevant to your focus area so for almost everybody that might be learning the you know basics of the web stack you some people might also want to learn about rest or things like that well go learn the major pieces of infrastructure technology etc that are relevant to you or even more broadly development and then the only thing that can be useful to do if this is particularly if it's this is something that comes as a little bit challenging or intimidating to you is practice a little bit of back the envelope calculations it's very common that you know I interviewed somebody a little while ago and I asked them to build an RSS reader in order to do this they need to figure out how much of the database can fit on one machine can it all fit on one machine and that requires thinking about how many users about how many URLs how many feeds would each person have about how many those fees would be active how many you know how many posts per day or per window of time how big does each post you know how many megabytes how many whatever and so they have to do this back of the envelope calculations to figure out what's realistic to fit on one machine practice that if it's not something that comes naturally to you one piece I want to leave you here but leave you with hair before moving on to algorithm questions is and I really want to drill this in these are fundamentally problem-solving questions so yes learning these different infrastructure pieces technologies etc can be very useful but fundamentally they're problem solving questions you're not asked to design a system like tiny olive bitly to see if you already know how to do that you're a being asked because they want to see how would you do that so they're fundamentally they are problem solving questions not your tests of knowledge so just keep that in mind both as you are preparing and as you're going into the actual interviews they're problem-solving not knowledge questions with that I'm going to switch to talking about algorithms so algum questions are you almost certainly get some algorithm questions the reason why they're asked is a good chunk of it is analytical skills problem-solving skills assessing that another piece is seeing your communication skills what is it like to work with you you know what what does it like to solve a hard problem with you can you make good trade-offs can you do you think about things as trade offs or just you know this is the way to do it and then you know one thing I really like to see is I like people who are at least willing but ideally eager to solve hard problems by contrast I interview some people who are kind of what I refer to as mentally lazy they're not necessarily dumb I'm not saying they're they're necessary done but they can be actually very bright and still be what I call mentally lazy these are people who just don't want to think it's correct and lungs is correct it's fine they don't care if the code is you know has terrible style they don't care if it's terrible of variable names they don't care if it's poorly organized they don't care if the algorithm is really slow correct is good enough for them and that worries me a little bit I want to work with people I want to hire people who are excited about solving a hard problem and so that's one thing I like to look for are you at least willing at the very least but ideally excited about solving the hard problem and then another component of this is just finding people who are have a good strong have a strong foundation in computer science what does that mean I don't mean you must have a cs degree because there are plenty of people who get hired who don't have CS degrees we need to have a strong foundation in computer science without that here's what I say is the must have knowledge this is the must have knowledge you can do more than this absolutely and don't let me stop you you can go learn Dijkstra's algorithm and topological sort and a lot of these more complex algorithms they won't come up a whole lot but there's no heart and you'll cut rule for this stuff it's fair game for an interview and this stuff is not so you know you could go learn that it could come up I don't see you come up a whole lot these are the topics that I think are really really fundamental that you really need to have where if I were interviewing candidate and they didn't have some of this knowledge it could present a problem so you'll see you know the a lot of stuff about Albert you know ArrayList hash table is really really important sorting and searching algorithms you certainly need to know those one thing that is super important is big-oh time and space this is the topic that I'd say when I when I do interviews with engineers that startups I'd say about half of those people claim to be comfortable pick out the other half admit that they're very not very much not a consul with it but how about half claimed to become flipping out of those 80 plus percent are not quite comfortable enough they're still making a lot of the common mistakes so you know play the odds here and you're probably in that bucket of people who isn't quite comfortable F of Big O so spend a bit of extra time making sure you're really really comfortable on the basics and then last topic I'll mention here is recursion and memorization and dynamic programming practice recursion they it comes up a lot in interview questions and you may not have a lot of real-world experience with it when I say dynamic programming though I'm not talking about these super famous dynamic programming problems that you hear about and you know big thick algorithms textbooks I again you can learn that I'm not stopping you but what I'm talking about more is the pattern of practicing memorization and dynamic programming problems it's a pattern that comes up in a lot of interview questions and it's substantially easier once you get used to seeing that pattern so practice some of those problems for preparation as I said really master Big O that's one of the first things I would do is just make sure you have a very strong foundation and what that is then you know go and implement that whole list of data structures and algorithms go and plant all those from scratch it's unlikely at Facebook that you get an asked something like implement a binary search tree you could it's just actually kind of an easy boring problem so I don't know I wouldn't ask it but you could get it it could happen but more likely what would happen is you'd be asked some modification of it so one question I ask does not require you to implement a binary search tree by any means but if you aren't very comfortable with the implementation you're gonna have a lot more problems on it so practice practice implications it'll really help solidify your knowledge then practice on real interview questions and you know there's a ton of resources for this career cup is one glass doors another what I mostly stay away from is people who write blogs are like top 10 crazy questions like those are picked because they're obviously like crazy questions so they're not really representative but practice unreal interview questions you can go read algorithms text books and things like that the it will help you but the knowledge is generally beyond the scope of a normal interview so it's not quite as applicable it's best in my experience particularly if you're short on time to actress actually practice on real interview questions really important here though code on paper a lot of people don't spend enough time practicing this you forget before you forget how much you're you know a computer kind of holds your hand you have syntax highlighting and so you kind of know when you write the wrong thing you might have some code completion you might you know when you open up a new file get a whole bunch of templated code that pops out in front of you you know ask a see develop or a c++ develop or something as simple as write hello world and a ton of people are unable to do it because they don't usually have to write code completely from scratch so practice coding on paper there's actually a more complex and impactful reason why it's so important practice code on paper when you've been it's not just that you have syntax highlighting code completion and all these other other nice features on a computer it's also simply that computers are faster you can type a lot faster than you can handwrite so what you've done and you haven't totally realized you've done this probably is you've gotten used to a pattern of oh well you know if I understand code the new album about to write about this well I'm going to start just coding if I make a mistake I'll fix it whatever I'll realize they'll test it I'll restructure my code whatever it's only ten or twenty lines so I'll just go ahead and do it so you know you look for a level six understanding on pen and paper now or on a computer when you're writing in pen and paper it's just slower and that means that every you know if you start writing the wrong thing takes a lot longer to get back on track it's not a lot more time writing the wrong thing you can't just throw in a new test case and rerun it every mistake you make every bit of confusion is far more powerful and far more damaging than it would be if you were on a computer so you want to get very comfortable you want to with coding on pen and paper because you want to learn to slow yourself down take a moment before you start coding to really make sure you know what you're about to write and the best thing best way to do that is just get comfortable handwriting and get comfortable with hey I really need to understand what I'm about to write before I write it you can't cut corners here you also just want to know about how long is it gonna take you to code something so practice coding on pen and paper then do mock interviews you can you know there are various mocks mock interview services out there to practice interviewing those are great you can do those you can also just grab a buddy and practice interviewing each other in fact it's really useful one thing I've done when I'm coaching people is particularly coaching the larger team it's all often have people interview each other because it's actually really useful for somebody particularly those who are more nervous to try be on the other side try being an interviewer because you'll start to just naturally do a lot of the things that interviewers tend to do so it's actually useful to practice being an interviewer as well and see what it's like from their side so do mock interviews then the last thing here push yourself a lot of people too many people look at interview preparation as a quantity game they're gonna try to learn as many problems as they can before writing code they're before you going to interview and that's it's not really what it's about it's more about quality spend time really pushing yourself when I ask a question my assumption is that you don't know how to solve it and that you're going to essentially that means you're gonna be struggling you're gonna need to be comfortable with seeing a problem if being hard and finding techniques to make progress if your technique to solve a problem when you're practicing is to look at the back of the book well--that's you're gonna be kind of out of luck in an interview so really get comfortable pushing your if you're using cracking the coding interview in the sixth edition there's a whole bunch of hints there use those you know they're there for a reason but try not to use them or try to use them as little as possible so if you have to use a hint you look at the hint read it and then try to make as much progress as you can before going on to the next hint do as much as you can to push yourself through the problem before you look for more help because that's what you'll want to do in an interview so push yourself as much as possible so with that uh as you saw in the one of the last slides one of the things I stress a lot is really really understand Big O so I'm gonna give a very very quick crash course on Big O so it's not going to teach you everything that they go in you know five minutes or whatever it's gonna be very quick crash course for people who know nothing about Big O this will hopefully just kind of give you a taste of what it is for people who have a bit more understanding you'll hopefully kind of jog your memory about some of the common mistakes and hopefully you'll avoid those in the interview but at least it'll be a little jumping off point for you for hey I need to understand this a bit better so we'll start with some more simple things okay first problem here I'll start with the basics we have a for loop it iterates from and this is all in pseudocode so don't worry about any particular language you need to know for this we have a for loop that iterates from 0 through n what's the run time well Big O is essentially like this is a bit of a simplification but an equation to discuss how things scale with time how the run time will scale with time so in this algorithm this little bit of code the run time will scale linearly with the size of n so we would say it's o of n basic stuff all right bring a little more interesting now here we have nested for-loops the first one goes from I equals 0 to n second one goes from J equals 0 to N and it prints a pair IJ so this just goes through all the numbers between 0 and n and prints all the pairs one thing we can do to say the right time is we can say well if we're printing all the pairs of values and between 0 and n there's N squared pair so the runtime should be au then which is indeed is the other thing the other way we can look at it is the inner for loop takes open time and that's run n times so the run time will be n times N or n squared both perfectly valid ways of getting for the answer ok more complex slightly more complex so okay little more interesting here now we have a for loop that runs from 0 to n and within the for loop it checks to see if n is even and if so prints it so prints all the even numbers now as you may know this is still o of n because we're still before loop that goes from 0 to n just because it only prints stuff half the time it doesn't change the runtime because we're still going through all of those values between 0 net so it's still event even if we did though even if we were able to jump from 0 to 2 to 4 to 8 or 2 from 4 to 6 to 8 that would still be o of N in Big O we drop constants we don't say something is o of 2n we say it's o of n because we're concerned about saying is does a scale linearly and both N and 2n scale linearly so we don't drop car we do we don't include constants and this is one of those first things that a lot of people make mistakes on when I hear someone describes a runtime as 2n or 2k or something like that it's kind of a sign to me or okay this this person doesn't quite get Big O so keep that in mind you drop constants okay next example here we're printing the evens first and then the odd so two for loops one from or both from 0 to n1 checks for if it's even prints it one print pics checks texture that's odd then prints it the first for loop is open second for loop is also of n so the total run time is o of n not up to n as I said earlier you don't you don't include constants to OV n for loops that's okay all right we're gonna start getting a little bit more interesting we had before we have had printed Paris we were printing all the Paris from zero to n now we're printing all the ordered pairs so we have I from 0 to N and then J starts from I and goes through n so it doesn't start at 0 it starts at I instead and are printing the pairs we call this ordered Paris because we we don't print all IJ's we only print the J's that are bigger than I so it's ordered pairs one thing we can look at here is we can say well this I when I is 0 we J goes from 0 through n when I is 1 J goes from 1 to N then to the end then 3 to n then for 2 and then 5 to n etc so where is printing all the pairs was like we're printing a grid that's n by n here we're still kind of a printing a grid but we're only printing the top right side of the grid so we're printing half the grid so that's n squared over 2 things we're printing roughly which again is ov N squared not we don't say OV n squared over 2 because we drop constants so oh of N squared all right so go back then so now again printing ordered pairs but now we have 2 different arrays here we're printing from I equals 0 to a to a dot length so going through all of Munson a within this we're printing going from J equals 0 to B and we're printing the pair IJ there are B of a of ibf J a lot of people here and this is one the most probably the most common mistake I see people make a lot of people here will say N squared they see nested for-loops and they think aha nested for-loops N squared be very very careful here when you say o of n for some some algorithm you mean o of n where n is some particular thing it's not you know inherently open inserting a node into a balanced binary search tree or finding a node in a balanced binary search tree is not inherently log n it's log n where n is a def the tree it's also oh of n where n is the total number of nodes in the tree you can't just say Oh event or log n it's not inherently those things so when people describe this as many do as n squared that's you know that's not quite correct because what would n mean and can't be the length of the array because there's nothing in here saying a and I a and B at the same length so you have to say it's O something like over a times B of M times then it's something like that that's a very very very common mistake it can cause huge problems when people don't get that so different inputs through every variable in runtime has to have a meaning different inputs is a different it has a different variable so of a times B unless of course you're told that a and B are the same length in which case saying N squared would be perfectly fine so very very careful be very careful there different variables means a different runtime all right now we're getting a lot more complex here's a big chunk of code don't just try to look at this and say AHA this thing just walk through it step by step so this is code that first walks an array of people and does some simple max function then it walks through all the people all over again and looks like we have a nested for loop so this is going through each person nested for loop here that goes from walks through problem every year from their birth here to their death here and increments something and then we go through another array so let's just take this piece by piece okay first step is we're walking through all the people so I'll do some I always like to use logical variable names in runtime I don't like to use and actually because unless there's like no ambiguity about what and what n could be so I'd like to use logical grammar names so P so this step is ofp because they're walking through all the people where P is the number of people I'm going to assume here that max is you know a constant time function which it almost certainly is so o of P then for each person and there are P people we're walking through every year from their birth to their death so this for loop here inside will be O of L where L is a max lifespan and then we're doing that for P people so of P times L then third step here is we're walking through every year from the you know first person's birth year to the last person and then we're going and incrementing something so I'll let this be oh of Y where Y is the span from the very first birth year to the very last death here and we're and so that step is o of Y note that T and Y and L wine L are not the same thing this is walking through each person's lifespan this is walking through the lifespan of the entire population so it's not not the same thing if every person lives for a max of you know each person lives for a max of 100 years but we're you know looking at all of the people who've ever lived on earth those are gonna be very different numbers so to get the runtime then we add these things up so that's gonna be Oh P plus P times L plus y so that gets down to P times L plus y be when the mistakes that people make with runtime is they get tripped up on when they add and when they multiply things adding is I do this thing I'm all done it's wrapped up I'm good and then do this other thing that's adding when it's I do this thing for every time I do this other thing that's gonna be multiplying to keep an eye out for that I think most people understand this fundamentally but they make a lot of mistakes there okay now we're gonna get harder so Fibonacci this is a basic recursive run the cursive code for to get the nth Fibonacci number so if we call fib of n if n is 0 1 return 1 otherwise call fib of n minus 1 plus tip of n minus two recursive runtimes are one of the things that I think the bastard and people really struggle with getting because I want to look at it and they want to just say you know it's easier when it received or loose whatever to get the run time it's harder when it's like what this thing calls itself a bunch what do you do the way that I found works well for people to get the run time is to actually walk through it see what happens draw what I call a call tree so fib of 6 who's gonna run through an example fib of 6 cost above 5 and fit before good with 5 culture before fib of 3 for the for call tip of 3 5 2 etcetera talk so it's happening and kind of like a tree so if we look at this this tree has a height of 6 or in this case height of 6 in general you know if you call fib of K you'll have a fib height of K every level doubles the number of nodes because each call call that two more times so if we have one node at the top and then we're doubling it we're gonna have two nodes then we double the number of nodes the next level and then double and double and double if we do that k times if we take a number and then we double it k times you start with one that's gonna be 2 to the K so that gives us a runtime of over to the K now this is a you know you can go online and read more about this it's actually a little a little bit of a simplification for more complex natural reasons that are way beyond the scope of this or a normal interview it's actually slightly less than 2 Z K but to the K is a perfectly satisfactory answer so over to the K this is a technique that I found it is very valuable for a lot of a lot of recursive runtimes to draw out this call tree now as you might know this is not the best way to do Fibonacci one little optimization is to notice back here that we're calling Fibonacci on the same nodes more than once so fib before is called twice well that's that's so stupid right like why call the before here if we already did it here we should only compute it once it's not like the answer changes likewise you know why called above 3 to the 3 when soon before also called fib of 3 down here we only need to do these things once so that's this is getting into a memorization approach so we'll add in it's essentially operating like a hash table that says okay if we haven't called it before haven't computed fib of n you know compute that and then return the computed value now we draw out the call tree it looks a little bit different fib of 6 calls to the 5 to the 4 but it doesn't go anywhere after that before because soon to the 4 is already computed for the 5 cost of a four in favor of three but tip of three would have already been computed so that one doesn't get called here if we draw out this thing we don't get a tree anymore with you know not like a full complete tree that's huge like the last time we actually just get something that looks much more like a straight line down here that straight line goes to a length of n so that gives us a runtime of oh of N or okay so when you and that's this actually brought a point I wanted to make when you see really really slow recursive algorithms think about memoization look for those repeated problems okay so that's the very very quick crash course in bigout does not meant as I said to teach you everything you need to know about Big O this is just kind of the basic some of the common patterns you could that you'll see come up please please go practice big out you need to know it really really well it's not about you knowing the Big O time of all those algorithms and data structures I put up earlier yeah absolutely you should know that stuff but the point is more that you need to be comfortable enough with Big O that if you see a new you know if you're designing a new algorithm which is what you'll really be doing interviews you'll be designing new algorithms you'll be able to immediately state the runtime for that algorithm and then you'll you know make this or that change and you'll say ok now it's this now it's that so you need to be really really fluid with Big O so go practice that with that I'm going to switch to talking about how to actually solve algorithm problems ok so I wanted to go and set a bit of expectations here because while people walk in thinking that it's they need to know a lot more than they do so I like to set expectations first of all you don't need you know the answers to the problems I asked in fact if you do already know the answer please just tell me oh I've heard this before you know I know I just solve it already and here's how you do it or I've heard something like it whatever the case is you're not expected to know the answers you're not expected to solve the problems immediately either or even to code perfectly that's not to say that shouldn't be your goal and I want to make that very clear the you know faster you can solve the problem great the more perfect your code is great people often ask like is it okay to have a bug in your code and it's it's a very tough question to answer because it depends on what you mean by okay more you know I'm trying to evaluate your problem-solving skills and it's not a binary thing it's not you are good you are bad or I'm trying to evaluate your coding skills again it's not binary it's not you work good you are bad the fewer bugs you have the more quickly you solve it the more likely I am to think you're a great coder you're you have very strong problem-solving skills the point I'm making here is not don't worry about you know it was you know how quickly you saw but don't worry about bugs not at all it's more that the more quicker you're not you're it's not like not knowing how to solve it immediately it's gonna result in a rejection or having a bug in your code it's going to result in a rejection and of itself I rarely ever interview somebody who would I ask the hard problem to just says aha this is exactly how to solve it I've never heard this before but this is the I've just solved it right now and here let me write up perfect bug free code this doesn't really happen so shoot for that try to solve this quite quickly as you can that helps demonstrate good problem-solving skills try to code perfectly and all that but I just want to set expectations and don't want people to think that they failed and it's not a binary thing anyway but that they failed because they had the bug or struggled a little bit everybody's kind of struggling and most people have bugs what I do want to wade you want to look for is I want people as I said who are excited about solving a hard problem I want people who will drive through the problem as I said there's some people who are kind of mental lazy who see a problem and they have a solution it's work so that's fine maybe they don't even think about if it works they just the first thing there's like well here's way one way of doing it and they don't even think through what whether not it works I want you to drive through the problem I want you to look for a great solution not just any old thing so I want you to be striving for something that's more than just correct it's actually a great solution I also want you to keep trying when you're stuck for some interviewers particularly it's actually it connected me of like a big red flag if somebody says like mmm I don't know how to you know I don't know how to do it I don't know where to go from here for something over here that's a big red flag and I'm not quite as harsh about that but I understand their perspective what if in the real world somebody said this is a hard problem I don't know how to do it therefore I can't that could understand me big problem the real world too so keep trying when you're stuck getting stuck is normal it's normal to get stuck it's normal they have hard problems the thing is you want to keep trying even when you're stuck when you want to keep trying even once you have a solution make sure it's a great one look for a great solution next thing is pay attention to me pay the true what I'm saying I've interviewed a bunch of people held this actually pretty common when I at you know they give me a solution and I ask and they kind of you know give it to me and then they try to start coding and I stopped them but I say okay well hold on does it work and they think for a second they say yeah and I'm like okay that give them a couple more you know maybe fifteen thirty more seconds whatever trillion the problem to continue to think about and then I'm like let's take a step back are you sure that your algorithm works again they think they think yeah I you know again this happens over and over again pay attention to the things that your interviewers saying interviewers aren't saying things to confuse you they're saying things for reasons if they keep asking you are you sure it works that that's a sign right if they ask you are you sure you need to arrays maybe they're trying to indicate hey I let's try to reduce the space commit I think you can maybe able to get by with one eye right so think about the things that your interviewer saying I talked about this from the perspective of system design and scalability and design questions as well think about the points that interview are saying listen to them though you don't have to immediately concede if I say are you sure one array wouldn't be enough don't just say oh absolutely yeah I know you can do with one array without understanding how to do it but you just you just want to listen pay attention to the things that interviewer saying if your interviewer ever says the same thing more than once that's probably a reason all right that if I say more than once are you sure you only need are you sure you need two arrays I'm probably indicating you missed it the whatever I was pointing trying to point out the first time I said it you probably missed and so pay attention to this time so pay attention what your interviewer saying and then write real code sometimes interviewers are okay with pseudo code but it's unusual your expectations should generally be to write as close to real compiled able code as possible that said you know I'm not this is not a binary evaluation ultimately I'm not judging your code on percent correct or some sort of fixed number like that I judge your code based on the attributes I can drive from it what is it indicating to me if you are using a built in linked list class and you call the method add and it's actually called insert in that language I don't care personally like the fact that you called it add it's actually insert all that tells me is okay you're not comfortable enough with the new you haven't used the built-in link let's class that much recently okay no big deal I don't expect that you have I don't care at all about that personally now if you're writing double single equals for a comparison in a language that most languages that use a double equals well that worries me if you're not declaring your variables that worries me if you are you know not writing types in if you're operating in say Python right I plus plus when Python doesn't support that syntax these things start to add up and start to be a bit more worrisome so you know try to write as close to real correct compilable code as possible don't think that you know I'm not saying that one little issue is going to be equal rejection that's not realistic but you know depends on the issue obviously but try to write as close to real compilable code as possible and then before gone to the algorithm specifics I want to make this very clear show me how you think about the problem I'm trying to evaluate your thought process it's not you know I don't get a metric that says you need to solve the problem in this number of minutes or else you know and that will give you this score people often ask like how long do I have to solve a problems right it's 20 minutes enough well it depends on the problem and it's not about the time alone people can take more time and do better than somebody took less time it's much more complex than that but because what I'm trying to do is evaluate your thought process if you're not talking out loud and showing me your thought process I can't really do that I also you know I can't say wow that was a brilliant insight you made if you didn't vocal I that insight so try as much as you can to talk out loud if this is something that you particularly struggle with one most people who say that they have a really hard time doing this are actually okay here people don't struggle as much as they think they do but one thing to think about is if you can't tell me everything you're thinking about notice when you're being quiet and try to give me at least the headlines of your thought process all right so tell me you know when you notice yourself being quiet for a little bit hey just give me the headline know what I'm thinking about is how to optimize this piece what I'm thinking right now is how to you know get rid of the second array I don't think we need it so give me at least the headlines when you're quiet and focus on that that's something concrete that most people can do but as much as possible try to show share your thought process with me okay with that I'm gonna talk about how to actually solve algorithm problems this is a handout you can get at cracking the coding interview comm click on resources and you can download that you can also the same auto-response I mentioned earlier G at Yale comm the subject FB prep one word that'll also give you an otter I'll give you about such an auto-response you don't need anybody in the subject or in the email I at all just a subject to FB prep is fine so that'll give you a hand link to this handout I really really really encourage you to actually use this structure when you walk through the real problem it was prepared after doing a ton of interview coaching a ton of questions and seeing a lot of the mistakes people make and now you know when I watch people interview and when I do interviews myself a lot of the mistakes people make could be avoided if they just followed this process so walk through this structure and also Payton you I would actually have this out in front of you when you prepare and actually look through you know when you're stuck optimizing on optimizing go actually look through these different things at different things I say there they're there because they avoid a lot of the mistakes I see so I'm going to walk through this kind of flow chart you'll see in the top right again I really encourage you to focus here pay attention obviously and to use this when you're actually practicing problems okay very first step here step one listen now this is the kind of expected interview advice it's the kind of thing everybody says listen carefully to the problem make sure you've heard it correctly bla bla bla bla I agree with all that a hundred percent do listen to the problem do you make sure you've heard it correctly do ask any follow-up questions I'm saying one step further than that I'm saying listen carefully to what I said how I constructed the problem listen for clues there are often little clues in the problem and the interviewer may not even be thinking about them as clues but they are often clues a clue is well taking a step back interviewers tend not to give it give you information you don't need so every bit of information the problem nearly they try to simplify problems as much as possible they try not to give you information that's irrelevant these are there exceptions but they try they tend not to do that a whole lot so generally speaking any information given in a problem is there for a reason so that means if you hear something and you think I don't really need that I can solve the problem without that it probably means that you can solve it but you can't solve it optimally every bit of information should be generally useful for something given it I'll give a hypothetical problem you have to erase sorted and distinct how would you find the number of elements in common between the two arrays so do you construct the problem you have to find the number of elements in common okay well that's the question itself that's why I gave that information obviously you can't solve the question if I didn't state what the question was you need to find you you're told that there are two arrays well again you couldn't the problem wouldn't really make sense without knowing that there's two arrays yeah you need to know how many arrays there are in order to find the number of elements in coding okay so it kind of makes sense why I told you that but why did I tell you that the data is sorted even with two unsorted arrays you could find the number of elements in common so that likely means is that the fact that the data is sorted actually changes the optimal solution yes you can find a solution even it's unsorted but it probably changes the optimal solutions so pay attention those clues I'll give a different example of what a clue might look like this is a little bit different scenario so you first of all starting off with the definitions an anagram or the anagrams of a word are all the permutations of a word that exists in a dictionary so for example the anagrams of rates are astra ter ser to astro stare tasers and tears so the question is how would you build an anagram and as I state this pay attention to the clues see if you can figure out what the clue is how would you build an anagram server or website so given a word you want you're given some list of valid English words and you want to print all anagrams of that word so if I soar printer returned so if I said rates then you'd new returned your server or website would return a stressed air teaser there Cheers so how would you design that website or server and I'm gonna preface this with saying this is an algorithm problems not system design so let's look at the information I told you and what I've put in the problem so I told you you need to I told you what an anagram is it's pretty clear why I did that it I can't really ask you to do something if I don't tell you what the term means okay I told you that you need to print or return all anagrams that word well that's the problem itself I told you that you're given a list of all babbling Schwarz again the consequent anagram is permutations that exists in dictionary so clearly you need a dictionary ah so make sense why give you that but why put it on a server why not just say I mean I told you it's an algorithm problem anyway why not just say okay write a function that given a word and a list of valid English words prints all anagrams that word why did I say go do this thing on a server though likely what that indicates is hey the fact that's on a server actually changes the optimal approach so what does a server let us do well allows us to have additional resources like databases or things like that it allows us to cache things one of the things though is that a server let's just pre compute and if you look at that if you look at the anagram some rates Aster's stare to tears these all sort to AE rst so that means is if you took your dictionary and your server when your server boots up you can do this pre-computation step of taking your dictionary sorting the characters in every single word and then grouping all the anagrams together so when I say give me the antig Rams of rates I can say okay great I'll pull out the arst grouping and I'll pull out all those words assorted to that that approach you know it makes it super fast on a server we can do this pre-computation it's weird to run through all the words but if we do that once that's not a big deal and then when we say give me the antig Rams it's going to be really quick to do that this pre-computation step makes it the server approach really fast if it was just a single function run once the pre-computation step wouldn't make any sense there'd be no reason to build this whole anagram you look up thing if I only wanted a single one so the server piece is incredibly important you cannot do this pre-computation optimization it doesn't make sense to do on a single like without without being on a server or something like that so paid into these clues if you miss the clue then you kind of can't solve the algorithm without that at least not optimally it's a paid inch of those clues and if you ever think you might have missed something the problem feel free to go ask the interviewer what the problem is or shade it back them in your own words you know this goes back to what I said in the very very beginning about hey your interviewers on your side they're not trying to like trip you up but with something like this if you think you forgot something or you didn't get all the details just ask just clarify it's fine okay step 2 really really really really important piece here and something that it's such a shame having people don't draw examples so don't make as much use of them because it's such a simple thing to fix just draw an example and make your examples large and avoid special cases it's really really common for people to miss here a problem and I think what happens is that people get nervous it's an interview it's intimidating and maybe it's that when you when an interviewer states the problem they get kind of caught up in oh my god oh my god oh my god are they gonna ask me really hard problem and they miss some detail then they can miss and they can interpret the problem in a very very strange way even when the problem was actually perfectly clear so draw an example an example is one the most one of the first times when I'm like no you actually misheard the problem so you know I say you know that example I gave earlier with and think when I do this about what kind of example you might draw for this you know two arrays sorted and distinct find the number of elements in common I'll see people draw examples that have like one array and then it's very clear that doesn't make sense so draw an example get the input the output would be four that helps to clarify that you actually heard the problem correctly but to make good use of the example make it large and try to avoid special cases as much as you can so for that problem I just mentioned two arrays sword and distinct find them or elements in common most people draw example that look kind of like this two arrays great okay yes so sorted yes so they have distinct elements but they only have four elements so they're tiny and they're erase the same length and I never said the Rays are the same length and they only have one element in common it's you know yes it's an example but it's a bit misleading because the arrays are not necessarily the same length and it's also very small and so it doesn't help you walk through your example your algorithm very well a better example something like this much larger so that you have like six seven eight elements they're not the same length they've multiple elements in common that's the kind of thing you should look for the idea here is an example that is complex enough that your brain has to do at least a little bit of thinking so compare this to say something like reading if I just like point to a word like big as soon as I point to it you'll you will have read it you can't like turn off your brain from not reading it right like you've read it by merely a glance likewise with that first example with two arrays of length four as soon as even if I didn't underline the element common as soon as I point to it you will basically notice oh they both have a 12 right there you're not going to learn much by trying to walk through and do it by hand something like this with your two arrays six seven elements your brain has to do a little bit of study how to do a little bit of work to get the right output that's the kind of example you should look for so something that's a little more complex and meaty this is when the quickest fixes to avoid a lot of problems down the road make your examples large and avoid special cases okay third step is get a brute-force naive algorithm very very very very important here don't code this I'm not saying to immediately say an algorithm and go and code it just state the algorithm well you know one brute force way of doing this like this that'll have this run time but I think we can do something do something a little faster so I'm not saying go immediately code it please don't do that unless your interviewer wants you to you can always ask your interviewer is not trying to like you know trick you or test when you which album you want a code like that you can always ask her out your interviewer here but you know just practice your you know just state when you have a brute force naive algorithm just go state it and say if the runtime and go into optimizations the most important message I want to get across here is it's okay for your first algorithm to be slow it doesn't have to be a perfect ballad limit first I'm not you know it just wouldn't be reasonable to expect that I would know with a really complex problem you'll immediately know how to solve it these are supposed to be hard challenging questions so the first thing you come up with it's okay state it even if it's really slow the reason why this is so important is first if you did miss here the problem the brute force algorithm will often make it clear that you misheard it and yeah it's unfortunate you misheard it but it's much better that we realize this thirty seconds into the interview than fifteen minutes in and often your brute-force algorithm I'll be able to say that doesn't really make much sense and then it will realize you misheard it it's also really important because not everybody can develop a brute force sometimes you know there's some problems where the brute force is actually really challenging there's other problems where the brute force is the brute force that's pretty obvious and there's still some fraction people who will struggle to get there so you want to make it clear that hey you're at least of that level thirdly and perhaps most importantly it's important because it's a really good jumping-off point a lot of optimizations can be made by starting with the for us so start with the brute force again I'm not saying to go and hear you come up an algorithm immediately go and code it just state it state the runtime and then you can ask if they want you to code or keep working the algorithm usually you'll want to keep working on the I'll give a bit more then go and optimize it so you have a brute force go try to optimize this algorithm or come up with something better I'm going to talk through a couple different ways of optimizing algorithms very first one I'm going to talk about is called bud now when I talk about these approaches actually try to practice using them when you're preparing and in the interview themself so bud is one the first one is the first one this means to look for bottlenecks unnecessary work and duplicated work bottlenecks all right so our first job first problem we mentioned earlier to array is sorted and distinct by the number of elements in common between the two arrays the brute force algorithm here you imagine on McCann as I'd say ok well yeah I draw this example and say ok well you know one way of doing it is just walk through the first array and for each element the second in the first array that'll the 3-chome in the first array walk through the second array and look for it and if it's uncommon and commit the intersection and that'll be of course on a a times b runtime but i think we can do some do something a little faster so that's like that you know step 3 or never the brute force save the brute force state the runtime optimize it and notice here that the runtime is ov a times B not N squared ok so you have an OB runtime and this that Bo of beast thing that we're doing a times that's the bottleneck and for every ailment a we're doing OB work so I've gotta find that bottom I can get rid of it so ball neck is this searching for each element a we look through B that's OB time well how do we make these kind of lookups or searches or sweeps faster well we could throw everything and B into a hash table or hash set that'll be of beats time to do that but then each lookup is only off one so that'll give us an of a plus B run time and B space complexity we could do we could do a binary search here on B so that'll be an O of a log B runtime and then oh of and then over one space complexity and then or we could walk through B and a and B with two pointers kind of like doing them sorted and you're merging two sorted arrays so walk through a and B of two pointers and that'll be O of a plus B runtime and O of one space complexity so the technique here is identify that bottleneck in the in the brute force or your an algorithm and focus on you know figure out where is that ball not coming from and then how can I get rid of that okay next thing to look for is unnecessary work so new questions this is a question I've asked a bunch it is not a math problem despite how it might sound there's nothing more than like very basic math use now just the question is given the equation a Q plus b cubed equals C Q plus D cube find all solutions ABC and D that are integers between 1 mm so I want to find all the solutions great okay just walk through what well you want to find all the values of a b c and e that work fine walk through all possible ABC and DS and look for matches so that's four nested for-loops this gives us a runtime of n to the fourth and you know we're looking at this again you wouldn't have so draw right out this brute force code but I'm just doing for demonstration purposes so you have four nested for-loops and within this we might notice okay well you know we can make this a little bit faster by throwing a break statement here after the print doesn't change the big o time it's important to note that but - well dude it's easy it's fast it makes a little bit better so throw in a break statement here but what that indicates here is that well wait if we're saying we can put in the break statement what we're saying is that there's only one value of D that works for any given a B and C so yeah not only can you break break once you find that value of D that works but if there's only one value of can we find it more quickly and you can imagine a were seventeen and B were 53 and C were 32 if I just gave you that if I just told you seventeen cubed plus wherever I said 53 cubed plus 32 equals 3t cubed plus b cubed yeah I think I don't know when you learn this seventh grade you need a solve for D so D is a cube root of a cubed plus b cubed minus C cube just solve for D so that's necessary work a lot of times the necessary work is kind of comes up when it's like oh it breaks him and here are some minor little thing that may not even change the big o time but it triggers a bigger thought about an optimization and this one drops it down to N cubed better they're not still ideal let's jump back to the brute force another thing we can look for is duplicated work so if we look at this brute force will notice what we're really doing is saying okay for every a be pair walk through all generate all the city pairs and look for matches on their cube sub so times when CDs what I'll call cube some matches abs cube some then I change the a B pair and generate all the CD Paris all over again look for matches new a be para generate all the city Paris look for matches etc we're doing this CV work over and over and over and over again it's the same list of pairs every single time so maybe we should think okay well can I just take that CD loop pop it out and just do it once so this is the table this is like all the CD pairs that we walk through and then this here's our cube sum and so what our algorithm is really doing our brute force is saying okay 3 KB essentially generate this whole list and then look for times when a B is cube some appears over here and if we were to only do that once we would probably want to just be able to look up on this column right so what if we had we took those CD pairs and actually just up front rather than walking through this list every you know this hypothetical list every single time what if up front we just said okay let me just generate all the CD Paris and put them into a list that maps a hash table that maps from a cube sum to the parasite got us there then when I have an a/b pair I can compute that cube sum and pulled it out of a hash table and that's what this does appreciate for each CD put it into a hash table that maps from a cube Sun to the pair that got us there and then free JB just pull up the results pull the matches from the hash table that drops us down to an N squared algorithm even faster though or even different way not actually faster but differ way of doing it is we could even notice that these ABS also go through all the pairs between one mm so that means that they're these a B pairs are actually already these a B pairs are actually already in this hash table here so rather than you know once we generate this all the city Paris we can actually just use the hash table directly and walk through all the groups in that hash table so that's duplicated work notice when you're doing something over and over again and see hey is there a way of reusing this work of it that's bun alright next approach is looking for space-time trade-offs this is one of the most common things a lot of problems involve hash tables in fact so many problems involve hash tables that I'm not even gonna give a special hash table problem here because so many problems already involved that but I'll give a slightly different version of this which is more about pre-computation so new interview question you have a matrix of positive negative values and you want to find the sub matrix or this sub rectangle that has the biggest sum where it has to begin the top left corner all right so we want to find the rectangle with the biggest Sun that begins the top left corner so well step 3 right was a nice generate you know any solution no matter how slow we're going to find the back pain with the biggest some fine that aren't all the rectangles walk and compute the sum of every single one and then just pick the biggest one it's slow but it'll work now let's walk through that and think a little bit more about what that does what it means that we're doing is we're saying okay get the sum of the six that's the first rectangle next one it's the six and five so add up the six and five next one is the six five negative nine so add up six five negative nine then six five negative nine two cetera et cetera et cetera we go down here 6 negative 2 3 6 5 negative 5 to negative 2 3 negative 2 add up these six elements now we're adding up all of these 9 elements we keep adding up the same things over and over again we added we're like saying add up these 9 elements and but we just added up 6 of those elements so I mean no reason I'm going going through no reason to go through all of these out of all those 9 elements when six of them we already did right so let's at least reuse that work this actually relates a lot to the duplicated work I talked about earlier let's reuse that work we already added up these six elements but now what about these other ones well this negative five nine negative two well we didn't add up all of those elements yet but we did we added up these top six also so we could try to use that rectangle as well except that we'd be double counting the 6 5 negative 5 negative 2 so what do we do well that one we added up earlier till so if we want to know the sum of these like nine orange elements that's gonna be some of this blue rectangle here that we added up earlier we already have a sum to that if we if we store all our prior answers we already have the answer to that plus some of this green rectangle which again we already had that the answer to - the only problems that were double counting this red square what we already add up that square so let's just take out that one plus this last one so that's gonna allow us to pre-compute this then we can do it the next one the orange elements is the blue rectangle which we just did now plus the green one which we did earlier - this overlap that we're double counting so that's pre-computation if you do that in this case you can get a much more awful you can do this in n-squared time it's an n-by-n matrix so because we can get the sum of each rectangle and given the prior ones in constant time so on a lot of problems there's optimizations involving hash tables or pre-computation so pay attention to those third approach this is one of my favorite interview questions and it turns out one of my favorite approaches so new question you want to find all the permutations of s within B so we've two strings s is a smaller string B is a bigger string find all permutations of s within B all right so um one thing here is I like to use logical variable names so rather than using like a and B m and n some point that for variable names I like to use logical variable names whenever possible there's a little little tip avoid some confusion so s is small string B is a big string find all permutations of s within B I've asked this problem dozens of times now and pretty much everybody you know 95% of people pretty immediately have an algorithm that is okay well brute-force find all permutations of s look of each with and B it's slow but it'll work right but you know then they get really stuck they get the run time use there's some help and they realize it's s factorial times B that's really really slow if you go back to the ball next to necessary work to placated the work that s factorial is a bottleneck you've got to get rid of that I'll see a lot of people who will you know start thinking of the realize it's really slows X factorial that's how I look really really really bad it's way worse than exponential time then they'll and they won't kind of prioritize things right they'll see X Factor all the times B and they'll start thing oh maybe I can take this string of length B and I can throw into a try I can do this as a man maybe I'll be able to get down this B time and in some ways you can you it's kind of silly because s factorial thing is just gonna kill your run time it's got to give me the best factorial which means no generating all the permutations anymore it's got to get rid of that so late let's take a step way back to step two which is just get an example all right so we want an example of s and B and so again the the idea here can you hear when you get an example is generate an example have it be big one and try to avoid special cases and then you should get an example then you just you figure out what the output is so this is this is an example s this is an example B as I do that as I talk about this look start looking for the permutations yourself so this is s and B I looked for here attention we made the example I made be really big and I also made s s could have been a little bit larger but I made it on the larger side and I also try to avoid avoid special cases so I made sure that s was not all unique characters this is s and B so that's our input and now okay well we need the complete example involves output so what's the output well you just want to go through and find all the permutations of odd of s now what's interesting here is I've done this dozens of times looks looking at my underlining a little bit messed up but I've done this dozens of times and pretty much everybody can find all the permutations of s nobody really has problems with it but what's even more interesting is that I've asked this dozens of times again nobody but pretty much everybody comes up with this algorithm that's find all permutations of s look up each with and B nobody has yet after dozens of interviews with this actually use their own algorithm to solve the problem themselves no we does it this way nobody says ok all the permutations ask so that's gonna be a BBC and ABC B and a CBB and this isn't this and all 12 of those permutations and them goes and looks for every single one of those drinks nobody does that because you don't want to hold all the stuff in your mind you know that coming up the permutations is just gonna take a while how much everybody doesn't much more logical thing of just walking through this and looking the first four characters is this a permutation and then going to the next is some permutation is there some permutation is a some permutation and depending on your algorithm to you do the is this a permutation check your going and run time that's hopefully s times B may be as bad as s squared times B either way way better than s squared times or s factorial times B this happens for a lot of problems one of the easiest ways to solve a lot of interview questions is just give yourself a nice meaty complex example it's part of why I pushed that so much on step two just forget about computer science forget about algorithms and all these other stuff act like you've never programmed before get the output however you do it just get the output then trying to verse engineer it and really think okay how did I do that I really did was I walked through every four character s and B what I really did was I looked for all the A's and then look at the surrounding characters so use that technique get a nice big complex example and then figure out okay what did I really do this is one of the most useful and Keynesian techniques to apply in algorithms last technique I'll talk about is recursion so there's four things I want to say about recursion the first thing is you have this instinct of this problem sounds recursive a lot of people have that instinct great instinct to use it don't cling to it a lot of time you're about half the time when you think this problem is for is recursive it's not so use it because it is a decent rule of thumb you'll be right at least number of times but be prepared to realize maybe it's not second thing I want to say is you can approach recursive you tend to implement recursive recursion top-down but you can implement it both bottom-up and top-down or you can not solve the problem both bottles and top-down one approach might work better for one problem one might work better for another however what I've found doing a lot of recursive problems generally but bottom-up works better than top-down not universally but generally it works better justin to Rive the algorithm because people just think better people tend to think more clearly concretely so you know that bottom-up means you have these base cases like empty set a a B and then you say okay how can i generate all subsets of ABC for any of these prior answers that's bottom-up it tends to work better third thing I want to say is when you're solving a problem and you think oh jeez I'm gonna need to do and go this way but then I'll need to potentially backtrack whenever you think backtracking think recursion that tends to be how you implement it and people can get really really stuck on trying to figure out these very complex ways of backtracking and tend that tends to lead to a recursive approach so just kind of remember that instinct last thing as I mentioned when I was talking about Big O is think about repeated subproblems when you when you're trying to get the read time draw out a call tree and look for repeated subproblems that that tends a useful way of getting the run time okay so those the four major precursors or four major algorithm approaches I wanted to mention use those techniques solving problems they are here because I've seen them come up again and again and again so use them practice them when you get a you know when you get a problem push yourself it's not about do you know how to solve this problem initially it's about can you drive through it can you solve the problem so really push yourself the problems are going to be hard once you have an algorithm don't just like say okay I think I basically understand it now I mean the start coding I see it over and over again messes up people a lot take a moment to walk through your algorithm one or two three last times and make sure you know exactly what you're gonna write I'll interview a lot of people who three four or five lines into the code are thinking about what their data structure should be that's a big problem you should know your code to the level of what all these data structures are and when they're when exactly they changed you should basically be able to picture your code before you start writing because you're not going to write all of that much code so take a moment know exactly where you're going to write before you start writing rushing does not help you out all I promise when you start coding your goal is not just correct code that's one goal but you actually want to demonstrate good coding style so you want to write beautiful code a couple quick things here some simple little handwriting things first try to write straight you know I'm not judging your handwriting no interviewer would generally judge your handwriting but if you're writing and your lines are like at a sharp angle that can present some problems they'll make your code more confusing you're gonna get confused especially in a language like Python where whitespace is significant you'll start to forget like which line of code which code block each line of code is under so try to write straight when possible give your make your life easy give yourself as much space as possible to write code so - usually it's a top-left corner but right wherever wherever you have the most space you can erase stuff on the whiteboard that you don't think you need anymore if you need to insert new code don't like erase three lines of code that'll take you a long time to rewrite you can just use an arrow it's fine it's not a big deal more important things think about error cases think about - duze things like that if there's a whole bunch of little boundary checks and things like that you may in some cases want to just write it to do and explain out loud what you do rather than writing out like a whole bunch of boring boundary checks if there's a bunch of them next thing variable names super important look we only have as interviewers like 10 20 lines ish usually to judge you on so one of the things we can always evaluate is variable names it matters in the real world so use good variable names the problem here of course is that this can be verbose if you're writing out the good variable names like number of children handwriting is slow right so the compromise here is the first time write out the long variable name and then for each variable write out the longer variable name then after I've already written number of children I might later on just abbreviate that as NC you can always check with your interviewer to see that they're okay with that the most should be this is not pseudocode it's just abbreviations language trace generally speaking up to you use whatever let's language you're most comfortable with don't try to like pick a new cool functional language just to impress your interviewer use whatever language you're most comfortable at their trade offs of every language it honestly doesn't matter that much which language you pick but be aware of what those trade-offs are because there's often ways of handling that for example Java known for being very verbose a lot of people don't want to you know it's very readable in that lots of people are familiar with this syntax but a lot of people kind of shy away from in an interview because it's you know very proposed the Rossi isn't that big of deal you can use abbreviations so rather than writing out something like hashmap string comma integer my hash map equals new hash map string comma integer you might just check with your interviewer and abbreviate it it's just hm s comma I my hash map equals new dot dot literally just new dot dot dot your interviewer will probably be ok with that and this allows you to avoid a lot of the verbosity this isn't pseudocode is just an abbreviation that works well for languages like Java Objective C things like that if you're coding in a language like Python Ruby JavaScript people who code in that language the issue I see a lot is that they gloss over the runtime of the different functions they call so you know I'm interviewing a Python coder and they had a recursive method that at each level of the recursion pops off an element of the string and they're not really thinking about you and Python it's like something really short like s or you know STR whatever my string is s bracket 1 colon bracket pops off an element the string doesn't look like a big deal and they're not thinking about the fact that that is probably a linear time method that means that their algorithm that maybe they thought was Oban is now actually of N squared so you know and there's usually ways of avoiding this maybe they could pass an index rather than popping off an element but think about you know to be very careful when you're using built-in methods this actually goes absolutely just as much for Java coders and objective-c in other languages but Java it's just so much more obvious that you're like calling like you know create this new string it's very much it's much more obvious so Java coders tend not to make the same mistake as much just so be just very aware of the runtime a few of the different functions you call and you can usually just think about what they would be you know if you're popping off and creating a new string probably linear time but again it doesn't matter that much what language you pick use something that you're comfortable with mostly though it's up to you the only exception might be that sometimes if you someone's interviewing you for a very civic role like a you know i OS you might be expected to code in a specific language but this is always on this thing so you can just ask this isn't something you need to you know guess that just ask a very important thing with coding and a way to make your life much easier modernize your code it's just it helps in so many different ways the code a lot of you write code that looks like this one giant method so this is a little function that generates or walks through I won't get into the details of it it's called the rants note net ransom note algorithm or interview a question you can look it up but this is an algorithm that basically processes one string process another string compares the results this is what a lot of people write and it's not a very good idea first thing instead that you should write is that method the overall method of method and look in the like the first thing you write is a function that is essentially the answer to the question so and then you just prepare pretend everything in the entire world exists and especially the functions that you might need so I need a function that you know this my step was my process was process one string process another string compare the results so that's the first thing I write those first three function calls from here on out it's just filling the details I got the skeleton of the code out just fill in the details whenever I get you know I go I go into the next my next function I write is the next most interesting algorithmic part so if I need a function that converts a character to number like a 2 0 B 2 1 C 2 2 then that's then that's not something I really need to write in line that's a very concrete chunk of code pushed out to another function don't write it in line then I'm just you know filling the details this is really nice to do it makes your life much easier it's much easier to kind of conceptualize all the different pieces if you're not writing out the details of one before you run out the structure it also makes it devastates good coding style makes it easier to test it just makes everything so much easier and very often your interviewer might say and don't worry about spending your time on this one function it's not that interesting so madres your code and keep an eye out for any conceptual chunks of code push this off another function if there's like two steps first I do this then I do this push it off to another you know push those off to separate functions if I am writing code that needs to get first the biggest cell in the array then the smallest then I you know do something else with that I would just call that as a method get max get min and then write this other part so use modernization to your advantage it'll not only make you a demonstrator coding style but it also make your life much easier so monetize your code very important thing I want to make very very clear here is modular code top-down not bottom up Oh sometimes people who take this advice and so the very first thing they write is this little helper method and that's completely the wrong thing yes your monitor eyes and that's great but now you're spending your time on like the helper methods at least important things start top down not bottom up this isn't one little major questions people ask is do I need to know you know do do can I just call the built in API so do you need to write everything from scratch if you approach your code this way it largely avoid this issue assume the built in API is a to your you know are at your disposal you can always ask your interviewer but assume those are at your disposal assume anything with higher world you want is at your disposal you can use whatever you want and then just fill in the details okay last step testing your code it got a test your code very important a lot of people don't do this you gotta test your code when you do it don't just throw in a giant test case that you know a lot of people will just take that example up on the board and throw that in as a test case immediately and it'll work kind of it'll take a really long time instead analyze your code think about what you're doing really really think of your walk through line by line by line think does this what is this doing talk out loud explain the process of your code double check anything that looks weird any math things like that any addition subtraction multiplication division double check those things if those are the kind of things that cause problems your for loop decrements the set of increments you did it for a reason but double check that it's a right logic then start with small test cases not big ones small test cases work pretty much as effectively as a large one they're just way faster to to run then throw in some edge cases and then when you have time some big test cases to last things I want to say with testing test your code not your algorithm seems obvious and yet a lot of people don't realize what's happening I'll see people who you know their algorithms over on the left side or their examples over on the left side their codes on the right side and they if I were to ask them they tell me they were testing their code and yet they're not looking at their code they're actually just walking through their example that's validating that your algorithm works it doesn't value that your code does what your algorithm should be doing so make sure you're testing your code not your algorithm then when you find a bug don't freak out it's totally normal most people I interview have bugs in their code again better to not have bugs shoot for bug-free code I just want to make it clear that's not like oh you have a bug now you're gonna get reject it doesn't work like that when you have a bug don't just rush into fixing it make sure your fix is the right thing if you notice for example you know there's a piece of code that people that a permutation problem where you're looking through for all permutations of s you're walking through B and Windows of size ask you know is this a permutation source of permutations of summer vacation people usually write code that looks like for int I equals 0 I less than B dot length my set length I plus plus you know to walk through Windows of size s and not run off the edge of B make sense Niklaus I'm so glad it looks right but then they throw in some test case or a beam s of the same length and they realize uh-oh I run until I is less than B dot length minus s dot length that means I be an S to the same length that means I run until I is less than zero and therefore my for loop never gets increment never gets hit at all uh-oh and they think that their bug was when B and s are the same length and they make some initial fix in the very beginning that says okay if B and s of the same length do this other thing but that wasn't their bug their bug was actually an off by one error in every single call regardless of the length and B and s they have not by one error the logic actually should have been I lesson B dot length nice s dot length plus one easy mistake to make it really easy bug to make I'm not that concerned if somebody makes that bug if somebody has a bug in their code I'm but I am concerned if when someone finds a bug they make the first thing that'll fix that test case and they don't think through what really caused the bug because that person is much more dangerous that person gets test gets bugs reported to them closes the bug because they think they fixed it they just made the code more complex and pension changes new bugs and they didn't fix the new the actual bug that person is much more dangerous so when you find a bug just don't don't panic think three realize it's kind of normal think through what caused the bug and then fix that suppose the seven steps to solving an algorithm an algorithm coding problem use those steps walking through the problem so when you're going through this actually walk through and say oh right Gail said in step seven I need to test it oh right Gail said to analyze the code look for you know little things like off-by-one errors first then go to small test cases then edge cases then big ones actually use that process very last thing before we wrap up questions for your interview for the most part you know you the majors and you're like you know here is you should ask your interviewer some questions at the end the interview you'll get a chance to ask you any of your questions have something prepared people stress far too much about what the right questions are to ask ask the things you want to know honestly you know it doesn't doesn't matter that much as long as you have something to ask asking questions shows you know curiosity shows where your interests are your passions things like that so you should have some questions to ask it doesn't match what they are that said people always want some specific ideas here's what I'd say here's a way of just generating questions think about what's made you happy and unhappy in your past jobs that's just new and that may lead you to a question to ask so for me I don't like I haven't been happy jobs where I'm not given as a developer more influence over the feature set so that's what I'm gonna ask about what kind of influence do I have I'm gonna ask about how long it takes to launch because I'm happier when I can launch faster I might you know asking about my you know think about what your goals are ask questions around there you can ask questions around a lot of different areas but some of those common things is asking about the culture and work styles the things like you know test-driven development those kind of technical things you can ask questions about the career paths and career goals and then you can also ask question about technology so that might be you know which technology you use interesting might be interesting technical problems things like that again you know have some questions ready ask things that ideally you actually want to know don't stress a ton about this but these are just some ideas of that might get you thinking about what the right things are for you to ask all right last very last final thoughts here remember that all of this everything about this process is done for a reason and that's to identify people who'd be successful at Facebook so yes that is about technical strength it's also about you know how you are you in the comparison you'll be successful or you can you work effectively on a team so remember the kind of softer behavioral side as well as the technical side the last very rarely last little details if you're ready to fall through your if you're ready for an interview go ahead and fall for your cooter for next steps and then slides are online gale calm click on events and search for Facebook or you can set you an email G at Gamescom the subject FB prep and you get a link to the slides the handout I mentioned earlier and some other things so as I said handouts online auto-response or go to crack and coding interview dot-com there's if you want more in big oh there's a big section crack encoding interview in the six Edition for that so you can go read that as well and there's some exercises there that's one of the first things I would encourage people to do is just really really master Big O cuz it's so foundational there's also a ton more problems in crack and coding interview if you're looking for more questions you can find more on career cup and online as well but do do the best you can to prepare and just remember that this is you know this is supposed to be a chance for you know yes for Facebook to evaluate you but also for you to evaluate if you think that this would be a place where you would be effective so do your best to prepare and walk into the interview hopefully comfortable and happy about the process you're about to go through Thanks

Channel: Siamak Sobhany

Views: 141,800

Keywords:

Id: wCl9kvQGHPI

Length: 109min 9sec (6549 seconds)

Published: Sat Sep 29 2018