Preference list - Airbnb

https://github.com/allaboutjst/airbnb/blob/master/README.md

Given a list of everyone's preferred city list, output the city list following the order of everyone's preference order.

For example, input is [[3, 5, 7, 9], [2, 3, 8], [5, 8]]. One of possible output is [2, 3, 5, 8, 7, 9].

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/preference_list/PreferenceList.java

        public List<Integer> getPreference(List<List<Integer>> preferences) {
            Map<Integer, Integer> inDegree = new HashMap<>();
            Map<Integer, Set<Integer>> nodes = new HashMap<>();
            for (List<Integer> l : preferences) {
                for (int i = 0; i < l.size() - 1; i++) {
                    int from = l.get(i);
                    int to = l.get(i + 1);
                    if (!nodes.containsKey(from)) {
                        inDegree.put(from, 0);
                        nodes.put(from, new HashSet<>());
                    }
                    if (!nodes.containsKey(to)) {
                        inDegree.put(to, 0);
                        nodes.put(to, new HashSet<>());
                    }
                    if (!nodes.get(from).contains(to)) {
                        Set<Integer> s = nodes.get(from);
                        s.add(to);
                        nodes.put(from, s);
                    }
                    inDegree.put(to, inDegree.getOrDefault(to, 0) + 1);
                }
            }
            Queue<Integer> q = new LinkedList<>();
            for (int k : inDegree.keySet()) {
                if (inDegree.get(k) == 0) {
                    q.offer(k);
                }
            }
            List<Integer> res = new ArrayList<>();
            while (!q.isEmpty()) {
                int id = q.poll();
                res.add(id);
                Set<Integer> neighbors = nodes.get(id);
                for (int next : neighbors) {
                    int degree = inDegree.get(next) - 1;
                    inDegree.put(next, degree);
                    if (degree == 0) q.offer(next);
                }
            }
            return res;
        }

airbnb面试题汇总

每个人都有一个preference的排序，在不违反每个人的preference的情况下得到总体的preference的排序 拓扑排序解决(https://instant.1point3acres.com/thread/207601)
https://www.1point3acres.com/bbs/thread-218938-1-1.html

vector<int> preferenceList(vector<vector<int> > &preList) {
    unordered_map<int, unordered_set<int> > mp;
    unordered_map<int, int> in;
    vector<int> ans;
    for(auto lt : preList) {
        for(int i = 1; i < lt.size(); ++i)
            mp[lt[i - 1]].insert(lt[i]);
    }
    for(auto m : mp)
        for(auto s : m.second)
            in[s]++;
    queue<int> q;
    for(int i = 0; i < preList.size(); ++i)
        if(!in.count(i)) {
            q.push(i);
            ans.push_back(i);
        }
    while(!q.empty()) {
        int c = q.front();
        q.pop();
        auto next = mp[c];
        for(auto s : next) {
            if(--in[s] == 0) {
                q.push(s);
                ans.push_back(s);
            }
        }
    }
    return ans;
}

Airbnb Preference List 起始时如何每次优先选择person1的选项？
https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=506275
Airbnb Preference List里，有一个要求是 break tie by person 1。
我看到的答案，初始queue为空时， 是把indegree 为0的元素选进queue。 如果有多个indegree为0的元素， 这么简单选择是不是就不是优先选择person1的选项了？

可以把queue改成PriorityQueue， 排序算法自己定义，这样ind 为0时就是你想选的那个元素了。 不过这样复杂度会增加从O(1) 变成O(logn)