DeepLearningAI-高级全栈-一面Coding

是中国的职位，当时还没有office所以可以远程办公。第一面试纯coding，面的还不错；第二面是类似behavior面试挂掉了，就不发了。如果能通过的话，最后一面是Andrew（吴恩达）亲自面试。
Coding面试只问一道题，即使提前做完了，也不会追问更多的题目。


题目（面试官用中文解释了一遍，所以如果不想看英文可以跳到下面的中文描述）：

1. /**You are a group of students
   
2. You don’t want to go to classes but attendance accounts for the majority of your final grade for each course here.
   
3. Fortunately, you and your colleagues can sign in for each other, no one would know.
   
4. For each lecture, you need one person to attend the whole lecture time since you don't know when the professor will ask for signing in during that period.
   
5. Given all your lectures, represented as a list of tuple like (start_time, end_time), write a program that calculates what the minimum number of people you need to sign in for all lectures.
   
6. 
   
7. ```
   
8. Example 1
   
9. Input: [[1,4],[2,10],[9,11]]
   
10. 
    
11. 1   4   
    
12. -----
    
13.   2         10
    
14.   ------------
    
15.            9  11
    
16.            -----
    
17. Output: 2
    
18. 
    
19. 
    
20. Example 2
    
21. Input: [[14,16], [9,10], [13,15], [8,12], [11, 12]]
    
22. 
    
23. 
    
24. 8                  13
    
25. ---------------------
    
26. 
    
27.   9   10   11  12
    
28.   ------   ------
    
29.                    13    15
    
30.                    --------
    
31.                       14   16
    
32.                       -------
    
33. Output: 2
    . check 1point3acres for more.
34. ```
    
35. **/

复制代码

大致的意思是，给定一系列的课程，每个课程有开始时间和结束时间；课程的时间可能有重叠，一个人不能去上时间有重叠的课。问这些课程最少需要多少人可以上完。
输入的格式是一个二维数组，每个子数组只有两个数字，第一个表示开始时间，第二个表示结束时间。





------------------分割线------------------
下面是我对这道题的分析和解答，如果想自己先做一做的话可以先 不往下看！






首先，是对于题目模糊部分的澄清。这部分很重要！大多面试不仅考察你会不会做出算法题，还会考察你会不会去问清楚那些“故意”没有说清楚的部分。
比如这道题还有一些模糊的地方，括号中是面试官补充的信息：
1. 关于输入：
1.1. 表示时间的数字是整数还是浮点数？（整数）
1.2. 数字的范围？（大于0，最大可能是Integer.MAX_VALUE）
1.3. 开始和结束时间是保证有效的吗？（保证有效，每个课程的开始时间小于结束时间）
1.4. 课程是按照时间排好序的吗？（不是排好序的）
2. 关于课程时间的重叠的边界条件，如果课程A结束时间和课程B开始时间相同，它们算不算重叠？（不算重叠）

其次，是思考阶段。对于稍微复杂的题目，构思好大概的想法之后，最好能够用伪代码把思路写下来！然后对着伪代码过一下这个思路可不可行！


如果没做过类似的题可能不是很好想，可以投石问路地先给课程按照开始时间排个序。然后按照时间先后去遍历，如果能得知每个时间点上有多少课程正在进行，再把历史最大值保存，就是结果了。

“按照时间顺序遍历”的做法，如果是从0遍历到Integer.MAX_VALUE可能复杂度较高，不作考虑。

如果按照每个课程的开始时间顺序遍历，如何得知此时有多少课程正在进行？不妨将之前遍历过的课程都加入到某个容器中。遍历到某个课程的开始时间时，此时这个新课程还没有开始，之前遍历过的课程中 那些已经结束的课程就可以从容器中删除，然后将新课程加入容器中。容器size的历史最大值即是答案。

为了方便地维护和查询“所有小于等于当前时间的课程”，容器可以选最小堆，按照课程结束时间来建堆。可以看到堆里不需要用到开始时间，只需要存储结束时间。

于是伪代码如下：

1. /*
   
2. sort(lectures)
   
3. minheap.push(lectures[0][1])
   
4. for [start, end] in lectures[1:]
   
5.   while start >= minheap.top
   
6.     minheap.pop()
   
7.   minheap.push(end)
   
8.   record the maximum minheap.size
   
9. */

复制代码

接下来，有了伪代码，正式代码已经很好写了

1. import java.io.*;
   
2. import java.util.*;
   
3. 
   
4. /*
   
5. * To execute Java, please define "static void main" on a class
   
6. * named Solution.
   
7. *
   
8. * If you need more classes, simply define them inline.
   
9. */
   
10. 
    
11. class Solution {
    
12.   public int maxPersonsForCourse(int[][] courses) {
    
13.     if (courses.length <= 1) {
    
14.       return courses.length;
    
15.     }
    
16.     Arrays.sort(courses, (c1, c2) -> c1[0] - c2[0]);
    
17.     PriorityQueue<Integer> minheap = new PriorityQueue<Integer>();
    
18. 
    
19.     int res = 1;
    
20.     minheap.offer(courses[0][1]);
    
21.     for (int i=1; i<courses.length; ++i) {
    
22.       int start = courses[i][0];
    
23.       int end = courses[i][1];
    
24.       while (!minheap.isEmpty() && start >= minheap.peek()) {
    
25.         minheap.poll();
    
26.       }
    
27.       minheap.offer(end);
    
28.       res = Math.max(res, minheap.size());
    
29.     }
    
30.     return res;
    
31.   }
    
32.   public static void main(String[] args) {
    
33.     int[][] courses = new int[][]{{14,16}, {9,11}, {11,15}, {8,15}, {10, 12}};
    
34.     System.out.println(new Solution().maxPersonsForCourse(courses));
    
35.   }
    
36. }

复制代码

最后，分析一下时间复杂度：排序的平均复杂度是O(nlogn), 下边按照时间遍历时，每个课程被遍历了一遍，每个课程遍历时，往最小堆插入一个课程的复杂度是 O(logn)，弹出课程的复杂度是O(logn)。所以按时间遍历循环的复杂度也是O(nlogn)。
由于内层使用了循环弹出课程，需不需要计算成多次logn？不需要，因为整个过程中每个课程最多只会被弹出一次，从整体来看，复杂度还是O(nlogn)

最后的最后，就是使用 不同的用例来测试了！要把各种奇怪的边界也测试到！


-----

最后的最后的最后，祝各位牛年多拿offe！还求各位赏点大米ORZ！