HW4

無逸煩 - Kris

207. Course Schedule

🧔‍:

你好，很高興你能參加我們這次的面談，這次想請你幫忙解決一些我們公司上遇到的一些問題，我們在日常規劃上會有一些排程的問題，當中就會有一些事情是必須在另一件事情之前完成的，如果我今天給你一個pair(a,b)，代表說你要做a之前必須完成b，好那我想問的是，假設我今天有很多pair，我能不能得到一個可以依序完成的排序，我同時還會給你一個Input是任務的個數，假設說今天任務的個數是5，則所有pairs的值都會介於1-5之間，也就是類似(1,2) (2,3)這樣，舉例來說，我會給你一個任務個數是3，他的pair會是(2,1) (3,2) 則你要告訴我說他能不能完成這個執行順序，以這題來說是能，他只要依照1 2 3來執行就可以，不行就回傳false

Hi, glad to see you in this interview, this time I want to let you help us to solve some problem that we met, in our daily life, we will have many task, but some tasks are depend on another task, for example, we need to start task A before finishing task B that task A is depend on task B, we can write this relation as (a , b) , then today’s question is if we give you many pairs of this relation, could you give me a order of these task that we can do these task according to this order, that is topological sort

I will give you two input, one is the pairs of task, second is number of task, be careful that the number of pairs is less than number of task, for example if I give you task number is 4, then the pairs of task is like (1,2) (3,4) (2,3) would not larger than 4, if these pair can make a reasonable topological sort, then return true, if cannot, return false

🙋‍♂️ :

你好，很高興認識你，在聽完你的講解後，我可以理解說我要計算出一個topological sort的意思嗎?

Hi, glad to see you, after I listen your explanation of this question, can I understand that I need to calculate a topological sort, right?

🧔‍:

對的，你可以這樣理解沒問題

Yeah

🙋‍♂️ :

那我如果假設我今天的input是一個二維Vector，第二維的vector包含了剛剛的pair[a,b]，這樣的假設是可以的嗎?

I want to make a assumption that the inputs of pairs is a 2D vector and the second dimension include the pair (x, y)

🧔‍:

可以

That’ ok

🙋‍♂️ :

好的，那我想請問任務個數跟pair的個數的範圍?

I want to ask the boundary of number of task and pairs?

🧔‍:

任務個數介於1_{2000，pair個數介於0}5000個

It would be 1~2000 and 0-5000

🙋‍♂️ :

我的pairs裡面的任一個值都會小於我的任務個數對嗎?

All the value in the pairs is smaller than the number of task, is that right?

🧔‍:

沒錯

That’s right

🙋‍♂️ :

如果任務長度是5的話，pair中是一定會包含1~5的點嗎，還是可能只有123 234之類的

If I have 5 task, will the pairs include all the number 12345? or maybe only 234 123

🧔‍:

為5的話，1~5的點都一定會出現

Yes, pairs will have all the number from 1 to number of task

🙋‍♂️ :

想請問這些pair會有重複的嗎?還是他們每個都不一樣?

are the pairs woild be duplicate or unique?

🧔‍:

都不一樣

They’re all diofferent

🙋‍♂️ :

好的，那我大致了解了題目的要求說明，我的解法會需要去記錄兩個東西，一個是對每個點i記錄要在i之後完成的點，我會用一個二維vector去做儲存，把它叫做after 相鄰的意思

另一個是紀錄每個點還有幾個前置作業要去完成，我把它叫做indegree

有了這兩個後，我只需要一個q，先將indegree內的值為0的點取出，因為這些點沒有前置作業，可以直接去加入topo，

之後就每次從q pop一個值加入topo sort，同時間依據after把要在該點之後執行的點的indegree - -，代表該點已執行了，這些點依賴的個數-1，並將indegree減到0的加入到q中，因為這些點已經沒有前置作業了，重複直到q為空( 畫圖應該比較好解釋)

OK, I basically understand the question, to solve the topological sort , my solution need to record two information, first is record the points that need to start after point i for each points, it will need a 2d vector to store the points for each points, i call it “after”

Next, i need to calculate the number of indegree of each points, it can consider as the numbers of previous tasks for each points, I call it “indegree”

after that , i create a queue, then put the point that indegree equall to 0 in the queue, then go to the loop, each time i will pop a point in queue, then add it to the topological sort, then accroding to “after”, decrease indegree of the points that depends on this current point, if the indegree of some points decrease to 0, add it to queue, then loop again, until q is empty

🧔‍:

好的，那請問你要怎麼判斷是不是真的存在topo的順序?

OK, So how do you decide if exist a topological sort?

🙋‍♂️ :

我只要將我結果得出的topo跟任務長度去做比較，如果不等長代表我有幾個任務沒辦法放進topo裡面，就回傳false，否則回傳true

I compare the length of my topological sort with task number if equall return true, else return false

🧔‍:

我聽完覺得沒什麼問題，那請你開始實作吧

I think it it no problem

🙋‍♂️ :

class Solution {
public:
    bool canFinish(int numTasks, vector<vector<int>>& pairs) {
        //after[i]紀錄所有要在i之後才能做的j
        vector<int> after[numTasks];
        for(auto it: pairs){
            after[it[1]].push_back(it[0]);
        }
        //indegree[i]紀錄i有幾個前置要先完成才能做
        vector<int> indegree(numTasks);
        for(int i=0;i<numTasks;i++){
            for(auto it:after[i]){
                indegree[it]++;
            }
        }
        //將沒有前置的加入q
        queue<int> q;
        for(int i=0;i<numTasks;i++){
            if(indegree[i] == 0){
                q.push(i);
            }
        }
        //q pop出去的即為topological sort的順序
        vector<int> topo;
        while(!q.empty()){
            int node = q.front();
            q.pop();
            
            topo.push_back(node);
            for(auto it:after[node]){
                indegree[it]--;  //移除同時，將跟他相依的點的indegree--
                if(indegree[it] == 0) q.push(it); 
            }
        }
        if(topo.size() == numTasks) return true;
        return false;
    }
};

🧔‍: 可以告訴我這個做法的時間跟空間複雜度嗎?
Can you tell me the time amd space complexity of this solution?\

🙋‍♂️ :
Because I need to create the after and indegree, we call the numtask is N and number of pairs is M, then the after 2D vector's space complexity is O(m+n) and indegree is O(n), so the total space complexity is O(m+n)

Then, the time complexity is O(m+n), because we calculate "after" is O(n)
and calculate indegree is O(n) and

🧔‍:

好的我看完之後覺得還行， 那我這邊如果請你回傳拓樸排序，如果有的話，沒有回空字串，請問你的code應該怎麼去做修改

After checking the code i think it is fine, if I want you to return the topological sort not the true/false, how to modify it?

🙋‍♂️ :

modifying…..

🧔‍:

好的，那這題我們就到這裡

OK, that it the end of this interview

學期檢討

自己學過的很多知識都一閃而過，沒有留在腦袋裡，也了解到自己的不足，很多甚至是常識的知識也不甚了解，所以透過這堂課對自己有更深的了解，並在慢慢去補強自己的一些弱點，也包括面試的部分。