Friends 系列

给你一个 api, getfriends（）， 输入是一个user id， 大概是getfriends(1) - > [2, 3], 输出的user friends‘ ids，完成一个function 求出两个user 共同的朋友。写到一半，面试官说下一题。

很简单，思路349一样。虽然api返回朋友数组不会有重复，但是还是要转化为set，查询效率高O(1)。

• 给一个user id，找出潜在朋友，这个定义是不是自己朋友的朋友的朋友（不是自己的朋友，不过是自己朋友的朋友）， 有点绕，大家自己体会一下。 LZ 使用了hashmap， 和两次for loop， 最后没写完， 面试官确认了思路之后说觉得我能做出来。
• friend recommendation。问题是给定person A 返回一个list 包含推荐给A的不认识的人。顺序按照与A的mutual friends 的数量排。return friends of friends that are not this persons friends

Solution 1: HashMap + bucket sort O(m); O(n)

m: # of person's friends' friends, n: # of legal recommend friends

一共三步：HashMap存潜在好友（不是A的好友，但是是A的好友的好友）和其频率（和A共同好友的数量），然后对HashMap的key进行桶排序，排序后获得前k个潜在好友。

    public class Person {
        int id;
        HashSet<Person> friends = new HashSet<>();
    }

    private List<Integer> friendsRecommend(Person person, int k) { //assume person is A
        List<Integer> result = new ArrayList<>();
        if (person == null)    return result;
        // id : frequency
        Map<Integer, Integer> map = new HashMap<>(); // recommend id -> count
        int highestFreq = 0;
        for (Person friend : person.friends)
            for (Person recommend : friend.friends) {
                int id = recommend.id;
                if (person.friends.contains(id) || id == person.id) // don't forget 'id == person.id'
                    continue; //person A knows id, not recommend
                map.put(id, map.getOrDefault(id, 0) + 1);
                highestFreq = Math.max(highestFreq, map.get(id));
            }
        // bucket sort 'recommend list'
        List<Integer>[] buckets = new List[highestFreq]; //index is freq, value is id.
        for (int id : map.keySet()) {
            if (buckets[map.get(id)] == null)
                buckets[map.get(id)] = new ArrayList<Integer>();
            buckets[map.get(id)].add(id);
        }
        //this two loops are O(k) time, when result has k nums, return it
        for (int i = highestFreq; i >= 0; i--)
            for (int j = 0; j < buckets[i].size(); j++) {
                result.add(buckets[i].get(j));
                if (result.size() == k)    return result;
            }
        return result;
    }

Solution 2: Quick Select average O(m), O(m + n^2) worst case; O(1)

    public class Person {
        int id;
        HashSet<Integer> friends = new HashSet<>();
    }
    private List<Integer> friendsRecommend(Person person, int k) {
        List<Integer> res = new ArrayList<>();
        if (person == null)    return res;
        Map<Integer, Integer> map = new HashMap<>();
        // O(m)
        for (int friend : person.friends) 
            for (int recommend : friend.friends) {
               int id = recommend.id;
               if (person.friends.contains(id) || id == person.id)    continue;
               map.put(id, map.getOrDefault(id, 0) + 1);
           }
        // O(n) average, O(n^2) worst case
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet()); // important
        int left = 0, right = list.size() - 1, pos = -1;
        while (true) {
            pos = partition(list, left, right);
            if (pos == k - 1) {
                index = pos;
                break;
            } else if (pos > k - 1)   right = pos - 1;
            else    left = pos + 1;
        }
        if (pos == -1)    return res;
        for (int i = 0; i <= pos; i++) {
            int id = list.get(i).getKey();
            res.add(id);
        }
        return res;
    }
    private int partition(List<Map.Entry<Integer, Integer>> list, int left, int right) {
        shuffle(list);
        int idx = left;//remember to add + left !!!
        Map.Entry<Integer, Integer> pivot = list.get(idx);
        int pVal = pivot.getValue();
        swap(list, right, idx);
        for (int i = left; i < right; i++) 
            if (list.get(i).getValue() > pVal)  swap(list, i, idx++);
        swap(list, right, idx);
        return idx;
    }
    private void swap(List<Map.Entry<Integer, Integer>> list, int left, int right) {
        Map.Entry<Integer, Integer> temp = list.get(left);
        list.set(left, list.get(right));
        list.set(right, temp);
    }
    private void shuffle(List<Map.Entry<Integer, Integer>> list) {
        final Random random = new Random();
        for(int ind = 1; ind < list.size(); ind++) {
            final int r = random.nextInt(ind + 1);
            swap(a, ind, r);
        }
    }