I want to go over a question called task scheduler. This is a super super common interview, question right now: that's going on at Facebook, so it's a good one to know. As a quick note, sorry that I've not been uploading like the past month or so I actually got sick for a while, and then I was out of town - and I was studying for a bunch of stuff, so kind of can really can commit a lot of Time to uploading, but hopefully I will start uploading super regularly again. I don't really want to commit or promise anything just yet, but I really am trying to upload a lot Morgan. So hopefully I will be able to do so. So, just as a quick start up - and you guys have any kind of questions you guys home and do be sure to leave in the comments I'll try and address all the comments like I always do and I would be happy to try and solve any question.
You guys are having problems with so again today is task scheduler. This is asked by Facebook. Definitely a good question to know it says, given a character array representing task. Cpu needs to do. It contains capital letters, A to Z, where letters represent different tasks. The task can be done without the original order. Each task could be done in one interval for each interval. The CPU could finish one task or just be idle. However, there's a non-negative cooling interval and that just means between the two same tasks. There must be at least and intervals that the CPU is doing different tasks or just being idle. You need to return the least number of intervals that the CPU will take to finish all the given tasks, wow. That was a mouthful and kind of broken English, but anyways the whole gist of this problem is that we're given a bunch of tasks, some of which are recurring so here right. We see that a curves 3 times B occurs three times and we need to process all these tasks on the CPU and the only catch really is that between two same tasks, there's some non-negative cooling interval.
So if this is our example, right and n is to 2, which is the non-negative cooling interval. We output eight and the reason is because we're on a and then B and then we have to be idle and then a then B again, and we have to be idle right because we haven't had two processes in between a here. So we can't rerun a, and so we have to be idle here and here and then we output 8, because this took 1 2, 3, 4, 5, 6, 7 8 cycles. I guess, or intervals to actually run all these tasks. So the first thing that should really kind of jump out of you that jumped out at me is this is like a greedy approach, and by greedy I mean you want to run the most frequently occurring task first, and the reason for that is because then, if You run the most frequently occurring tasks.
First, you have the best chance of not running into the situation where the CPU has to be idle right. So, ideally, the CPU will be idle as little as possible and if we run the most frequently occurring tasks first, we have the best chance of it running again in the shortest time period, because we can put all the other tasks between it. So that's the first thing that jumps out. The second thing that jumps out is that, because we want to always be running the most frequently occurring tasks or if we can't run a right, which you know arguably in this scenario, is the most frequently occurring task. We want to run the next one, which would be B, so we had five processes. We always want to greedily, be taking the most frequently occurring task that we can process it process at any given moment. So we probably won't like a max-heap right, so we can keep track of all the most frequently current tasks.
So I think what we can do is we can make a map a hash map. We can count. However, many times all of our different tasks occur, throw them all in a heap and then we could be in doing our processing. So let's start doing that. Okay, so we're gon na make a hash map. So hash map will map a character which will be a task to an integer, which is how many times it occurs. Map equals new hash map cool and so now, we're gon na say for every character, C right, which is really a task in our tasks. We'Re gon na say, map top put that character with maps out yet or default C: comma, zero plus one. So if you guys haven't seen me use this function before all this is doing, is it's gon na say put whatever C maps to in the map increment? It by 1, so plus 1 or if we've never seen C before we're gon na put it in the map with a count of 1. That'S all that means well, okay, cool! So now what we want to do is we want to make a maxi right.
So, let's make a priority queue, priority queue and it's just gon na hold integers, because we don't really care what task is running necessarily. We just want to make sure that the count of the tasks is the highest or the most frequently occurring so we'll say max heap equals noon. Priority queue cannot type right now, oops. Now we need to tell the priority queue: how to organize itself right. So we're just gon na pass it function, saying if you're given two elements a and B return or compare them by saying B minus a so all that's going to do all that fancy jargon is really just gon na say. Give me a max heap. Put the max the max number at the root of the heap, so we have constant time access to it cool. So now we have a max heap, so we're never just gon na, say max heap dot. Add all we're gon na say, map dot values. So all this is doing is throwing all the values from our map into our key, and now we get to the actual processing.
So we need a return value. So I'm just gon na call this cycles because, typically, when you're dealing with CPUs you're talking about how many cycles are running and I'm sorry how many cycles have passed and how long a certain process takes in terms of cycles, things like that so cool. So now the idea is that we're gon na use our max heap to determine when we're done processing, so our max heap is empty. We'Re done.
Otherwise we have some processing to do so. We'Re gon na do that. So while our max heap is not empty right, we still have some sort of processing to do, and so now we want to do is we want to try and process again the most frequently occurring task that we can write whatever is available so like here? We couldn't run a so we would have run the next thing. Maybe there would have been a third task see in some example, then we could have run so we're gon na do is we're going to iterate through, however long the cooldown interval is and we're just going to constantly try and take tasks to process. So to do that we'll just say for in I equals 0 well, I is less than n plus 1 because it's inclusive right.
titsay
turnnoffyourmind
2087
yousharknotpass
snowghoul