compass经典高频题 game rank解法

给一系列比赛结果，例如“a beats b”, “b beat c”，“c beat d”；输出最终排名，这个例子是abcd，算是alien dictionary的变形。
不存在circle，例如“d beats a”。然后问了time and space complexity，还有会用什么样的test case去测试。

先上代码

1. public class GetGameRank {
   
2. 
   
3.     public static void main(String[] args) {
   
4.         // write your code here
   
5.         String[] test1 = new String[]{"a beat b", "b beat c", "c beat e"};
   
6.         getOrder(test1).forEach(x -> System.out.print(x + " ")); //a b c e
   
7.         System.out.println();
   
8. 
   
9.         String[] test2 = new String[]{"a beat b", "a beat c"};
   
10.         getOrder(test2).forEach(x -> System.out.print(x + " ")); //a b c OR a c b
    
11.         System.out.println();
    
12. 
    
13.         System.out.println(getOrder(null).size() == 0);
    
14. 
    
15. 
    
16.         String[] test3 = new String[]{"a beat b", "b beat c", "c beat e", "e beat f", "e beat d", "d beat k"}; // a b c e d k f
    
17.         getOrder(test3).forEach(x -> System.out.print(x + " ")); //a b c e
    
18.         System.out.println();
    
19.     }
    
20. 
    
21.     public static List<String> getOrder(String[] games) {
    
22.         LinkedList<String> res = new LinkedList<>();
    
23.         if (games == null || games.length == 0) return res;
    
24.         Map<String, Integer> inDegree = new HashMap<>();
    
25.         Map<String, List<String>> graph = new HashMap<>();
    
26.         for (String game : games) {
    
27.             String[] team = game.split(" beat ");
    
28.             inDegree.put(team[1], inDegree.getOrDefault(team[1], 0));
    
29.             inDegree.put(team[0], inDegree.getOrDefault(team[0], 0) + 1);
    
30.             graph.computeIfAbsent(team[1], x -> new ArrayList<>()).add(team[0]);
    
31.         }
    
32.         Queue<String> queue = new LinkedList<>();
    
33.         Iterator<Map.Entry<String, Integer>> iterator = inDegree.entrySet().iterator();
    
34.         while (iterator.hasNext()) {
    
35.             Map.Entry<String, Integer> entry = iterator.next();
    
36.              if (entry.getValue() == 0) {
    
37.                  queue.offer(entry.getKey());
    
38.                  iterator.remove();
    
39.              }
    
40.         }
    
41. 
    
42.         while (!queue.isEmpty()) {
    
43.             String curr = queue.poll();
    
44.             List<String> next = graph.get(curr);
    
45.             res.addFirst(curr);
    
46.             if (next == null || next.size() == 0) continue;
    
47.             for (String n : next) {
    
48.                 inDegree.put(n, inDegree.get(n) - 1);
    
49.                 if (inDegree.get(n) == 0) {
    
50.                     inDegree.remove(n);
    
51.                     queue.offer(n);
    
52.                 }
    
53.             }
    
54.         }
    
55.         return res;
    
56.     }
    
57. }

复制代码

首先看到这种题 一个压着一个 第一个想到的就是topological sort （拓扑排序）

首先我们要将这个String 进行拆分

每个String的格式基本都是

xxxx beat yyyy

用 String[] team = game.split(" beat "); 来进行拆分成两个队伍

拓扑

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

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

这里不是我为了展现代码风骚来装逼才使用 iterator. 因为使用for loop来循环这个map 然后遇到indegree为0的entry 然后remove掉这个entry会导致concurrentModificationException

Iterator.remove()不会抛出ConcurrentModificationException,因为这是在迭代时修改集合的允许方式.
面试的时候记得避坑！

1.         Iterator<Map.Entry<String, Integer>> iterator = inDegree.entrySet().iterator();
   
2.         while (iterator.hasNext()) {
   
3.             Map.Entry<String, Integer> entry = iterator.next();
   
4.              if (entry.getValue() == 0) {
   
5.                  queue.offer(entry.getKey());
   
6.                  iterator.remove();
   
7.              }
   
8.         }

复制代码

这个我就不仔讲了 详情大家感兴趣可以去网上搜搜看

👍

想问如果"a beat c" "b beat c", 最后a和b怎么排名?

同学，感谢分享代码和这么详细的解析。如果你把indegree的map和graphmap的key-value顺序颠倒的话，你可以直接res.add(cur)把cur添加到list的末尾了。

哥们 我也马上去onsite 能再多说点onsite面试的事情吗

https://www.youtube.com/watch?v=ddTC4Zovtbc&t=542s
感觉这个方法简单些，先建图然后对图bfs就好了

说错了 应该是dfs

这个哪里是dfs？ 典型的图的遍历 找到入读为0 的点 用queuebfs

楼主这个是高频题？我都没在面经里看到过。。。