狗家阳谷昂赛特

上个月面的，因为有内推所以recruiter给skip了电面。4轮算法+1轮BQ
1. 两个人玩占领二叉树的游戏，二叉树的node可以往parent，left child，right child走，问如果你是后者开始占领的人，选哪个点获胜的可能性最大。
Follow up：如果你是先走的人，应该选哪一个点开

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

什么时候全部都互相成为好朋友。
5. BQ 主要问做了什么项目，如何跟同事合作的。还问了Accessibility相关的问题，如何让客户更好的使用产品。

tianjiayou 发表于 2019-8-20 11:15
我其实没get到。。因为每个课程的indegree和outdegree不一定是1，这样的话，怎么算呢？

感觉还是可以做，和indegree，outdegree并没有太大关系

1. class Solution {
   
2.     public int minSemester(int numCourses, int[][] prerequisites,int k) {
   
3.         int completedCourses = 0;
   
4.         List<Integer>[] nextCourses = new List[numCourses];
   
5.         int[] height = new int[numCourses];
   
6.         for(int i =0; i<numCourses; i++){
   
7.             nextCourses[i] = new ArrayList<>();
   
8.         }
   
9.         int[] incomingEdgesCount = new int[numCourses];
   
10.         for(int[] i:prerequisites){
    
11.             incomingEdgesCount[i[0]]++;
    
12.             nextCourses[i[1]].add(i[0]);               
    
13.         }
    
14.         // for(int i : incomingEdgesCount){
    
15.         //     System.out.print(i+" ");
    
16.         // }
    
17.         for(int i = 0; i < height.length; i++){
    
18.             if(height[i] == 0)
    
19.                height[i] = getHeight(height,nextCourses,i);
    
20.         }
    
21.         
    
22.         PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>(){
    
23.             public int compare(int[] a, int [] b){
    
24.                 return b[1] - a[1];
    
25.             }
    
26.         });
    
27.         // Add all nodes that have indegree zero to the BFS queue
    
28.         for(int i = 0; i<incomingEdgesCount.length; i++){
    
29.             if(incomingEdgesCount[i] == 0){
    
30.                 pq.offer(new int[]{i,height[i]});
    
31.             }
    
32.         }
    
33.         // Bfs starting with indegree 0  
    
34.         int semester = 0;
    
35.         while(!pq.isEmpty()){
    
36.             semester++;
    
37.             int num = pq.size();
    
38.             for(int g = 0; g < k && !pq.isEmpty() && g < num; g++){
    
39.             int[] course = pq.poll();
    
40.             completedCourses++;
    
41.             for(int i : nextCourses[course[0]]){
    
42.                 incomingEdgesCount[i]--;
    
43.                 if(incomingEdgesCount[i] == 0){
    
44.                     pq.offer(new int[]{i,height[i]});
    
45.                 }
    
46.             }
    
47.             }
    
48.         }
    
49.         //System.out.println(completedCourses);
    
50.         return semester;   
    
51.     }
    
52.     private int getHeight(int[] height,List<Integer>[] nexts,int idx){
    
53.         List<Integer> next = nexts[idx];
    
54.         if(next.size() == 0){
    
55.             return 1;
    
56.         }
    
57.         if(height[idx] != 0){
    
58.             return height[idx];
    
59.         }
    
60.         int max = 0;
    
61.         for(int n : next){
    
62.             max = Math.max(max,getHeight(height,nexts,n));
    
63.         }
    
64.         return max + 1;
    
65.     }
    
66. }

复制代码

tianjiayou 发表于 2019-8-21 02:56
我觉得还是有问题，这种做法我想过;
看下我这个例子；这里2是7的parent（实在是不好画 lol）1是2,3,4,5 ...

没有问题啊，345的height都是3，而2的height是2，所以先入345，再入2,6。下面是我跑的结果
0
243
15
6
total：4

第一个问题是 Leetcode 1145 新题
https://leetcode.com/problems/binary-tree-coloring-game/

支持下楼主分享，很有参考意义

请问第二题是那个投票面经题？如果不是，能请楼主解释一下？已加米

请问第一题的那个获胜条件是什么？

请问，第一题，对方经过的已经占领的点，我还可以经过吗 或者我只能经过那些未被占领的点？

求问楼主course schedule的follow up怎么回答的？

tianjiayou 发表于 2019-8-20 06:02
求问楼主course schedule的follow up怎么回答的？

我的思路是用priorityQueue每次pop剩余课程最多的课程串，比如1->2->3->4, 5->6, 7->8，三个课程序列，k=2的时候，上课顺序1,5 -> 2, 7 - > 3,6 -> 4,8 这样

支持楼主分享

zzwzzw435 发表于 2019/08/20 10:37:16


我的思路是用priorityQueue每次pop剩余课程最多的课程串，比如1->2->3->4, 5->6, 7->8，三个课程序列，k=2的时候，上课顺序1,5 -> 2, 7 - > 3,6 ...

我其实没get到。。因为每个课程的indegree和outdegree不一定是1，这样的话，怎么算呢？

crlyw 发表于 2019-8-19 21:40
请问第一题的那个获胜条件是什么？

获胜条件是最后能占领最多的Nodes