Wizards - Airbnb

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

There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard as square of different of i and j. To find the min cost between 0 and 9.

For example:

wizard[0] list: 1, 4, 5


wizard[4] list: 9


wizard 0 to 9 min distance is (0-4)^2+(4-9)^2=41 (wizard[0]->wizard[4]->wizard[9])

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/ten_wizards/TenWizards.java

X. BFS

        public List<Integer> getShortestPath(List<List<Integer>> wizards, int source, int target) {
            int n = wizards.size();
            int[] parents = new int[wizards.size()];
            Map<Integer, Wizard> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                parents[i] = i;
                map.put(i, new Wizard(i));
            }

            map.get(source).dist = 0;
            Queue<Wizard> queue = new LinkedList<>();
            queue.offer(map.get(source));
            while (!queue.isEmpty()) {
                Wizard curr = queue.poll();
                List<Integer> neighbors = wizards.get(curr.id);
                for (int neighbor : neighbors) {
                    Wizard next = map.get(neighbor);
                    int weight = (int) Math.pow(next.id - curr.id, 2);
                    if (curr.dist + weight < next.dist) {
                        parents[next.id] = curr.id;
                        next.dist = curr.dist + weight;
                        // queue.offer(next);
                    }
                    queue.offer(next);
                }
            }

            List<Integer> res = new ArrayList<>();
            int t = target;
            while (t != source) {
                res.add(t);
                t = parents[t];
            }
            res.add(source);

            Collections.reverse(res);
            return res;
        }
    }

    class Wizard implements Comparable<Wizard> {
        int id;
        int dist;
        // Map<Integer, Integer> costs;

        Wizard(int id) {
            this.id = id;
            this.dist = Integer.MAX_VALUE;
            // this.costs = new HashMap<>();
        }

        @Override
        public int compareTo(Wizard that) {
            return this.dist - that.dist;
        }

X. Dijkstra
29. Ten Wizards: Dijkstra解法，使用Priorityqueue每次pop出cost最小的点，为了记录path，用一个数组去记录到达过的点，在每个点中记录每个到达这个点的父节点，这样做既能从后往前把路径串起来也能通过判断该数组中某位置是否为空来判断此位置是否已经访问过来避免重复路径。

        public List<Integer> getShortestPath(List<List<Integer>> wizards, int source, int target) {
            if (wizards == null || wizards.size() == 0) return null;
            int n = wizards.size();
            int[] parent = new int[n];
            Map<Integer, Wizard> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                map.put(i, new Wizard(i));
            }

            map.get(source).dist = 0;
            Queue<Wizard> pq = new PriorityQueue<>(n);
            pq.offer(map.get(source));
            while (!pq.isEmpty()) {
                Wizard curr = pq.poll();
                List<Integer> neighbors = wizards.get(curr.id);
                for (int neighbor : neighbors) {
                    Wizard next = map.get(neighbor);
                    int weight = (int) Math.pow(next.id - curr.id, 2);
                    if (curr.dist + weight < next.dist) {
                        parent[next.id] = curr.id;
                        pq.remove(next);
                        next.dist = curr.dist + weight;
                        pq.offer(next);
                    }
                }
            }

            List<Integer> res = new ArrayList<>();
            int t = target;
            while (t != source) {
                res.add(t);
                t = parent[t];
            }
            res.add(source);
            Collections.reverse(res);
            return res;
        }

airbnb面试题汇总

There are 10 wizards, 0-9, you are given a list that each entry is a list of wizards known by wizard. Define the cost between wizards and wizard as square of different of i and j. To find the min cost between 0 and 9.

说白了，就是带权重的最短距离，最优解是Dijkstra algorithm。似乎面试官说，只要普通的BFS能得到解也是可以的，Dijkstra我最近正好写过，所以也写出来了。（https://instant.1point3acres.com/thread/218032）

def min_distance(wizards, start=0, end=9):
     # info = collections.defaultdict(set)
    # for idx, wizard in enumerate(wizards):
    #     info[idx] = set(wizard)
    cur_level = {start: 0}
    ans = 0x7FFFFFFF
    for _ in xrange(10):
        next_level = {}
        for idx, cur_cost in cur_level.iteritems():
            if idx >= len(wizards):
                continue
            for nx in wizards[idx]:
                cost = cur_cost + (nx - idx) ** 2
                if nx == end:
                    ans = min(ans, cost)
                else:
                    if nx not in next_level:
                        next_level[nx] = cost
                    else:
                        next_level[nx] = min(next_level[nx], cost)
        cur_level = next_level
    return ans

unordered_map<int, int> bfs(const unordered_map<int, int>& preLevel, unordered_map<int, unordered_set<int> >& next, int& ans, int k, int end) {
    unordered_map<int, int> nextLevel;
    for ( auto pre : preLevel) {
        for (auto nx : next[pre.first]) {
            int dis = (nx - pre.first) * (nx - pre.first) + pre.second;
            if (nx == end) {
                ans = min(ans, dis);
            } else if(!nextLevel.count(nx)) {
                nextLevel[nx] = dis;
            } else
                nextLevel[nx] = min(nextLevel[nx], dis);
        }
    }
    return k == 1 ? nextLevel : bfs(nextLevel, next, ans, k - 1, end);
}

int wizards(const vector<vector<int> > &wizards, int start, int end) {
    unordered_map<int, unordered_set<int> > next;
    unordered_map<int, int> curLevel;
    int ans = INT_MAX;
    curLevel[start] = 0;
    for (int i = 0; i < wizards.size(); ++i) {
        for (auto nx : wizards[i]) {
            next[i].insert(nx);
        }
    }
    bfs(curLevel, next, ans, end, end);
    return ans;
}

https://instant.1point3acres.com/thread/218032