Buddy List - Airbnb

https://github.com/allaboutjst/airbnb/blob/master/src/main/java/travel_buddy/TravelBuddy.java

I have a wish list of cities that I want to visit to, my friends also have city wish lists that they want to visit to. If one of my friends share more than 50% (over his city count in his wish list), he is my buddy.

Given a list of city wish list, output buddy list sorting by similarity.

        private List<Buddy> buddies;
        private Set<String> myWishList;

        public Solution(Set<String> myWishList, Map<String, Set<String>> friendsWishList) {
            this.buddies = new ArrayList<>();
            this.myWishList = myWishList;
            for (String name : friendsWishList.keySet()) {
                Set<String> wishList = friendsWishList.get(name);
                Set<String> intersection = new HashSet<>(wishList);
                intersection.retainAll(myWishList);
                int similarity = intersection.size();
                if (similarity >= wishList.size() / 2) {
                    buddies.add(new Buddy(name, similarity, wishList));
                }
            }
        }

        public List<Buddy> getSortedBuddies() {
            Collections.sort(buddies);
            List<Buddy> res = new ArrayList<>(buddies);
            return res;
        }

        public List<String> recommendCities(int k) {
            List<String> res = new ArrayList<>();
            List<Buddy> buddies = getSortedBuddies();

            int i = 0;
            while (k > 0 && i < buddies.size()) {
                Set<String> diff = new HashSet<>(buddies.get(i).wishList);
                diff.removeAll(myWishList);
                if (diff.size() <= k) {
                    res.addAll(diff);
                    k -= diff.size();
                    i++;
                } else {
                    Iterator<String> it = diff.iterator();
                    while (k > 0) {
                        res.add(it.next());
                        k--;
                    }
                }
            }

            return res;
        }

        class Buddy implements Comparable<Buddy> {
            String name;
            int similarity;
            Set<String> wishList;

            Buddy(String name, int similarity, Set<String> wishList) {
                this.name = name;
                this.similarity = similarity;
                this.wishList = wishList;
            }

            @Override
            public int compareTo(Buddy that) {
                return that.similarity - this.similarity;
            }
        }
    }

airbnb面试题汇总

你和你的兄弟都有一个wishlist，找出和你相似度最高的。follow up是给出一个max值，找出你的buddy的wishlist里不在你的wishlist里的最多max个城市，根据buddy和你的重合程度来排序

例如：
你的wishlist是 a,b,c,d

buddy1 的wishlist 是 a,b,e,f, 有两个和你的一样，所以是你的buddy

buddy2 的wishlist 是 a,c,d,g, 有三个和你的一样，也是你的budy

问题是输出一个size最多为max的推荐城市列表。当size为10时，buddy1和buddy2的wishlist中不在你的wishlist中的城市都可以加入推荐中，因为buddy2的重合度更高，所以先输出buddy2中的，所以推荐为 g,e,f 当size为2时，推荐是g,e 或 g,f

代码我只写了重合度排名，推荐的话可以按照相似度从高到低遍历，找出不在你的wishlist中的输出，输出过程中可以标记是否已经输出

def find(self, nums, nums2):
    return sorted([(sum([num in set(nums) for num in nums2[i]]) / float(len(nums2[i])), i)
                   for i in xrange(len(nums2))])