OA原题描述参考：

注意：具体抽到的题目可能会有细微变化。

假设有个Movie类，

public class Movie

{

int movieId;.

float rating;

List<Movie> similarMovies

}

现在要求找到 k个和movie最相似 的movies。

函数的signature大概是这样的：

public static List <Movie> getNearest(Movie movie, int numSimilar)。

举个栗子：

m0 <--> m1, similarity 2-google 1point3acres

mo <--> m2, similarity 3

m1 <--> m3, similarity 4

m2 <--> m5, similaity 5

如果要返回和mo最相似的movie, 那么应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的）； 如果返回3个最相似的就返回 m2, m3， m5（顺序不重要）； 如果需要返回10个，但是相似的只有9个，那么就返回9个。

source movie本身不能在返回结果里面。

可以的一个做法是 dfs + min-Heap(PriorityQueue)， 我们一直做dfs， 每次碰到一个新的movie，如果现在queue的size比 k小的话，直接加到queue里面； 如果新movie的rating比queue top movie的rating高的话， 把顶部movie

踢出队列，加上这个新的。

update: 应该返回 m5 (只有有一条路径从 m1到 m5, 并且 5是最大的） 应该返回 m5 (只要有一条路径从 m1到 m5, 并且 5是最大的）

解题思路参考：

BFS找，dfs的我没有实现。

参考答案：

package com.amazon;

import java.util.*;

/**
 * Created by Tian on 2017/4/8.
 */
public class SolutionMovieNetwork {

    Comparator<Movie> queueComp = new Comparator<Movie>() {
        public int compare(Movie a, Movie b) {
            return (a.rating - b.rating > 0 ? 1 : -1);
        }
    };

    public List<Movie> getNearest(Movie movie, int k) {
        /*
            A priorityQueue to keep minHeap of top k rating
            Use DFS level order traverse all nodes
         */
        PriorityQueue<Movie> pq = new PriorityQueue<Movie>(k, queueComp);
        Queue<Movie> queue = new LinkedList<Movie>();
        HashSet<Movie> hash = new HashSet<Movie>();

        for (Movie indegree : movie.similarMovies) {
            if (!hash.contains(indegree)) {
                queue.offer(indegree);
                hash.add(indegree);
            }
        }

//        queue.offer(movie);
//        hash.add(movie);
        while (!queue.isEmpty()) {
            Movie oneMovie = queue.poll();
            if (pq.size() < k) {
                pq.add(oneMovie);
            } else {
                if (pq.peek().rating < oneMovie.rating) {
                    pq.poll();
                    pq.offer(oneMovie);
                }
            }
            for (Movie similar : oneMovie.similarMovies) {
                if (!hash.contains(similar)) {
                    pq.offer(similar);
                    hash.add(similar);
                }
            }
        }

        List<Movie> res = new ArrayList<Movie>();
        while (!pq.isEmpty()) {
            res.add(pq.poll());
        }

        return res;
    }

    public static class Movie
    {
        int movieId;
        float rating;
        List<Movie> similarMovies;
    }
}