Solving Coding Interview Questions in Python on LeetCode (easy & medium problems)

hey what's up everyone and welcome back to another video so if you want to become a great data scientist software engineer uber hacker dude dudette you first want to become a good problem solver so in this video we're going to walk through a bunch of lead code problems and the reasoning for this is twofold one these leak code problems kind of can help you improve your general coding skills and then two these are algorithms type problems so they really make you think and they really kind of train that problem-solving muscle in this video we're gonna go from easy problems or relatively easy problems to more difficult problems so feel free to do a little binary search to figure out like the right difficulty for you also feel free to kind of like watch one problem then come back to the video another day etc and also the general way that you'll want to approach each problem is i will link every problem that we do in the description so what you should do is try out the problem on your own and then if you can't figure out the solution or just want to see how i would approach the problem play through my solution of the the problem in the video i think this should be a fun one without further ado let's get into it how i'm going to get to these problems i'm just going to go to elitecode.com i'm going to click on problems i'm going to use filter by algorithm it doesn't really really matter here and then just to kind of figure out what's harder what's easier this isn't a perfect filter but what i ended up doing is i filtered or i sorted by acceptance so the higher the acceptance rate you would think that that would be kind of the easier problems more people got them right so to start off we'll kind of do some higher acceptance easy problems then we'll move into kind of some higher acceptance medium problems and then maybe at the end of the video we might do one or two hard problems i'm not positive yet all right to start off let's do this problem the goal parser interpretation this is problem 1678 and i've linked it in the description and so you can read through the problem statement but the basics is that we have this parser that takes in strings of the format like this and translates it into more readable strings like this and so there's three characters there's the g the parentheses and the parentheses with the al and we need to just do these replacements so it's a pretty straightforward problem but let's let's give it a shot feel free to pause the video and then resume when you want to see me solve it all right so when i look at this problem i think about replacements in python we're taking these inputs over here on the left and we're making these outputs so when we're thinking replacements in python i think of the string replacement method if you're not familiar with that as always kind of allude to do a quick google search like replace strings in python and you'll find you know something useful that can maybe help you out so it's as easy as doing something like this well now that we have that we can just simply do the replacements that are necessary so we have our command right and if we do dot replace well we can replace the g with a g but we don't really need to do that because that's not actually replacing anything so we can start with the parentheses anytime we see parentheses let's replace it with just an o we can chain these commands together so this is going to return us a string so we can actually just simply do dot replace again with al and making that just a l without parentheses and that should be all there is to changing it to the format that we expect so i'm going to just go ahead and return this and see what happens so i'm going to run code nice it looks like it worked and the next thing we want to think about when we're doing problems like this are there edge cases that we're not considering well i think to do that we're going to have to look at the different examples and kind of the constraints so we know that it's going to be between 1 and 100 so that's pretty straightforward that's pretty small we don't really worry about like is the replace method like efficient or not and we also know that we're constrained to only these three characters so there's no like weird uh maybe like situation where there's like something like you know a parenthesis that's not fully closed or something or like nested parentheses like that so i think we're good here um you can feel free to type in these other examples as test cases but i'm going to go ahead and submit this accepted look at that cool and there's many different ways to do this my other recommendation when you're doing these problems is you can go to the discussion always and look at other people's solution so we see like python one-liner i'm guessing this is going to probably be the same as what we have and look at that it is but maybe some of these other solutions are different so python c plus plus simple solution using dictionaries and we see this person has done something else in their solution so it's good to maybe look through these discussion solutions because that gives you other ways other perspectives on how you can solve these different things all right next let's do problem 1436 destination city so in this problem we are given an array paths and each path in that array is a connection between city a and city b where there is a which means there is a direct path going from city a to city b and our goal is to return the destination city which is the city that doesn't have any outgoing paths from it so as an example we see in this case we have the path london to new york we have new york to lima lima to sao paulo and because sao paulo has nothing coming out of it no no paths are leading leaving from sao paulo we know that sao paulo is the destination city this also you can have more complex examples like example 2 where you can go from b to c you can go from d to b and you can go from c to a so there's a few different path options as we can see here but every one of those paths leads to a so we know that a is the destination city so how could we program out a solution that could kind of find that destination city so when i think about this problem i think about counting we're ultimately trying to count the city that has no outgoing nodes from it so if we count how many outgoing nodes each one of the cities that we see has and just return the one that has zero outgoing that will be our solution so we can probably utilize a dictionary to help us do this so let's write a solution that does that so for path in paths we want to iterate over each path and i do want to quickly add some sort of dictionary that we can use to count so let's say that this is called outgoing count and we'll make that an empty dictionary so for path and paths well that each path is going to be a pair of two cities city a and city b so what we could do is we could say that city a comma city b equals path this is just unpacking a path like london new york so city a would be equal to london and city b would equal to new york that's one way we can unpack a list of two items or a tuple of two items so we have city a and city b and really what we want to count is we want to increase a count every time a city is listed as city a but we do want to count city b because ultimately if we only counted city a's we would miss out miss out on the destination city so let's add both of these to the dictionary so what we can do is something like outgoing count and we can use the city that we want to input into that and then what we want to do is kind of like increase that count by one but it might not be set to begin with so we'll have to keep that in mind so we'll say something maybe like outgoing count dot get of the city a and if we don't have city a already there then let's go ahead and set that to one to begin with and we can do something similar for city b so we can say outgoing count city b equals outgoing count dot get city b but this time because city b is the destination node we don't want to increase that outgoing count for city b so if we haven't seen city b before um let's just set it to zero and i guess in this case two we don't want to just get the number we do need to increase it so in this case we should do we don't even need it we can say keep this at 0 but we should add 1 at the end so if we haven't seen it before we set it to zero but then we add one if we have seen it already we've seen that there's outcoding node then we get that count and we just add another one to it and really it doesn't even matter all we care about is ultimately what's left as zero okay so that creates our dictionary so once we have a dictionary that has all those counts then we actually need to go ahead and count them and and see what value is the lowest so what we could do is just iterate over the dictionary so let's just say for city and outgoing count and then if we ever find a city that has zero outgoing counts that's our solution so that's what we can return so outgoing count of city if outgoing count city equals equals zero then we want to return that city and we always are supposed to have a destination city so there should never be uh an error case here so i think that this is probably a good solution look at that it seems to work and so what would be the complexity of this solution well it's bounded by o of n to iterate over the each path in the paths and really we can't get any better than o of n because we have to look at every path to ultimately figure out what's the destination city but i guess the question is does this last second iteration over the dictionary increase that runtime complexity and ultimately it does not because it's just another instead of just going uh o of n or like just one iteration of n times we're doing a second iteration of n times so it's really a total of 2n iterations which is still bounded by that o of n runtime complexity so that seems like a pretty good solution to me let's go ahead and submit that and it is submitted or it is accepted cool um and it looks like it's running pretty well it's less than 97.31 of the python 3 online submissions and it's faster than 74.5 of them so in this case our first solution uh worked out well and and did a good job sometimes that's not the case we have to continue to improve things but i would say that i would be pretty happy with this if i saw this as the solution to like a coding interview question uh one thing that's cool to do though is kind of look at the discussion see if there's anything else really clever that people did oh and look at that this person used a set um and basically said okay i mean this is a little hard to read but i i really like this idea of a set um basically they counted what's in city a and what what b is a city b and then they subtracted the set of b elements that were in b from elements that were in city a and ultimately the one that's left in b that wasn't an a will be that element that is returned next we're going to do problem 1365. how many numbers are smaller than the current number again linked in the description and so the problem statement here is give an array nums for each nums i find out how many numbers in the array are smaller than it that is for each nums index i you have to count the number of valid js such a j is not equal to i so that's talking about indexes and nums j is less than nums i so sometimes these problem statements can be kind of confusing so my recommendation is always you know really look at the examples that will be what really solidifies the problem so we see here in this example we have this input which is an array of nums eight one two two three and we see the output is four zero one one three and what they're doing here is that we look at this number 8 and we see that we have four numbers that are less than it that's where we get the 4 here the 1 there are no numbers in this array that are less than it so we get the 0. etc so when we're solving problems like this what i recommend is don't try to be creative don't try to be clever to start what is a simple solution that you can think of that would work and so when i look at this i see what's easy to me is just let's do some kind of a straightforward counting let's look at each number in this and as we're looking at that number let's just iterate over the entire list and just count how many numbers are less than that number and append it to our output so for example this 8 we would be looking at it and then iterate over the rest of the list so we see one that's less than it plus one two plus one two plus one three plus one that's a total of four so we'd append four to our list and we just kind of continue down our list so let's write that in code and this solution i just described would be a complexity of n squared so i think we can probably do better but i think it's good to just kind of write out a simple solution first but if you were doing this in an interview setting just be like hey this is what i'm thinking of right now but ideally we could figure out something more efficient and kind of start there see that you're thinking see that you are kind of always seeing how you can improve things all right let's implement this so for i in nums when i look at each number here i'm going to keep track of our output in array so i'm going to say output equals an empty list so for i in nums we want to then iterate over for j in nums and basically as we are looking at this problem we don't want j to be equal to i so we're going to say if j is not equal to i then we want to maybe let's say we have a counter count equals zero and we're going to increase that counter count plus equals one and then when we've exited out of this loop so when we've iterated over the entire array of nums for this specific i we can do output is the append of the current count and then we will get our next i and our count will be reset to zero so we do that for everything and then we can simply at the end return the output so hopefully that made sense and let's run it and try it wrong answer okay i guess uh something got screwed up there oh i'm i'm impending every time uh we want to only append if j is not equal to i and nums j is less than nums i oops that was a silly mistake indexer list index out of range what do we do here oh oops now what are we doing now we're we're not looking at the indexes so see you make mistakes if you're not careful but what's happening here is we're not iterating over the actual index value so what we could do is we could say in length of er and range length nums and again we want to iterate over the index values so we're going to do range length nums um and what i would recommend is if you have premium you can get the debugger so you can actually like print out values and see what's going on but you also could just like open up a sublime text window whatever your code editor of choice is and you know try out some of these test cases with a function that you define there but let's run this code again okay look that looks like it works we could try more test cases but i'm feeling confident let's just go ahead and submit our code look at that it is accepted but we see that our run time is only faster than 8.83 of python 3 submissions so there's something we probably can do that is smarter than this so we're right now at a complexity of n squared i'm going to just scrap all of this and we're going to start fresh let's try to get to a complexity that is better than n squared and one thing to note is you can always find the code if i clicked on accepted here i could find that last submission so i'm not losing anything by deleting all of my code but let's go back all right we just did an n squared solution what i think is better this is the next thing that comes to mind it might not be the optimal solution but i'm thinking if we sort this list and know the length of this list then it's pretty easy for us to tell how many numbers are you know less than the current number we're looking at so if we sorted this let's say like 8 3 2 2 1 so i'm going to type that out real quick so let's say we sorted this to eight three two two one well we see that eight would get four numbers less than it three would get three numbers less than it two well we see we have two and we see the next number is two so really we would need to start counting only when we get to the new number so we'd have to count how many times we see that the same number and kind of append that many times so with two would be one number two would be one number and then one is the last item so that would be zero numbers so can we implement this solution all right i'm gonna kind of just start flushing things out and i might have to like throw some print statements in this and whatnot to get it to fully be working but let's start out by defining sorted nums equals sorted i think we can do that sorted i think that's a built-in python function of nums and honestly i could real quick do print sorted nums and just check so we're going to run code real quick and it does give us our standard output okay so we see that it's sorting it lower to higher so i think if i pass in the keyword reversed equals true i'm like really i would normally be google searching this i'm like crossing my fingers that this works right now uh reverse is maybe it's reverse oh look at that it worked uh normally i would have to look this up i kind of vaguely remember that um okay so we have eight three two two one that's what we're looking for and now what we're gonna do is let's go for num or let's do how about this let's do for i comma num so we're gonna have the index and the number in enumerate enumerate's a very useful keyword enumerate sorted nums and we also need to think about the original index here so there's a couple of things that now that we're working through this that i'm trying to keep in mind because now that we sorted it uh things are out of order so this output would be out of order as well so how could we keep that in mind so one idea that comes to mind and i'm not positive if if it's the optimal solution but if we have a list like eight three two two one let's create a dictionary that looks of the format you know value so the key of the dictionary is the value and it maps that value to the number of values that are less than that value so like 8 would map to 4 3 would map to 3 etc and then we'll do a additional pass on our input just doing lookups in this dictionary to create our final output so this will make sense in one second so what we could do is something like as we look at a number so let's say we're looking at 8 we check the next number if it's less than 8 then we check the length of this array and we subtract this current index to find the number of values that are remaining in the array and then we append that to our dictionary so i'm going to call this value dict or maybe i'll call it if i want to be more descriptive like smaller smaller count i'm i'm struggling to just to figure out a good name it's good to use descriptive variables but you don't have to worry too too much i think smaller count makes sense there's probably something better i could use but what we're going to do is so we're looking at our current num so basically if sorted nums i plus 1 is less than sorted less than sorted is less than num then we want to take the index of soda nums i plus 1 and basically do remaining values equals sorted num or equals i equals length of sorted nums minus i plus 1 because this is the index that we're looking at and this is the total length so this subtraction would give us the number of values that meet that criteria so we see if we had eight this would be length five the three would be index one length five minus index one would give us four so we would see that eight has four values so what we would do is then do num or smaller count of that num that we're currently looking at equals remaining values and one thing that i see right now is that we're going to get an error when we get to the last index because i plus 1 will not be defined so i'm actually going to switch this up again and actually do for i and range length of sorted nums just so that i can actually go until one less than the total length so that i plus one is always defined we always know that the smallest number will be 0 less than so we can add that at the end so smaller count of the last index so we could just do sorted numbs negative one equals zero so this is kind of the last case okay so for i now we need to define num so num equals sorted nums i and if we wanted to be very uh kind of neat about this we could say current num equals sort of numbers i next num equals sorted nums i plus 1 then we can change this to if next num is less than the current num uh we want to do this now this the one case that we want to think about is what happens when we're iterating through our list we go 8 3 2 2 1 and we get to a situation like this where 2 and 2 are the same number well in this case what our code is already actually nicely factoring in but it might not be intuitive that it's doing this is if the next num is not less than the current num then we're basically going to skip over it because we really only start counting when the next number is in fact less than the current number so every two here will have the same value one number less than it and ultimately that will be added to our dictionary right at this last two so we could have a hundred twos but that last two is going to define how many numbers are after it that are less than it so we've now created our smaller account dict and then the final thing is to just iterate over our smaller account dect so for value in smaller or i guess we want to iterate over our input so for number in nums we want to create an output list oh and so for number nums we want to replace every num we want to do output dot append the lookup of the smaller account of the number we're currently looking at run that code it didn't return anything oops and we also have an error oh this is current now got to make sure that we don't we change if we change a variable name we got to change it everywhere and now we're getting nothing because we're not returning anything return output accepted look at that and i'm feeling confident again and so i'm going to go ahead and submit and look at that that's crazy um so that this new solution we just implemented we're not doing n squared uh time complexity anymore we're gonna be ultimately bottlenecked by how long this sort takes and if you know anything about sorts typically sorts are upper bounded by time constraint of n log n so o of big o of n log n is our kind of time constraint with this sort i don't know exactly what sort the sorted does by default but you can expect o of n log n for time complexity there so ultimately this answer is a bit more complex but as we can see it 10x speed up upgrades are our solution so this is in an interview setting this is the type of thing that you kind of work to get better and better and there might be even more optimal solutions but i'd be pretty happy with this n log n solution so retroactively i i wanted to check to see if this was an optimal type solution and i went to the discussion um and i ultimately saw this java solution uh beats 100 of n so they somehow found a way to do o of n and ultimately i'm not going to go through this you can look at it if you want it's pretty easy to find from the problem statement but what we missed when we were looking at this problem is the constraints are very important if you're in an interview setting always ask about the constraints you know how big can the numbers in this number list be how many numbers can there be because that can influence how you design the solution and ultimately what that very quick solution did that was very highly upvoted in the discussion is they noticed that the numbers are always going to be between 0 and 100 so ultimately as a result of that you can kind of do smarter things with counting because the numbers aren't there's not infinite number like infinite possibilities of what numbers you can choose so you can ultimately like store everything in a bucketing solution and that discussion problem has that and and speed it up further so constraints can be very important here always try to and i i'm i'm guilty here but it's always good practice to to get more information about the constraints all right next let's do a problem 704 binary search so if you're familiar with binary search it's probably pretty straightforward what this question is asking you to do if you're not familiar with binary search then this is a great example to kind of help you learn what binary search is and ultimately binary search is used in a lot of these coding interview type questions so it's always good to be kind of thinking of this whenever you're trying to do a problem that you need to find something inside of like a bigger array binary search pops up a lot so ultimately what are we trying to do well we're given an array of numbers and we're given a target and ultimately our goal is to figure out what index or if there is even an index that that target occurs at so in this case we see that there is a target and because it occurs at index four we return four in the second case there's no two inside of this array so whenever we don't see a number we output negative one so we could implement this in a very very straightforward manner and just kind of iterate over each element one by one and then if we see the number then we return the index if we don't then we return negative one and that is a valid solution and let's just type that up real quick the issue with this solution is it's you'll find out it's not optimal so let's do for i in range length nums or we could do something like for i common num and enumerate nums let's say if num equals equals target then ultimately we want to return the index that that happened at else if we get through every one of these items in the list and we don't see a number that equals target then we can go ahead and return negative one and i always forget i think it's index common num when we use this enumerate keyword this is supposed to be the index this is supposed to be the actual item in the list i always forget though the order let's run code and see if this works it looks like it works i'm actually very curious if this will be an accepted answer it might time out on us so it was accepted um but you know it is not optimal because ultimately this problem uh is the the key to this problem is that this is sorted so is there a way instead of iterating over every number and figuring out if our target's there is there a way that we can do this in a more efficient manner and this is kind of the crux of binary search so uh if if this isn't immediately come to you don't worry like this is can be tricky but try to think uh if the target is nine do we have to look through all of these numbers so maybe take a second pause the video think about that and resume it when you're ready to hear okay so yeah the key is that this is sorted so because it is sorted what we can do and what kind of the root of binary search is instead of iterating over every number let's just start in the middle let's start with this five or this three our target is nine so let's say we started with the three is three bigger or smaller than our target well three is smaller so ultimately we can ignore everything that comes to the left of that three because we know that's also going to be smaller so let's just focus on these last three numbers now we'll repeat the process we'll hit the middle of the remaining elements and that is nine and that's exactly our target so the index of that position is what will ultimately return and so this is going to be kind of tricky to write in code but let's give it a shot i think the best way to think about this as you start writing code is to think of examples of how this might work so let's say that we have the array of nums that is equal to negative 1 3 4 6 8 9 12 15 18 and we have the target which is equal to 9. well how could we go about solving this well we see that this has a length of 1 2 3 4 5 6 7 8 9 numbers so that would mean that the first index is always going to be so our start index let's say is equal to zero and our end index this has nine numbers so because we start index counting at zero that would be the end index would be eight and so our middle index would be equal to start plus and divided by two which in this case plus end divided by 2 equals 4. so that would give us 0 1 2 3 4. this is our new kind of like our middle point and we know that nine is bigger than eight so what that tells us is we can ignore all this stuff to the left and so what we can do with binary search is basically say okay our new start is going to be 4 our new end is 8 still 8 and now our new middle is 4 plus 8 which is 12 divided by 2 which are going to be equal to 6 and that would give us 0 1 2 3 4 5 6. 12 is our new number well is 9 our target less than or greater than 12 well it's less than in this case so we'll iterate again our start equals four our end now equals six because we're looking to the left and so now our midpoint equals four plus six divided by two which gives us index five which ultimately we see is the nine so in this case we would return the five if instead our target was so i'll say our mid equals 5 that number equals the target so return 5. if instead let's say our target was 10 well we get to the same point be between 8 and 12 but we'd see that our iteration of 9 our midpoint was less than 10 so it would kind of like repeat the process we'd say start equals four end equals or i guess our start equals five now end equals six and we see that if we try to like add those divide by two our midpoint is the same as it was in the prior iteration if we floor divide so it doesn't quite work um so let's get this out in code right so i'm going to say start equals 0 and equals length of nums minus 1 because if our we have 9 numbers the last index is one less than that and so our first midpoint is going to be start plus and divided by two to be safe because we might have an odd number here let's do floor divided by two basically what we're going to want to do is while our start is i'm writing in english even though i'm typing code while start is less than or equal to end let's continue this process i guess let's define our mid inside this for loop so while start is less than or equal to end our midpoint is this our number then is going to be numbs of the midpoint if target is equal to our number that we're looking at then we want to return that midpoint that index that gave us that number but if it's not then we want to reset our start or end to be kind of the new value so if target is greater than num then let's say like were here well we would have to go look to the right so we should shift up our start so we'll say that now start equals mid else and we could write this more elegantly but we can do that after if target is greater than num this is the three or less than num then our end is going to be equal to mid and then this for loop will just go again or this while loop will go again until we hit this kind of base condition and if we exit the loop without ever finding a match then we can return negative one let's see if this works look at that works and so if we wanted to be a little bit more elegant here we could have said that this was like lf and this was even an else condition or you could do another lf so basically it doesn't try to run these statements if you enter this statement hopefully that kind of makes sense binary search is very well documented so if this kind of quick code solution didn't make sense then you definitely can find resources online that can provide more i guess algorithms type high level intuition about binary search let's go ahead and try submitting this and i hope we didn't miss like an edge case or something seems to be going kind of slow time limit exceeded what did we do something silly is there any case that this i feel like we might get into a never-ending loop right so what i'm thinking about is uh it doesn't really make sense for us to just start the new start at the exact midpoint or the end at the exact midpoint because we've already looked at that midpoint so we don't need to include it in our range so let's just go ahead and make that the start is whatever the midpoint one was plus one and the end if we have to change that it's whatever the middle point was minus one so that you kind of are shifting in the right direction so like if we found the midpoint was eight then we do eight the index of eight plus one to get just this instead of looking at 8 again in our range so i think that that hopefully will solve the time limit exceeded because basically i think we were getting it into an infinite loop and that's why it wasn't working so i'm going to try running the code again accepted let's submit it cross our fingers accepted look at that and honestly it didn't run that that much faster than our first solution but honestly i believe that that's probably because of the test cases that they used for this problem but feel free always to like look at the solution so let's see what the solution actually does seems like pretty similar there's even a video solution here yeah it looks pretty similar if just kind of some slight nuance yeah and instead of using a time complexity of o of n that we did originally now it's o of log n cool all right we're going to do 409 longest palindrome so the question here is and if you don't remember what a palindrome is it's something that's the same forward as backwards and basically what we're trying to do is given a string we want to know how many digits would be the longest palindrome uh in that so we have a b c c c d d and we see that the output is 7 because the longest palindrome would be d cc a ccd so we need to write some code that figures this number out okay so how should we think about this well if we think about palindromes they have to be the same in you know going left to right as right to left they have to be the same forward and in reverse so really they need to be flippable and what that tells me is that really the digits that we use in it need to all be even except for whatever that middle one is if there is a middle so really if we just count the number of characters in the string that have even number of occurrences that's going to be really the longest palindrome plus if there's any odd numbers we would just do a plus one on that so it should be a pretty straightforward counting problem let's use a dictionary to do this counting so we'll say character count is an empty dictionary and what we can do is for character and string we want to do character count well if we haven't seen this character yet before we'll want to do equals character count dot get of the character but if we haven't seen it before we'll want to set it to zero and then we can do plus one this lets us fail gracefully in case character is not already in the dictionary whereas if we did something like this it would error out because character is not in the dictionary and we're trying to reference it but we're able to set it like this so that's why we're using the dot get because if it doesn't find character then it defaults to zero and then we can plus one to that okay so that would count all the characters in the string and so what basically we're going to want to do is our final count we'll say is equal to zero for character in character count well if the value so if the value so that's going to be character count of that character if it's even so mod 2 equals equals 0 so if it's evenly divisible by 2 then we want to go ahead and add to our final count all of those characters because they all could be included in a palindrome because you could use half of them in the front and half of them in the back so that equals character count the character um all right so that would add all of the even number characters and now we just need to count the odd number of characters well we only can count a single one of them because only can it be in the middle to create a valid palindrome we couldn't have them on both sides so here we just really need to have some sort of boolean that tracks whether or not we find a character count that is odd so what i'm going to say here is just an else so this would mean it's not evenly divisible by 2 then basically we just want to say that odd is present i'll say equals true and we can set a value odd is present equaling false initially and all we're going to do with this variable is at the end once we've iterated everything if we did find an odd number of values we'll just add one more to our final count and then we'll return that final count let's give this a shot run code that seemed to have worked we can try another test case it's always good to use these short strings as test cases because you always can get errors on the the short ones and also do we know that the string length is always between yeah it always has to at least be one it can't be an empty string that's another good edge case to think about so now we have the three examples they gave us oh wrong answer no so bb was wrong why was bb wrong it should have been count two oh oops if why did i not do this if odd is present then we want to increase the final count by plus one so the last one odd wasn't present so we shouldn't count that let's run it again cool let's submit come on wrong answer ccc oh interesting this is an interesting edge case it could be all of the same characters so this is what happens if you're not careful you should be thinking about the different edge cases and i was running you know i was jumping the gun there so let's think how do we incorporate this one okay so we need to add one more if statement to our condition basically what we want to do is if it is divisible by two then we add the exact character count l if it is or i guess else if it's not divisible by two then we would want to do final count um plus equals character count the character minus one so how does this work well if there's three c's right then that is not divisible by 2 so we wouldn't we'd skip this if statement and we'd enter this one well we can count the two c's because that is a a palindrome uh so we could add two there instead of three that's basically what we're doing right here and then the last thing is is there is an odd value present uh in this case it is three in general so that remaining c we can add it back in using this same if statement we had originally and then return the final count so this should work look at that accepted and submit i think that will be good this time accepted yay cool and it runs faster than 88.20 of python 3 submissions memory usage is not great though let's think what is the runtime here well we count everything every number in the string so that would be o of n and then we iterate oh so yeah we count all that that's of n and then we just iterate over our dictionary so that's also o of n because we could have n different unique characters so really our run time is bounded by o of n and that's really the best you're going to get because you do have to kind of look at every character to figure this solution out but we could do better probably in the memory usage department but i'm i'm happy with this solution next let's do 1561 maximum number of coins you can get and as always it's linked in the description so in this problem there are three end piles of coins with varying size and you and your friends will take turns taking one of the piles of coins and so in each step you'll choose three piles of coins and it's kind of we don't know which piles of coins we'll select of those three piles that we choose alice will always pick the maximum number of coins then we will pick the next maximum number of coins and then our last friend bob will pick the remaining pile and then we repeat until there are no more piles of coins so fairly straightforward problem it seems like let's look at an example so we have the piles two four one two seven eight and we kind of are just randomly choosing triplets so like you can imagine any pair of three we start with so if we picked 241 as our first triplet alice would pick the four i would pick the two and then bob would pick the remaining the one so given that we could pick any of these three at any time what is the maximum number of coins that we could ultimately get and so as we see in this example like we chose 278 first we'd get the seven and then the next triplet one two four we'd get the two and our maximum would be nine there's no way for us to get any better than that um based on how this is structured all right so when we're thinking about solving this problem let's start with kind of a very you know simple solution what would work what is the easiest thing we can think of that would work when i'm thinking about that i'm thinking about okay if we just looked at every single pair of three items like all the different combinations of triplets and then just took the max sum based on all those different combinations then we get the solution but we got to think about if that's practical there are so many different ways we could break up even just like six items into triplets of three um i'd have to do some kind of combinatorics that the word uh to figure out the exact count of that and i think in this case it would be six choose three which would give us our our count but in like other cases longer cases would be like nine choose three times six choose three uh all the way down until uh you um you know you have no more triple to go to so that would add up really quickly and i just it scares me especially given that the length could be ten to the fifth uh in total so it doesn't seem like counting all the different triplets in like summing that way makes sense so what else can we do well i think the key thing to think about is that we just really care about the maximum number of coins which we can have so all we care about is the most optimal case we don't have to care if that's probabilistically likely that this happens we just need to know in the best case scenario what happens and so if we're thinking about the best case scenario uh we'd pick the we get triplets that always have like the max number and the second max number and then the lowest number and always get that like in each triplet always would get that second max number of the remaining piles so as an example what we could show is let's take this list piles so we have two four one two seven eight well if we wanted to figure out what's optimal and it might actually work better to take like this longer example just to really demonstrate this property take this well i think we should sort it so if we sorted this we'd get 1 two three four five six seven eight nine and so what would be the most optimal thing to happen well the most optimal thing would be okay maybe our first pairing is has the eight and nine because those are the two largest numbers and then it has the smallest number for bob to pick next iteration we'd keep going so hopefully would have the next two biggest numbers the six and the seven and then maybe like the the smallest number for bob to pick so that would leave us with the biggest numbers remaining and then finally on the last iteration our last triplet would be three four five um it would be these three numbers so why would this be optimal well if we ever change one of these numbers so let's say like we put the seven in this spot instead of where how we structured it well that would mean that bob would get the seven and ultimately that would reduce what we could ultimately acquire so we always want bob to get the smallest and we always want to have the opportunity to get the second biggest thing remaining so that's why we liked these triplets so really what we have to do is just sort this list and then iterate two from the right and one from the left and keep going until we have no more items remaining and then just add up all of the second most uh from each triplet like as we're doing that just keep adding the second biggest item in each triplet so let's implement that in code and let's think about actual just real quick run time well this would be bottlenecked by how much time it takes to sort this sorting takes o of n log n so n in this case would be the pile's length so we would take that to sort it and then to iterate over this we could do that in just o n so our total run time would be o of n log n all right so what does that look like well we could say sorted piles equals sorted of piles um that's a good way to just do this in of n log n it's a built-in python keyword then so what we want to do is let's keep track of our index so for i in range the number of iterations we're going to do in total because piles is 3n we see 3n piles of coins the total number of iterations we want to do if we're grabbing three at a time is just n so let's do a length and also given our constraints we see that we know it's always going to be divisible by three so we can go ahead and do length of piles or we could do sorted piles doesn't really matter um divided by 3 to give us how many times we'll have to iterate and so for each iteration our triplet is going to be sorted piles of eye sorted piles of length of piles because our last index let's think about our last index if we have length piles then our last index is length piles -1 so i'm going to just i'm going to define this as a variable we'll say end index equals length piles minus 1 so that in this case we'd want to go our next part of our triplet would be length or that end index and then we also need to factor in our index so we apply something like minus i times 2 because we're looking at two items each time on the right side when it is sorted and then finally our last item would be sorted piles end index minus i times two that same thing as before minus an additional one just to get that offset one so that would be what's consisted in our triplet i can make this a little smaller so you see it would look something like that but let's think about do we need every item in this triplet i don't think that we do because we only care about our own individual pick so really all we care about is this last pick right here uh because that's what we're gonna take every time that's what we're gonna get based on these rules in the problem um and i think that these last two things are right we'll probably have to play around and print some stuff out to be sure but we're going to go ahead and say our value equals instead of doing this whole triplet we'll just do this last part so i'm going to just copy this and paste that in and so let's think so on the first iteration our index index is the last item in the array so if we had six items our end index would be five five minus i times two i is zero in the first case so that's minus zero so we're still at five minus one would give us four and that sounds correct next iteration would be i would be 1 that would give us 5 minus 2 which would be 3 for it to be this index minus one which would give us this one right here assuming that this is sorted i'm kind of just using this array down here in the bottom left just to show index and like think about my my head the index values here so r value equals this and really what we could do is just keep track of a count so our count equals zero and so or maybe i could even say our value equals zero and so every time we get a new item in the triplets we do plus equals our value and so once we get through this iteration we can just go ahead and return our value i believe it's run code float value cannot be interpreted as an integer why is that giving me an integer i want this to be an int so i'm guessing this division is being interpreted as a um float for whatever reason we might be able to do a floor divide to give us always an integer not positive let's try it should always be divisible we we know that from the constraints but i guess it's just kind of how the python implementation works here okay we got that working we could also try these other test cases let's try 245 and let's try this one right here both of those are working cool so i'm thinking that this solution works and realistically you know we could even make this smaller number of values but i think it's fairly neatly written out right now i guess the only confusing part would maybe be this what we're taking it from but hopefully the steps that i walk through to get to this point makes sense with that whole triplet idea so let's go ahead and submit our code accepted but it is kind of slow compared to some solutions so i wonder if there's something that we're missing here i'm thinking maybe just the way we're iterating over here is is kind of confusing or like maybe having to do these calculations every time so right now our solution is o of n log n um is there anything we can do better i feel like n log n is is realistically like one of the best you can do unless you really wanted to like do something clever with a bucketing type solution knowing that your piles can only have a range from one to 10 000 here let's look at the hints which pile of coins will you never be able to pick up well it's from the left i think we've already covered that hit number two okay yeah we we've covered both of these things i'm just wondering about the implementation honestly i'm happy with this solution so let's just look at the discussion to see if there's anything better this seems the exact same as what we're doing yeah so if we look at this solution realistically what we can do is just do a smarter summation of things instead of doing a for loop do something like this and that will be quicker but the algorithm all seems the same okay we're going to do 1472 design browser history and i really like problems like this from my own experience if i'm interviewing candidates i love to give them a problem like this where you're kind of actually building out a class or something because it really is more of a realistic feel for what their software engineering skills are so i usually in an interview process would give one of these types of problems and maybe one algorithms type problem to get a full field but i'd probably be more closely thinking about how they work on their classes and whatnot than the algorithms questions the algorithms question tells me that they're a good problem solver this type of question tells me that they have good software design principles so that's good to keep in mind with a problem like this okay so what does this problem say well where we have a browser and we always start on the home page and in this browser we can also visit another url as well as go back and forward in history a certain number of steps and so we need to implement all the details there that allow us to have a a browser such as this so we're implementing what allows us to kind of keep track of the browser history so what we need to do is first initially be able to initialize it with string home page that gives it that first item in the browser history we need to be able to visit new things which clears up all of the forward history so that's good to know too we need to go back a number of steps so a couple details there and it needs to be able to go forward a couple of steps until it returns to the most you know the last item that we've looked at the most recent item the example is here i would say like probably the details here are going to be more clear than looking at the example basically behind the scenes how they're testing this is using info like this but kind of following this trend can get you understanding what's going on so let let's just kind of work off of this and see how we do and then if we need to look at the examples a little bit more closely we can do that so i mean obviously it makes sense to start with this initialization step how do we get it to be able to be initialized with a home page and so let's keep let's start thinking about the different data structures we might need in a problem like this uh the biggest thing that i'm thinking about is that we need to keep our history in something so it makes sense to me to keep that in an array in python so i'm thinking right here what we'll do is that we'll initialize um this home page into something that we call history so we're going to say self.history equals a list with just the home page in it that's how we're going to think about history and now all these other functions in the class method they need to access self.history and do certain things with it accordingly so visit what does this visit do well visit would append to our history on top of it so what we would want to do here is just do self.history.append whatever the url is that we're now visiting another thing to keep in mind here is that it says that it clears up all the forward history so if we are at certain index in this history then we know we should clear all the so let's say we had like site 1 site 2 after the home page and we are currently on site 1 and we wanted to visit a new url well that's saying that this would be forward history and it's saying that if we were on site one then we would want to go ahead and just say this is like the new url and we'd have to clear everything let's think about that how would we want to implement that and clear all of the stuff well i think what might make sense is to also keep track of our current index and maybe you would make this like a private method like current index sometimes you use that the little underscore here to kind of signify this is like private to the browser history um it's up to you how you want to go about this i'm going to just say self.currentindex equals well it's going to equal 0 to start with just the home page so when we append our url our new current index is going to be whatever it was so self.current index equals plus equal one because we're going to take whatever we had before add 1 to that and we might not want to append this url right away because that would be appending it on top of existing history so instead maybe let's say we update the current index first and then basically say that our history is now equal to what it was before so self.history from the start so from zero to whatever the current index is now so self dot current index so that will allow us to keep everything that was already there because and then we can go ahead and do self.history dot append the url so i think this would capture then the two things that we need to do here which is clear up the forward history we'll do that first and then append the new url as the head of the forward history now let's do back well back would just move our current index so basically what we want to do here is do self.current index is going to equal and let's be clever here we can move steps back in history if you can only return x steps in history and steps is greater than x you'll return only x steps so it's basically like we can't go beyond the zeroth index when we're going back so what we can think about here is we could do return the max of 0 and steps or of and self.current index minus steps because if we were we had a list of let's say site 1 site 2 site 3 site 4 and let's say we were on index 3 and we wanted to go back two steps well then in this case we would go index two index one that would be two steps this would return one max of zero and 1 would allow us to get that right current index so i think we're good there and we don't have to update the history at all in that case similarly for forward we can do self dot current index equals well it can't go farther than the the max index so we could say the min of whatever the length of our history is so self.history and then the last index there would be that minus one otherwise we would go just like in the last one we do self dot current index and this time we would probably plus the steps plus steps if i make this a little smaller it will be more nicely on a single line and you could change up these names if you wanted to but i honestly think okay and then these two steps are back and forth we need to return the current url that we're at so that would be return self dot history of self.current index and this would be return self.history self.current index and this returns nothing and this is just the initialization method i think that this is good let's give it a shot accept it look at that nice and i think we can go ahead and submit accepted and it runs with pretty good memory usage pretty fast and this type of a problem as long as your solution is not um you know particularly slow it's not doing anything obnoxious i would be more concerned about making this nice and readable than trying to make it highly perform it and you would want to explain to whoever's interviewing you like this is what you're doing this is why you're doing it if you find that performance is an issue you know you could do some additional stuff to kind of speed up things with that my kind of final recommendation here would be comment your code as necessary or just clean up things as necessary is this if someone didn't hear you walking through the problem could they understand what you're doing here and for some of the things that i implemented uh i i think that uh it's it's pretty straightforward but there might be some details here that aren't clear without an explanation it's like the the one line i'm really thinking about right now is that it's not immediately clear to me um that this clears forward history so maybe i would add a comment like clears forward history here um right here and then it would be a little bit more straightforward that okay you know you're adding one because we're visiting a new site we're clearing the forward history and then add the new site hopefully this problem made sense hopefully the solution um made sense if you have recommendations on how this could be improved definitely let me know in the comments and also just keep in mind like this is another like designing classes and object-oriented programming this is another great skill set to have in an interview setting no matter if you're software engineer data scientist etc it's really nice to be able to see that someone can structure code in a succinct and understandable way so usually you're going to have to do a problem like this as well as an algorithms type question and you know the better you can do in both areas the better case you're making to the interviewer that you're a good hire candidate all right let's do problem 1110 delete nodes and return forest this is a medium problem so we're given the root of a binary tree and each node in the tree has a distinct value after deleting all the nodes with a value in some list to delete we are left with a forest and then our goal is to return the roots of the trees in the remaining forest and we can return the result in any order so to make that clear we see that we have a tree that looks something like this we see that each of these nodes has its own unique value and what we're asked to do is delete a couple of those nodes particularly in this example three and five so it's basically saying if we deleted node three and we deleted node five what are the resulting trees we're left with so as we can see if we deleted node three deleted node five we'd have one part of the tree that would be one two four and this part of the binary tree would be null and then because we deleted that three you can be left with these two just single node uh roots six and seven and that's what's our output so this is what we're trying to do in this problem so when we're doing any sort of problem that involves trees usually one of the things i start thinking about is traversing through the tree there's a couple different ways to do this uh you can kind of do like an in-order traversal which would be like one two four one two five one three six one three seven which would be an implementation of depth first search but in this case i think that really we wanna work top down so something like one two three four five six seven uh and the reason we want to work top down is i think that'll be easier as we delete nodes to kind of just uh be going from top to bottom and uh not having to like keep track of those deleted notes throughout the entire process so how would we implement breadth first search that's kind of the first thing i'm thinking about so i think when we start writing that the solution i'm going to just start with writing out something that could go through this entire tree and then we'll modify that breadth first search to delete nodes and kind of return a result accordingly you can implement breadth first search using a queue which means that the first nodes you put into some sort of q are the first nodes that you take out of that q so we can imagine defining some sort of q and well to start off the q would just be whatever root we have so we could say root and then we could do something like while while q and so what this would mean is basically while q is not empty we can pop off the root node so our node is going to be equal to q dot pop and then we want to look at for this given node we want to look at its left child and its right child so we could imagine we would add on to our kill the left child as well as the right child and given this is first in first out uh we don't want to pop off the end really we want to pop off the beginning so that for future iterations uh we're always making sure we grab the thing that was added to the queue first so we'll do we can do that like this in python okay um and basically let's see something i think if we printed node.value i guess it's node.val i'm looking at this class implementation up here node.val we could see that this would be like a valid traversal of the tree so i'm just thinking about traversing the tree and then we'll modify our breadth first search and this is typically with these tree problems you're taking some sort of thing that you know about that data structure and then modifying it to fit whatever the problem requests so let's just run what this does so as we can see for the example we're given here this does go ahead and print one two three four five six seven so that's good to know now what do we need to do really the question is what do we need to do to change this so that we can delete nodes and so to do this i would think about what what items do we need to keep track of well one thing that we need to keep track of is all the distinct roots so we'll have to implement that into our code somehow and then the other thing is for a specific tree we need to modify that tree so that any deleted nodes get updated in that tree accordingly so like if we had the node 1 here we need to make sure that we said set node like the right node of this one to be none because it gets deleted here so there's kind of two different tasks going on let's take care of just updating a existing tree first so basically what we can think about is we're not going to automatically append node.left or node.right to our queue we're going to first check to see if node.left or no.write even exists in the first place so we can do something like if node.left so if that's not none then we want to keep going down that part of the tree we're going to continue our search so we can do q so this is basically what we're already doing before but it's just we're adding an additional check that make sure that we actually have that child defined so q.append node.left and then the second thing we want to do is for whatever tree we're looking at so for the tree with root we want to just make sure that we should be counting this node that we're traversing down as part of that original roots tree and the only way we wouldn't include it is if that node happened to be deleted so let's say if node.left is in so in to delete well then we would want to set node.left equal to none so basically for the root node that we're looking at if we find that it's left child should be deleted then we ultimately just want to remove that from the tree because now we've gotten to like a disjoint root a disjoint node so we can repeat that with node.write so i'm just going to copy and paste so node.write cue.pan node.right if node.write.val is end to delete then node.right equals none so that's just basically seeing that's basically taking care of this aspect of things we are properly setting something in the case that we have deleted nodes so if i run the code here and then i guess once we're done with the queue we could just let's just to start return route and see how we've updated the tree so as we can see by doing this so as we can see by doing this right here we've updated the tree properly like we like we have here so let's look at that one more time but now we need to figure out how do we capture those disjoint nodes so that's the big question well maybe what we should do is let's keep track of our output kind of as a global parameter of this class so i'm going to say i'm going to just initialize this class to have an empty output list by default and basically any time we call this delete nodes method let's add the whatever root we're looking at so in this case it would be this root so self.output.append root and so what do we accomplish by doing that well what we can smartly do is imagine that we had in our nodes to delete from this tree up here in the example we were told to delete node one well if the node we were looking at was deleted then we would know we would have root nodes at two and three i'm assuming that three wasn't actually in this list just assuming one was the only thing we were deleting so basically you know that two and three are like the root nodes of the disjoint trees well what we can do is basically another if statement so if node.val in to delete so basically this is a different scenario um if that value is into delete then let's recursively call delete nodes on the left and right child so do we have to call self dot delete nodes on root or node dot left and self dot delete nodes on node dot right and because of the way the function's defined we'll also pass in to delete to both of these things and so what we get with this recursive call to delete nodes is that now um the left and the right nodes of a deleted node will get appended to our output and i guess one thing we should change right here is we need to only append if root.val is not in to delete okay so now if we look at our solution if we i think just run this uh none type oh okay i think one thing we also need to do is double check that no dot left is defined and double check that node.right is defined before we try to call that recursively otherwise we'll get an error when we try to do something like this okay okay oh and then we need to now instead of returning root here we would want to do self.output dot append oh wait a sec didn't we just do that up here we want to return the output so return self.output look at that we got it um i think that looks good basically if we're need if we're looking at a node that needs to be deleted then we want to just add the left and right nodes as like new distinct roots and we recursively call the function on that uh otherwise we just keep looking at the the tree the root that we're currently examining and just keep adding things and just updating that existing tree accordingly to get something like this so let's go ahead and submit this oh no wrong answer hmm okay so we see here in this example we get an extra five node that we shouldn't so that tells me that something is getting appended twice for whatever reason i think it's basically because we shouldn't both call a recursive call and continue this process so i'm thinking if we add an else statement and append these inside i think that will fix things so that we don't traverse down on the left or on the right multiple times when we've done it already here accepted um not great memory usage or run time but let's just let's let's figure out what our runtime is here so the way that we're doing this is we are looking at the root node we're doing breadth first search we're doing a modified breadth first search and breadth first search is going to have a run time of the number of edges plus the number of nodes and in this case it's a one to one correspondence so it's really just a time of how many nodes we have so you could think of n and even though we're doing this you know i guess the thing i don't love about this solution is that there's a lot of if else type stuff i guess one way to i mean it's not terrible i think it's readable i know that this solution is o of n because we we modified that breadth first search so i'm happy with that honestly i feel like most of these answers will just be like slightly smarter versions of what we have here so i'm fine not changing things what i'd recommend is feel free to go to the discussion um check out like the top solution this guy elite 215 he's pops up all over the place he does a great job explaining these problems uh and honestly this looks very similar to what we're doing but it's just being a little bit smarter using this helper method instead of what we're doing with if else is so i'm happy with our solution all right that's all the problems we're going to do in this video hopefully you found this useful if you did enjoy it it would mean a lot if you throw it a thumbs up and also subscribe if you haven't also i just created a new second channel huge announcement right now um but i'm gonna be posting a lot more frequently on that channel and i'll probably be doing a lot of these types of problems so if you enjoyed this video definitely check out the second channel i'm going to start posting on that once i hit 1000 subscribers and i will definitely take requests for additional problems i could solve there whether that be leaked code problems or problems from another site if you have any questions about the contents of what we did in this video let me know down in the comments but until next time everyone peace out [Music]

Channel: Keith Galli

Views: 31,239

Rating: 4.978261 out of 5

Keywords: Keith Galli, python, programming, python 3, data science, data analysis, python programming, coding interview questions, object-oriented programming, oop, leet code, leetcode, BFS, DFS, data structures, algorithms, breadth-first search, depth-first search, sorting, sorting algorithms, leetcode problems, software interview questions, software, binary trees, dictionaries in python, python problem solving, leetcode python, time complexity, space complexity, tips, tricks

Id: qnSF8YaPx78

Length: 99min 19sec (5959 seconds)

Published: Mon Jan 18 2021