Dota2 Senate - Leetcode 649 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Dota 2 Senate which is an absolute essay of a problem I've never actually played this video game so let's go through this real quick because this is a really good question to use as an example for me to show you how you can take like a pretty complicated question like this one and really break it down because sometimes that is the point of an interview to see how your skills can take like high level requirements like this which I guess aren't really high level but these are like problem requirements and they're not exactly spelled out for you in like the easiest to understand way in my opinion like this sentence over here I had to read it like 10 times for me to understand if this Senator found the Senators who still have rights to vote are all from the same party he can announce the Victor and decide on the change in the game well I think the easiest thing to do is actually to start with the example so let's see what we're actually working with here we're only given a single input string here and what we're trying to do is return turn the party that is going to win I guess some kind of election or something like that who cares what exactly it is let's not distract ourselves with those details that are pretty irrelevant to our problem or at least our solution and in this problem we have some R's and Some D's I guess they stand for radiant and dire who cares I don't as far as I know we have some R's and D's and we have an input string that is going to be r d at least in this example but we could have some others maybe r d d or DDR or you know something really long now it's not quite as easy as just counting the number of R's and D's that would probably happen in like a normal election where here we have 3DS and here we have two r's so D's would win unfortunately it's not quite that simple here so what are the rules well they are a bit complicated at least the way it's phrased here but basically we're going to iterate through this from left to right that's very important they mention that over here which they again they don't really tell you we're starting at the beginning of the string ring they tell you here the round based procedure starts from the first Senator to the last senator in the given order that's a fancy way of saying start at the beginning of the string and move to the right but to make it even more complicated actually we are actually going to not just iterate once necessarily we can actually loop around when we're talking about voting I'll talk about that in a second but these votes are not traditional votes so this is the senator that's first going to vote what do they do are they voting for their party no actually what they're doing here is saying that this person is allowed to remove one of these D's any of them since this guy gets to go first let's just remove this one this R gets to do the same thing remove ad well I'm just going to remove this one this D gets to do the same thing remove some R I guess I'll just remove this one so now we are left with an r and a d so here are we done does it end in a tie no actually the game keeps going here we were looping through this from left to right now we still have some character so here is the part where we loop around and go back to the beginning we're back to R this guy gets to make another move and guess what all they can do is remove a d where's the D it's right over here that's what she said uh but we can go ahead and remove that and at this point clearly there are not any choices left so for R we would just go ahead and return radiant that's kind of the only part of this problem where you actually need to know what the string is the r stands for radiant the d stands for dire so after that this seems really really simple it seems pretty deterministic there's usually just going to be a single solution right we're just going to take every R and just remove a d or something or maybe skip like a future D and do the same thing for every other D well first of all it's not quite that simple there actually is a greedy approach I'll try to explain the intuition really quickly for that whenever we do happen to have a choice for example let's just make this string a little bit longer the idea is that if this R gets to choose a d that we can remove does it matter if we choose this one or if we choose this one and it kind of does we probably want to choose the one that's closest to this R intuitively we'd want to do that because we know we're going from left to right this guy is going to get a move before this guy so when we have a choice with this R to remove either this D or this D we should probably take this one because this one is going to be harder to remove remember to remove a character we need something to the left of it to actually remove those well technically we can loop around but who knows we might not get another chance there might not be another R over here to ever remove this D this guy was our only chance and now we don't have one and this D is going to still remain then and then this D is going to end up removing this R and what they end up telling us is that let's assume that each Senator is going to play this optimally so assuming that they play as best as possible which like this D is supposed to remove the one closest to it this guy is going to remove the one closest to it so that this guy actually will not get the chance to ever remove an R so that's kind of the intuition here of why we want to remove sort of the nearest neighbor uh by that I mean like the for R we want to remove the nearest D that comes next okay so that doesn't seem so bad how would we go ahead and code a solution like that up well going character by character if we find an R we want to remove the next D character and just continue this character by character now when we say remove how do we handle that removal because we probably don't want to have to actually remove it that's going to be an O of n operation we can probably lazy delete it basically we could just have like a variable counting the number of like previous R's or something like that then when we come up to a d maybe we could just skip that one at least at a high high level you can kind of get a picture of how you could solve this by it like keeping counts of R's and D's and having an array instead of just using a string because string operations are almost always Big O of n converting this to an array will actually make the most of those operations o of one except for the removals so we will have to keep track of that the last thing is how do we kind of keep track of this D being able to loop around because that's going to be really painful and if we just keep going in circles and circles and we don't really remove these values then you know if we have to keep going through the entire array so many times we might end up having like an exponential algorithm so can we do better than that and yes we can so how do we usually handle removals in O of one time from an array well usually when we remove from the end of it right using a stack so maybe we can get some intuition that a stack will help us and I know an even better data structure where you can actually also remove from the beginning in O of one so maybe a q as well here will help us so knowing that let's go ahead and try a cue just because it's more flexible than a stack but we want to handle the removals how do we remove from a queue either from the beginning or the end where we can handle the voting here like when we go from this R over here I guess we add it to the queue and do the same thing for the next R over here and now let's get to the D well this D we don't want to add it to the queue so what do we do at this point should we just skip it maybe we can just check the top of the queue or the end of the queue and if we see an R we can use that to remove the D well that wouldn't work because if there's a d over here and now we're trying to add another D we're going to see a d here and think that we don't need to remove this but if there were some previous R's over here yeah we actually do need to remove it so can't just look at the top of the queue and maybe mixing and matching these R's and D's isn't helpful for us because clearly the relative order of them matter a lot and this is where you might get the intuition for two cues or you might not and that's perfectly fine because you may have never seen this solution before it's pretty rare I think the two stacks variation is more common but here we have two cues you can guess one is going to be for the RS one is going to be for the D's clearly the relative order of the matter let's keep track of the indexes zero one two three so let's try this again here we're actually going to add zero to the cube we know that there was a r at index 0. next one let's add one to the Q next D two let's add two to the other Q we have another q now for D's and a different Q for R's now we have R let's add two to the Q here or not two actually three and lastly let's add four to the other Q over here so these are the D's these are the R's and now to actually do the simulation let's start at the beginning of both of these cues now that we've kind of separated the R's and the D's starting at the beginning of the R's and the beginning of the D's let's look at the first value and actually pop both of them we're going to pop the zero and the two and at this point we kind of know what we should do we kind of know the rules here since R is before the d r is at index 0 D is at index two so clearly the r is going to be able to remove this D this is the first D that shows up we know for sure because we're starting at the beginning of the DQ and that's exactly what we were trying to do now here is a tricky part well first of all we know that the D is going to be removed so here I'm just going to cross out the D and we actually also popped the zero so I'm going to remove that as well but are we going to take that zero and then push it again to the end or maybe the beginning what are we gonna do here well one thing I want to remind you is that this D can possibly remove the beginning right we can loop around but we haven't really accounted for that in our cues like when we look at these two values three and four we're definitely not going to say this can remove any possible R's because they're all to the left so so that's where this kind of comes in where after we pop that we have visited it we know it's going to still remain in the queue but we want them a value to be modified and also the position so it makes sense to pop this and then just append it to the end and the new value that we're going to give it is going to be the original index plus n we're adding this offset of n because we want to add the length so that any value in the array can then loop around and actually not just loop around once but loop around multiple times so here if we added that four we might you know pop that for and then make it into an eight at some point because we're going to keep looping but that doesn't necessarily mean we're iterating through the array multiple times remember we're only visiting each of these values from the Queue at most once whether we're pushing or popping it it's always going to be a constant time operation and we're going to do it roughly Big O of n times we haven't really gone through this entire example but I've pretty much touched on all the points that I wanted to I do encourage you to walk through the rest of this I'll go through a couple more we're gonna pop from the left both of these one and four which one is smaller one so that's the one we're gonna pop but also re-push we're gonna add that offset of n which is the length here which is five which makes me realize that this value here should have been a five so I'm really sorry about that but also this value that we just popped was one plus an offset of five that gives us a six over here but this four over here was actually removed and now we end up at the end of our solution how do you know when to stop well here one of the cues is empty that means there's only ours remaining that means the r's are going to win and from this example that does make sense I think what would happen is this R removes this this R removes this and then we're done I will admit though this solution is definitely definitely not easy to come up so don't beat yourself up about it if you weren't able to solve it yourself now let's go ahead and try to code it up so the first thing I'm going to do is actually convert the input string into a list usually operations on strings are expensive because strings are immutable but lists are immutable like we can change this in O of one I'm also going to create two cues that are going to be poorly named D and R for the DQ and the RQ which is going to be a bit funky to keep saying those because this is DQ and this is what I'm also going to reference has the DQ but going now to the Senate list we're going to iterate through it getting the index and the character we can do that using enumerate in Python and using that character all we need to check is whether it's an r or a d and then we can add the index of it to the respective queue for so for this one we add it to the RQ and this one we add it to the DQ so now we did the initialization where we set up our cues now to actually run the simulation we're going to continue knew while both cues are non-empty because as soon as one of the cues is empty we know we can stop and actually once we know that one of the cues is empty we can return either radiant or dire and we can return radiant if R is not empty we know one of these cues is going to be empty we have to figure out which one if R is empty or rather if it's non-empty then we return radiant if dire is or rather just really the else case then we return dire so whichever Q is non-empty that's the one we're going to return well the string we're going to return the string we're not returning the Q okay but now for the simulation we pop from both cues so D turn what was that well we'll get it from the Q D dot op left and R turn r dot hop left and our question is which one of these is smaller is D turn smaller if it is we don't have to pop from the cube because we already really did that what we have to do if R is smaller is ADD its value back to the queue but all the way to the right and make sure to add the offset which is the length of the Senate and then we can do a very similar thing in the else case where D has a smaller value so we'll append to the DQ and we will append our turn to the DQ with the offset and then I think we are pretty much done here not a lot of code but definitely not a simple solution to come up with even if you know you're supposed to use a queue this still isn't easy in my opinion but let's go ahead and run it to make sure that it works and as you can see yes it does it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and I'll see you soon