Cracking the Facebook Coding Interview Problem Walk Through

okay thank you guys for joining us today what I'm gonna do today is walk through a actual interview question this is one I've asked a number of times fact I've asked it probably 10 times already this week it's only two days into my week so that's a ton of times and I'm gonna walk through a process let me give you kind of a process for how to walk through a problem and show it on this exact this specific question so if you hopefully you already saw the earlier video of how to walk through a question but if you haven't or you have I have a flowchart for how to walk through a question you can get it at if you send me an email at G Gail comm with the subject FB prep so that's G @ GA y le comm such a subject FB prep it's an auto-response so you should get it pretty much immediately you can also download it at cracking the coding interview comm and click on resources so I encourage you to follow this flow chart for solving a problem both in today as we walk through this problem as well as in general so the today's question is the following you have a group of people with their birth gears and deaf ears how would you find the year with the most number of people alive now I encourage you to pause the video at this time and give yourself a chance you know that can be five minutes or it can be thirty minutes to try to solve it design an optimal algorithm and actually code it yourself so I'm gonna walk through it you know I obviously know the answer so it's slightly unrealistic so you know it's gonna be a little bit faster than the typical candidate would solve it but I just want to demonstrate the flow of a question okay so the problem again is given a list of people with their birth years of birth years and death years how would you find the number of how would you how would you find the year with the highest population so the year where with where the most number of people are alive so very first step on this flowchart I'd have it out in front of you very first step is listen carefully the problem make sure her correctly identify any clues so let's just value that we've heard it correctly so you might want to repeat back to your interviewer at this time okay so you know you want to find the year with the highest population you might validate some assumptions like I assume people aren't necessarily alive all at the same time you might also ask some questions about what data structure the data is coming in is it in our array is it you know what kind of data structure it is that there's a reasonable follow-up questions to ask the answer that the interviewer if the interviewer is me will give you is yeah you can know probably you know an array is fine to the list of people but you can use a different data structure if you want and yeah we just want to find the year at the highest population people won't necessarily all be alive at the same time and looking through the problem there aren't really any clues in this particular problem okay step two draw an example so let's let's think about this so we want people a lot of people time so I'll see people to say like oh okay Bob is the first person he is born in 2000 and dies in 2010 it's a very morbid problem Chris is the next person you know when you draw examples yes draw a complete concrete interesting examples but also think about what really matters I don't really need the names of people and then so I'm not going to spend a bunch of time writing that if I really want to I can use like p1 p2 but the names don't matter so I'm just going to draw the birth years so 2000 to 2010 1980 to 2005 is another person in 1975 to 2003 this is the kind of example that I see if from a lot of people think through this carefully did this fit what I told you to do which is a big example and not a special case first and this are you know this is birth years and death years first this is not a big example three people is not very big also it is a special case everybody's alive at the same time that's not good like that's something that's not the generic example that you need that that kind of example will really trip you up for this problem but additionally it's sorted so that's gonna be a problem in fact it's sorted in two different ways first of all the birth years are sorted but ditional II people die in the order they were born also that's a special case that's not a realistic example you want something as generic as possible so I'm gonna make some people born in a much bigger time span so here 1803 to 1809 1750 and this isn't necessarily realistic in the real-world sense well that's potential you I'm you 119 years feasible I guess I want to make sure my data is out of order so let's make 1842 1935 now we're starting to get a little bit bigger 1860 to 1921 just doing random examples 1894 218 1900 you know I want to throw in some duplicates in here that'd be good right I don't want to pretend like everyone has this board different year so I want some duplicates here you know I think I want some others too I'm gonna make this like that to be 75 but I want to make this 75 too I want some other duplicates you yeah cuz this generic enough well probably will make a difference but let me be really careful but these two are the duplicates are adjacent to each other I don't really want that to happen so let me make let's say I don't know 1840 let me make mmm what you wonder I want to make let me make this 1803 so people have very long lifespans apparently in this culture so now we have some duplicates they're not adjacent anymore this is starting to get a lot better okay so step two I think were pretty good right now we can always fix up the example later on if it's not quite right but I think it's pretty good we have an example we avoid try to avoid special case as much as possible and and it's you know fairly large you know eight elements right that's that's fairly large that's pretty good okay step three come up with a brute force so let's go back to the problem the problem is given a group of people find the year with the highest population it's a year or the most number of people are live okay well brute force so well one way we can do it is we could go through all years that are potentially possible and look for the year of the highest population alright so go through every year check how many people are alive in that year and then get the highest population that they'll get the pick that wants the biggest of that how long what will that runtime be well first we need to go through all of the years well let's see here so that'll mean we're gonna go through 1750s the earliest up through 2010 right that's the last death here so then we're gonna check every single year between then so first thing we'll have to do is get the minimum birth year and the maximum death here each of those will take O of P time so getting them in bit Berthier getting the max death here those are each of p steps then for each of those years so it's o of P because it's basically you know find the min of this find the max of that so P is number of people so each of those are oh of P snaps then we have to find walk through the bet range from the min birth here to Max death here and look through all the people to see if they were alive at that time so that's gonna be O of Y where Y is the range from you know in this case it's it's a range from the when the first person was born to the last person died so that's gonna be seventeen that in this case I'd be like seventeen fifty through twenty ten and then for each of those years we're gonna check to see how many people are alive then so that'll be oh of P plus of P plus FY times P then we need to find the one that's the biggest this can either be done while we're doing lista stuff or we could separately find the max if we separately found the max they would just be another FP so that gives us a run time of o py plus P okay so let's think again okay so we're finding the min birth here let's walk through all the people find the max at zero of P Y where Y is the rate the year with the highest population or Y is the range from the first birth year to the last death here and then we're checking to see how many people are alive in that time that's a with P and then we have to go through and find the one that's the biggest well actually wait that's not P so we have to that's why it's so important to walk through that very carefully so if we're doing that for each year well it kind of depends now on our implantation and this is one things where you have to think carefully about how you're implementing it if you're using a hash table or something like that - well really depends so if you're using an array where you have you know an array of each year from you know 1750 to 2010 then you're gonna have to walk through that array or you might be using a you could be using something else like a hash table in which case you may be just walking through the you years so it depends on the implementation in either case we can certainly do it at the same time as we're incrementing these years so it shouldn't impact our run time we don't necessarily have to do as a separate step so total run time add up these is o of P plus P times y and that ofby great okay so this algorithm is walk through all the years from the first birthday to last step here County Helen people are alive in that year it's a brute-force I don't necessarily go and code it I might ask my interviewer hey do you want me to code I think we can have I think we come up something at more optimal and yeah we can here so I'm gonna do this I'm gonna say okay it's a little stuck right now so let me walk through this problem let me think about what I'd be doing here well if I were to actually be solving with this algorithm I start with 1750 and I only have one person alive this is kind of my album goes right now 715 fifty of one person alive 17:51 I actually know that that's the same there's no one born in 1751 fifty-two da da da okay so 1803 maybes the next one and then 1803 one person live o - two people alive three people live now this is where I step and say hold on wait wait what did I actually just do I thought I was walking through my algorithm but I didn't I didn't actually when it got to 17 I started 1750 and I said okay how many Pilar live in 1750 I knew the answer was one I actually just did something kind of automatically I got to 1750 one I said oh I know nothing happened then it's the same one in 52 does nothing happened I'm just gonna you know I think I'm pro Qing as though I'm just doing a little bit of shorthand cutting some corners but it's important to be aware this is part of why it's so important to really walk through your algorithm and think about what you're saying what I'm saying here is oh well I don't need to check every year from the first birth year to the very last death here I obviously don't need to because I didn't do that I only needed to check the years where something happened the years works where people were alive there someone inside that born or died if no one was born and no one was died my population doesn't change so hah new algorithm I don't check every year from the first birth year to the last death here I only check the years where someone was born and someone was died someone died because if nothing happened population didn't change so it's not going to be the highest population so now you might want to say wait a minute so I just make it an assumption I didn't realize maybe I just maybe I did or what I said was if no one was born and no one died the population didn't change so it's irrelevant this is probably the time when I asked my interviewer hey wait a minute so if what do I need to if there's a tie in multiple years have the highest population what do I need to return in an ideal world I as a candidate would have realized that in the very beginning that that's a you know potential and big ambiguity but you know I didn't so that's fine so I asked it later on my interviewer will tell me in this case oh you know you don't need to return a range just any year that's the highest it's fine so if there's a tie just retreat any of those years great okay so then yeah the approach I was talking about works I only need to check the years where something happened where someone was born or someone died so rather than all the years from 1750 to 1700 2010 I just check the birth and death years so we go to 1750 how people are alive I go to then 1803 you know I'd say okay no no no yes this one yes that's - no yes three 1803 okay I just did that that's three wait that's another optimization I only check I don't need to check actually every single year every single birth you know every single death here I only need to check the unique years so now we have a slightly more optimal algorithm I'm going to walk through every birth and death here and I'm going to just check the unique year so I'm that means going to need a hash table or a hash set to say okay have I already looked up this year or not I haven't calculated it then I'll do it again so 1750 throw then do hash table kind of says okay you know visited that year Karen how people are alive and then go to I actually start with any wire it doesn't matter so mm how do I live in 2000 1975 County filled our lives 1975 already done it it's in my hash set if you know three how many of our life so this gives us a little bit more up full algorithm so now our algorithm is get the actually we no longer been me the min and max birth year now we're just gonna say okay walk through each person and check for each person compared to every other person to these counting people who are alive in their birth year and how people are alive in their birth and their death here and that's gonna give us an Opie squared algorithm we can actually describe a slightly tighter run runtime if we want we can actually say what we're doing is we're only actually checking doing the second P loop forever unique year so we could actually say it's u times P where u is the unique years and P are all the people so this is a little bit better than what we had before it's getting better um let me think some more about this well so one thing we might notice is we're doing less you know I do this for 2009 to 75 97 5 etc guys on my birth years my death years this is where I start getting to the unnecessary work I you know if you look at the algorithm approaches I talked about in the video or initial talk wasn't things I talked about is unnecessary work cut it out so think very carefully about what you're doing here in my algorithm right now I walked through each birth year and for each birth year I check to see how people are alive the death years well if I'm looking for the highest population the highest population will occur in a birth year the death years I actually don't have to check the highest death deaths just take away a person they don't increase my population by definition so the death gears are not gonna be a max year they're not gonna be the year where the population Peaks unless there's also birth in that year and many worth in that year so what I walk through this I actually don't need to check my death because death just decrements I only need to check my birth years so walk to each birth year and check how people are alive in that year this doesn't change the runtime but it's still a good insight to make and it'll change the you know number of seconds it takes to run potentially but not the nope not the big go time that's fine it's still a good insight to make okay so our album right now is walk fall the first years for each birth year check how people are alive in that year still you times P how can we okay so how can we make this more optimal well here's one way of doing it you know you can't we can drive an example like this sometimes you know I talked about when the approaches is do-it-yourself so use examples sometimes it can be useful to draw things in a different way try a different way of representing the data so let's try that so a different way of representing the data could be on a number line so let's draw this a little you know abbreviated number line 1750 is the first one all the way through 2010 and now let's start recording this so one person was born in 1750 this is not going to be the scale that's fine one was born in 1750 lived to 1869 1869 someone else was born in you know just start deviating from that example just to make things easier maybe someone else was born here this is a birth and death birth and death birth and death birth and death so pictorially if I were to walk through this I'd be looking for basically if I start your representing my data this way now I'm looking for something more visual which is like I kind of walk through my line and I start looking for the thing that intersects the most now one thing I might notice here is that it interestingly it doesn't actually matter who died when so this is a really useful observation to make meaning that if I were to take a set of data jumbled up all these death years it wouldn't really matter fact one of the things you might notice I said earlier is it doesn't matter or doesn't a death decrement some population and thus won't be the max I made that point earlier so if it just decrement some population doesn't actually matter who died when a birth adds a person of death adds a death subtracts person but doesn't matter who did what so let me redo the data with that observation so I'm gonna draw births and death kind of arbitrarily birth death birth death try to make my birth up here birth order birth birth birth death now what would I do well let me just try walking through my my example again so we have what is the highest population well one person other person's for another person's born that's three people in this year now somebody died that's down to two now we're back up to three down to two back up to three two one zero oh wait I just did a brand new algorithm here this wasn't this is kind of the way my brain to ative to tively led me what I did here was I said okay well I put these all in the number line and label all the births and deaths and naturally my brain went - well I'm just gonna walk through and figure out what the output is my brain was led to O birth increment birth increment birth increment death increment birth increment I do this in linear time and that's a much more optimal algorithm so this algorithm now I need to transfer now I need to kind of reverse engineer my thought process this algorithm essentially put everything on a number line from the earliest birth to the last death and then when I have a birth give me a little uptick when I have a death give me a little downtick and then every year in that table essentially represents the max populate the how the population changed in that you then I can walk through that and find the highest population that's the basic gist of my algorithm and here's where a lot of people will say okay I think I basically understand what's going on let me walk through it one last time slow down or let me just go ahead and code it slow down here and walk through your example one last time and really really think about what things mean I'm gonna go back to this example okay so what my algorithm does is I need a table from the first birthday to the last death here okay that means I'm going to need to actually find those years so I'm need to find the min birth year that's 1750 and the max death year is 2010 and then I'm gonna have a table this is gonna be an array from 1750 to 2010 which is gonna operate almost like a hash table that's gonna walk through that's gonna add a check mark when you increment in a check mark when you decrement so we have 1750 person was born that increased the population by one the in fact I don't have these necessarily in the order so unless I want to sort the data which isn't necessary I'm an attention to it out of order so mm that is a birth 2010 mm-hmm so here's an interesting question that I haven't yet asked my interviewer what when is a death recorded if some news say was born in 2005 and dies 2005 are they alive for that year or not the answer from the interviewer if I'm the interviewer is gonna be yeah you know if someone's born the morn during their birth year born and dies in the same year they're considered to be alive the whole year in fact and generally speaking or general someone is alive the entire year of the birth and the entire year of their death okay so 2010 then actually we can we actually need to record this as really more like it's a decrement the following year not in 2010 so it's actually means the population got dropped by one right at the beginning of 2011 so 1975 adds by one 2005 they died low-five oh that's actually at some Court 2006 subtract 1 1975 that's another person born 2003 that is up 2004 is when I get sooo corded that's right - 1 1803 that's 1 1809 they died oh that's a court of 2010 or 1810 1750 they're born 1869 they die sonne iTunes 1870 1840 they're born population increases by 1 1935 they die so 1936 it gets recorded 1803 increases by 1 1921 they die so let me write that down 1922 is when the death that happens 1894 1895 poor they're born +18 1921 they die so that's accord in 1922 okay so now once I this is these are all the population deltas in an array now I would just walk through this and find the highest population so it starts off with two people are born in 1750 nothing nothing nothing nothing 1803 population jumps up to four nothing nothing nothing nothing 1810 somebody dies down to three so I'll just I like to be really when I write draw examples this is something I found for a lot of people I like to be really detailed what I write down so two people born to more people born 1980 no three somebody dies in 1810 so that downs down to three 1840 another person is born 1870 somebody dies 1894 another person is born 1922 two people died down to two 19 thirty-six down to one 1975 to more people foreign down to three mm up to four 2004 down to 3 2005 down to two and 2011 down to one okay okay great so okay so that's my algorithm so now I just make sure I know exactly what I'm gonna do so I'm creating an array first I'm getting the min birth here the max death here and actually as I remember earlier I don't need the max death here right I only need the year with once once nobody's being born anymore that data is kind of it doesn't really matter what happens when nobody else is being born so actually the min birth year and the max birth here because people are only dying off at that point the population won't peek so min birth year and max death here I meant min birth year max birth year and then I create an array of all the people from the min Berthier to the max birth year and then I all those hooray is gonna be initialized to zero and it's gonna hold all the values even if nothing happened that year and then I'm gonna walk through each person here and increment their birth year and decrement their death year minus one or death year plus one so I'd recommend the year after that out of mine subtract one from that then I'm gonna walk through this and get the basically get the compute the running sum here and take the max of that all right I think I'm ready to code I don't need this stuff anymore and so like this spot would be a bad place to write code it's very tiny I don't need this number line anymore I'm making a bad example up on the board because I have enough space right now so I'm gonna start coding I'm gonna code in Java okay so let's go where this does I base have two steps my algorithm first I create this array of all the deltas then once I'm all done with that I get the running sum okay actually before I do that I'm gonna go save those runtime is so the runtime here first thing I do is get this array of all the deltas that's gonna be O of Y where Y is the range from the min Berthier to the mat now they're getting the right crit yeah building the array of all the deltas let's see so we need to get the min birth um the max death here that's gonna take of P time we get the min birth here the max birth here where P is number of people then I need to walk through these people and add a plus and I need to create a here's where I get something interesting I get this range from the min birth here to the max birth here and then I create an array very subtle thing that people will often gloss over creating that array that's gonna have say o of Y where Y is arrange them in birth into the max birth year that it takes actual time to create that array so you shouldn't forget that so min birth routes the max birth here takes o of Y time to create that a'right so plus y to create that array um then i need to walk through those people and put in the plus one at the birth year - when their death here that's gonna be another ofp x then i need to walk through that array and get the running sum that's the Meo of Y so total run time Oh P plus y don't try to do something here like say well if the people is you know a constant then you do that so the range of years is a constant it's not a constant unless you're told otherwise it's not a constant and so you do you say oh P plus y okay so now I'm ready to code alright so approach is I want to find the mid number of the max population so I'm going to taking a list of people return an integer with the year and I want to find the year at the highest population what I'm gonna do is I'm going to first get this array of deltas and then I'm gonna get the running sum so we're trying to ray which is integer for the result which is a year then I'm gonna say yet I'm gonna call it get population peak and I'm gonna take an array of people you know what I actually messed something up here I want more space should take my own advice I'm gonna write as far over and as far up as I can and get population peak and that's gonna take in an array of people and so I'm gonna use a person object I'm not gonna worry about writing out the class for this because you know honestly is it really that interesting a person class it has at birth it has a death ask your interviewer to validate but I'm not gonna write it out because it's really not very interesting okay so takes into people people object and then what it does is first it gets this array of deltas so that is just an integer array okay so get deltas that takes in people and then sigh that gets the running the Delta ray and then it gets the running sum int actually it's like get max running sum and takes in the deltas oops Delta Z equals get deltas people okay so Delta's and now I return the sum now I'll pause for a second here and think about this is this basically work one little problem here I this Delta's thing here if it starts at 1750 then that is actually corresponding to you know I could create an array that is literally everything from your zero to here those still how do I deal with potentially negative years my Delta's array I probably want this first birth year to be the index 0 so my Delta array doesn't actually have like it doesn't start at 0 it starts with like 1750 and that's like the 0th index which means that this get running sum here is going to just return say you know at 1750 were the or let's say 1810 were the biggest year it's not gonna return 1810 as the highest like the index of the highest some it's gonna return like 60 here it's gonna return the offset so that's gonna be a problem and this is part of why it's really valuable to mod rise in the very beginning I could have very easily have written out a whole bunch of code code for one of these helper methods and not realize oh I don't have the date need half so what do I do here well I can do one of two things here I can either have get deltas operate a little bit differently and get the min birth here in the max death here and return that somehow in some serve class and like that I could just get the actual running when I actually get the running sum I can now get the offset of the offset new couple different things I think what I'm gonna do here is rather than having get Delta's just taking the number of the people I'm gonna actually have this take in a shift value so I don't have it taken actually a like first birth value and a first birth and last birth then here I'm going to declare it so here I'm just using you know I'm not gonna write things down and not gonna erase a whole bunch of lines of code so first birth is gonna say you know get min birth and erase that I don't need that anymore get min birth of people want abbreviate that a little bit it's okay I've already written out people before so I know I've demonstrated my interviewer that you know I'm gonna use descriptive variable names so I'm gonna abbreviate that and to get last birth didn't last birth equals you know get max birth people okay the reason why I do it that way is that get deltas is gonna need to know the first birth and last birth to know the range of values to know and if I mean I'd rather not do that work twice so I'm just gonna call that and then have get deltas taken the first fourth and last birth and then get running some is I think shouldn't be okay with just Delta's now I just returned some or you know actually I should call this it's not really this am I'm returning get max running some index is a better name so it's like get the index of the max running some so taking the deltas peak year and then here it's peak here actually plus the first birth I can actually make that very well name a little bit bigger a little better it's actually more like the peak year offset big you're offset plus first birth okay that's my first method now now notice here how I really pushed a lot of modernization a lot of people's first the very first thing they'll do this they'll write this for loop that gets the you know maximum of this array the minimum you know this isn't I'm no I don't learn a whole lot from you by watching you write an array that gets the minimum gets the maximum that's that's very simple code to write so I'd rather you as you know if I'm the interviewer I'd rather you not spend your time writing that stuff so just mod your eyes so min births your max birth year they'll toes get the peak return that so a lot of monetization going on here now I look at what is I don't just go for the neck so like the first function this gets called what's the next most interesting thing to write well it's either the deltas or the running some kind of toss up I'm gonna write get dealt us so that's gonna return an integer array get deltas I've already defined this this person so I'm gonna just you know abbreviate this array of people a person objects called people int first birth and second last birth okay now I need to Claire an array and okay so I need an array of all the deltas and this needs to go from the first in this range so last birth to the first birth now for each person and this people array now what I want to do and notice how much I'm talking out loud that's one thing you want to do in your interview to try when you're coding to talk out loud and it's actually not only does it demonstrate good coding style and your thought process which is really a demonstrate good communication your thought process which is something your interviewer is doing it'll also likely encourage you to think a little bit more about what you're doing and make sure you're doing the right thing okay so for each person and notice that abbreviation let's just you don't have to do it by any means they'll just make your life easier for each person in this people hooray I want to increment their birth year and decrement their laughs their death year so I'm gonna have to do a little of bounds checking you know so it's not as simple as like deltas you know P dot birth P is my little person who are you here I just abbreviate it you know it's not as simple as that excited to do some bounds checking their to make sure I'm not going out there right so you know it's a toss-up here but I'm just going to I'm gonna call a method called like add Delta that goes and increments that changes that value by the one or minus one just pretty my balance checking one place so add delta path my deltas array my person and then one for the birth year or oh no I need to pass in my birth year and then one that adds the birth Delta notice here another little shorthand thing rather than writing out Delta again or Delta s actually it's called I just you know use quotes so cuz it's basically the same caller than that gets changed from birth to death and this gets change from a 1 to minus 1 okay so I walk through these person increment and decrement the birth and death now I return my deltas array okay so that's that function next most interesting thing is obviously my writing some okay so let's see where do I want to write this where do I have the most space I think I have the most space over here so I'm gonna write it over here and I could race this too but I think I might want it so get running get max index of running sum and that takes in just my deltas right okay so I always like to think through what I'm coding before I do it again even though I already did it before I started coding here so just make sure I know what this is gonna do again so this is going to basically run through this deltas array compute the sum as we go and then always look for the max as we go along so int running sum it starts off at zero and then we want to keep track of the max we're gonna need to know the max running sum so int max running sum and Max is gonna start off at zero and then we're also going to need to know we're actually going to need to know the year that it corresponds to so I'm gonna call that year of peak equals zero okay so now I just walk through my years and I I like you know usually I is okay for incrementing through a on an array in this case though this isn't just corresponding to like a random index the thing it has some meaning so I'm actually going to call this year you're less than Delta's dot length year plus plus okay okay so first thing I want to do is add the running sum and you know what this is this running something is a pretty long word I've already written it once already demonstrated hey I get it good variable names matter I'm just gonna breathe eat so and commit the running sum that means Delta's year now I want to check if basically it's bigger than that so if the running sum is bigger than my max running sum then running sum becomes my max running sum again abbreviation becomes running sum year of peak becomes my year index return your peak okay so that's the basic code for that now this point I'd kind of have an instinct as a candidate that you know again get min guess get max it's not terribly interesting code I mean it's just walking through and getting the max and then so I would just ask my interviewer if they wanted me to do that and me oh maybe an interviewer would tell you to do it maybe they wouldn't kind of hands in the situation you might also go out you know you can actually you know in Java 8 you could probably use a lambda function to just do this directly so you didn't have to do that so you don't have to write again and get max and certainly Python and other languages support that as well ah so you can throw that out as an option okay that's the basic code so now what I do is you know I'd go through and test it I wouldn't just say okay todo I'm done so I'd go through and test it now as I said the very first thing I do when I'm testing is I walk through the logic okay so my logic here is I need to know the range of the first birth year in the last death here and so I get that range and then I check okay does so get that first birth or death last death here I add create this array of all the deltas so that goes down here and I create this array from for first birth year to last death year and that's in that to have a range of that those years then I walk through each person adds increments of fourth first birth year adds the death year I kind of think about what I'm doing when I'm doing this and I think oh wait now it wasn't decrement the death its decrement the death plus one because I don't want to I don't want to record the death until the last year so validate does that really make sense yeah yeah okay so it's not decrement the death here they're currently you're after the death year all right okay so then go back to Delta's this is another function I haven't written yet again ask my interviewer do you want me to go write that let's say they say no okay okay so returns that so I get all these deltas then I go to peak worse get max running some and get max running some index you know didn't call the exact same thing I could go correct that and then I go through my writing some and walk through each year from in the array and every value and their right and come at my reading some because it's literally running some and then if I'm asleep that and then go through and return so now that I've kind of walked through you fix one mistake value that it basically works now now I'm not gonna throw in a test case quite yet I'm gonna go double-check things that tend to cause problems all right here things that tend to cause problems well they're nine parameters match up people people first birth last birth okay that matches up get max running son okay that matches up okay what else causes problems in this function you know I've got I'm gonna use a different color here math math just causes problems very very very often okay so let me go and double check that work first worse and last birth okay so one thing I found whenever I'm double checking math stuff is a lot of people double checking with like some arbitrary example like 1750 to 1869 really big and hard to see little problems I like to do it with things that are really small very very close together things that make a a mistake very very obvious so what if first birth were say 2000 and last birth were 2001 or I can even keep it simpler and go to 2000 but in this case first birth - death here I'd create last birth I'd create an array of size 1 but that's not quite right cuz I'm gonna need to increment the birth year that corresponds to 2000 and the one that corresponds to 2001 so that's not quite right so what I do here is I wouldn't just say you know oh I'm gonna make my first Bex I'd really make sure ok does this there's a logic my instinct is that this is off by one and it should be last birth - first birth plus one but I kind of think for a second make sure that's like really the right thing ah yeah okay so I think that makes sense because here I needed a difference of you know two and I only had difference of one okay so that should actually be first birth - last birth plus one okay okay so it's one one bug and this thing I fixed earlier that was a bug earlier okay so get max index now okay so I have the running sum is zero max sum of zero your of peak okay so I want to make sure I always set the max the right thing so let's see if the well oneness you might want to talk about is what happens if there's like you know no year you know the arrays are empty things like that so we might want to add in some logic there to double-check those issues but now what happens when the very first time so let's run through this so very first time I have a max of 0 so the very first time we should have a birth right like the our array is starting at 1 all right at the first birth so immediately running some naturally some should so immediately my very first value deltas should be at least 1 so that that will increment and and that means that you immediately will hit this this will be bigger than max turning someone bigger than zero actually some will be zero initially writing some will be at least one so we'll increment those values your P will change the year okay so that seems so least Max gets changed seems to get change to the right thing and then one thing I want to check is okay what if you know whenever I see like loops that get the maximun I want to make sure that you know what that does the right thing if the loop never operates at all so the loop never operates at all that means Delta is a zero which means it could only happen if there were no people so you know we can do some work there to control for it but we probably actually want to just add in something here that says okay if people is no or this you know or people's has a length of you know 0 then return some error code and this is where you might have a conversation with your interviewer about what's the right value here okay so now is where I would go to some cast cases so very first you know I might try some very very small test cases like mm I already kind tried this test test earlier - no I would not do that one first do some initial test case 2000 2001 2001 to 2002 very small test cases okay so we're gonna get the I'll use a different color to write this up so this is my test case 2000 2001 2001 2002 so there's when you run through a test case there's no you know the way I'd be best way of running through it it's really a matter of what works best for you and for the problem for me I'm gonna say okay this I'm gonna just run through it manually so and I'm gonna kind of write the values above so first birth is gonna be 2000 last birth is gonna be 2001 okay now I call get Delta so I go down here so last birth this 2001 first birth is mm so 2001 - mm that's gonna be array of size - okay that's good that's what I want think sometimes people like go through the whole testing thing just look at the right out look at the output at the end better to think a little bit more critically as you go along like is that the right output and right up sighs - yeah that's what I want okay now I add Delta that other Delta now I haven't written this function so I'm gonna assume it does what I want so I'm gonna pass and Delta's and then the birth so in a passing mm but wait we have a problem here Pete up birth is that from passing mm eltis doesn't know the right year to pass doesn't know that the offset is actually 0 or 1 or whatever I need to pass a knot mm I need to increment not mm index I need to increment mm - the first birth so - FB so mm - mm that's when you pass and you just say add increment the 0th index so my array looks like this this is mm this is 2001 so this corresponds to 2000 this corresponds to 2001 so P dot birth to two thousand nine thousand one that corresponds to index 0 so I need to increment that out of one add Delta decrement the death value so decrement the death value which is 2001 plus one that's actually 2002 so actually that won't nothing will change there because 2002 is off out of bounds I might add Delta will take care of the boundary checks now I go to the next person 2001 at increment their birth year - FB so it's 2001 - mm the first birth that's decrement increment value one now I decrement 2000 the death year plus ones decrement 2003 that's an offset of just didn't write in that - FB there so that's an offset of 3 which is out of bounds okay that's my deltas it's all done go to my get running sum function that's my example there okay so I walk through this running sum starts off as 0 max running sum 0 0 I'm gonna write the values over here your f peak is 0 and I'm gonna rewrite that example that I started with over here just for simplicity so that has a this was my Delta's array and this corresponds to 2000 this corresponds 2001 okay so you're all 0 okay running sum gets incremented by so year starts off at 0 running sum gets incremented by deltas of year that's deltas of 0 which is a 1 so that becomes a 1 if running sum which is 1 it's bigger than the max running sum then I update max running sum so good that is the case one is bigger than 0 implement Mac increment max running sum to a 1 or after that your if P becomes updates 0 okay now that's all done do the next loop year becomes 1 running sum plus equals Delta's of 1 so increment that now running sum is bigger if running sandwiches 2 is bigger than max running sum which is 1 increment or update max running sum that becomes a to your peak becomes a 1 and we're done and return your peak which is it's one right now all the way back here okay so peak here was returned as one now I returned peak here which is one plus first birth which is two thousand so I returned two thousand one and yes that is indeed what I want two thousand one has a population of two that is indeed the peak so that's walking through a very very very very simple example now what you'll notice here is it's a simple example it's a trivial example it working on this example does not mean that the algorithm the code is perfect but it was so small that is able to run through it relatively quickly it would have if I take an example like this to run through it would have taken me four times as long to run through it would have increased the probability that I just make when I'm testing just make some stupid mistake and I don't realize there's a bug or I think there's about that there isn't so my example though was really really really simple was enough for me to realize a couple little bugs I made I think and the bugs were little things they weren't out big algorithmic challenges they're tiny little off-by-one errors but those are the things that are most common to make so when you start testing and you walk through it analytically think about what you're doing walk through these simple test cases double check any arithmetic stuff like that and then you know next thing I do here is I throw in some edge cases so I might throw in some test cases like 2009 and 2009 so that's a little edge case I might throw in I might also check twenty thousand nine and that's actually my sample re-check 2009 and 2011 2011 I might also check and this is the conversation have with your interviewer could you have negative birth years do I need to validate that my my data works so if I do need to validate an idea is okay I might throw in a function that basically like maybe what if the death year is Berthier like the data's malformed so maybe I want some initial function your interviewer does want you to check that so just throw in a function that says you know validate birth years whatever I validate years so I check some edge cases and then if I had the time I might actually run through a bigger example but that takes quite a long time so walk through that process of you know analyze your code make sure it works then go to you know some double check any arithmetic like a little thing like that cause those problems so easy have a bug like that then you know bigger venez you know small tax case some edge cases then some bigger test cases so that's the process I want you to have when you walk through a problem so do going back to the very beginning what we did here was we first said okay do I understand the problem - I understand exactly what I'm being asked to do sometimes people will miss here this problem as find the you know population of every year or something like that or find the year where most of the people are alive which is a different problem so you walk through and make sure you you know make sure you've heard the problem correctly then we came up with an example and the initial example had bunch of special cases in it so I want through and I said okay let me make sure I've avoided the special cases let me make sure that everybody's not alive at the same time and in fact let make sure that most people aren't are necessarily alive all at the same time let me make sure that I have some duplicate years in there because that actually matters and that is that I can come at the same time the the same thing multiple times let me make sure I burst at the same time as deaths so I went through and make sure I got out as many of those special cases as I could think of then I came up with a brute force I came with multiple algorithms that were a little bit more optimal each time came with a brute force and then stayed the runtime derive that runtime be very thoughtful when you derive the runtime you don't have to state an algorithm and say oh boom that the UN time is this if you can do that great but a lot of times problems are a little bit more complex than that so just to Rive it step by step by step what are you doing then I started walking through my example to try to derive a more more awful algorithm eventually I tried a different way of representing my data and that ended up giving me the insight on how to solve it then before I once I said okay I think this is as good as we can do it might double check to my interviewer if they want me to code but then I said okay I'm gonna walk to my example I'm gonna make sure I know exactly what I'm doing I wanna know my data structure sir I want to know that I'm using an array and you know that my rains gonna have an offset of this and here's how I'm gonna get the offset I want to solidify all that stuff then I started coding when I coded I thought thought as I did it I wasn't trying to brush my thought as I did it and I tried to madres as much as possible little stupid you know simple functions like get them in get the max I don't want to spend my time writing that I'm not I don't demonstrate as a coder that I'm particularly great because I can write a function to get the minimum element so push that off to another function I'm authorized conceptually as much as possible and then eventually get it coated I might you know double check to my interviewer do you actually want me to go and write this stuff and then finally I test it as I said I'll analyze the code look for the little errors and then start with a then start with your you know simple test cases your edge cases and then your finally your exam your big test cases so that's the process listen come up with a good example big and not a special case come on for the brute force state the runtime optimize your code use those different approaches that I talked about in the initial talk about optimizing solidify your understanding of the algorithm code it thoughtfully and with a lot of monitor is a ssin and good variable names then test so use that process and that framework for walking through a question again you can find that framework I cracklin coding interview comm click on resources or send me an email G at Yale comm with the subject FB prep and you can get an auto response with a link to that those slides thanks and good luck

Channel: Siamak Sobhany

Views: 139,492

Keywords:

Id: 4UWDyJq8jZg

Length: 66min 52sec (4012 seconds)

Published: Sat Sep 29 2018