無逸煩 - 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