Airbnb phone interview

45 min phone coding session for one question only.

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

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

The expectation is to finish the code and have some test cases, and my performance is below that bar.
Never try to solve a NP problem, and was shocked the expectation is a bug-free brute force solution.

根据地里的面经 这题好久没考了 个人感觉不适合面试

jason524 发表于 2019-3-3 09:54
根据地里的面经 这题好久没考了 个人感觉不适合面试

agree. don't see the point to test coding ability by this question.
unfortunately I was the interviewee, not the interviewer.

这家确实很随缘，啥题bar都是一样，主要看运气遇到啥题

就是用SCC先把每个强连通分量当成一个点，此时图里不会再有环，再数有多少个入度为0的点就行。

哪道题目？ 积分不够

这题我感觉就先把入度为0的点全去掉就可以了，然后剩下的就是入度为0的点，剩下几个全返回，代码很简单，如果不对请指正：

1. import java.util.*;
   
2. 
   
3. public class MinNodesToTraverseGraph {
   
4. 
   
5.     private void DFS(Set<Integer> visited, int index, List<Integer> ret, Map<Integer, Set<Integer>> hash) {
   
6.         visited.add(index);
   
7.         for(int val: hash.getOrDefault(index, new HashSet<>())) {
   
8.             if(ret.contains(val)) ret.remove(val);
   
9.             if(!visited.contains(val)) {
   
10.                 DFS(visited, val, ret, hash);
    
11.             }
    
12.         }
    
13.     }
    
14. 
    
15.     public List<Integer> findMin(int[][] edges, int n) {
    
16.         Map<Integer, Set<Integer>> hash = new HashMap<>();
    
17.         for(int[] edge: edges) {
    
18.             if(edge[0] == edge[1]) continue;
    
19.             hash.computeIfAbsent(edge[0], k -> new HashSet<>()).add(edge[1]);
    
20.         }
    
21.         Set<Integer> visited = new HashSet<>();
    
22.         List<Integer> ret = new ArrayList<>();
    
23.         for(int i = 0; i <= n; i++) {
    
24.             if(visited.contains(i)) continue;
    
25.             ret.add(i);
    
26.             DFS(visited, i, ret, hash);
    
27.         }
    
28.         return ret;
    
29.     }
    
30. 
    
31.     public static void main(String[] args) {
    
32.         MinNodesToTraverseGraph traverseGraph = new MinNodesToTraverseGraph();
    
33.         int[][] edges = new int[][] {{2, 9}, {3, 3}, {3, 5}, {3, 7}, {4, 8}, {5, 8},
    
34.                 {6, 6}, {7, 4}, {8, 7}, {9, 3}, {9, 6}};
    
35.         List<Integer> ret = traverseGraph.findMin(edges, 9);
    
36.         for(int val: ret) {
    
37.             System.out.print(val + " ");
    
38.         }
    
39.         System.out.println();
    
40. 
    
41.         edges = new int[][] {{1, 2}, {2, 3}, {3, 4}, {1, 5}};
    
42.         ret = traverseGraph.findMin(edges, 5);
    
43.         for(int val: ret) {
    
44.             System.out.print(val + " ");
    
45.         }
    
46.     }
    
47. }
    

复制代码

补充内容 (2019-3-18 15:41):
入度不为0的点去掉，剩下不为0的就是答案，这里发代码格式太乱了

Now I felt blessed to be rejected by Airbnb