friend recommend

function get_friends(A) 能得到A的所有朋友,求get_friends_of_friends(A)

口头跑程序,run了好多个case,一开始我把所有和A有关系的“朋友”都找出来了,后来面试官提示只要找A的朋友的朋友(2层)并且找到的不能含A的朋友。就是一个图的搜索,并记录图的深度degree......

//return friends of friends that are not this person's friends

//Friend Recommendation:bucket sort,O(m) time,O(n) space,m is num of person's friends' friends,n is num of valid friends
public class Solution {
    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;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int friend : person.friends) {
            for (int recommend : friend.friends) {
               int id = recommend.id;
               if (person.friends.contains(id) || id == person.id) {
                   continue;//if person already has this friend,or this is person himself/herself,continue
               }
               if (!map.containsKey(id)) {
                   map.put(id, 0);
               }
               map.put(id, map.get(id) + 1);
           }
        }
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            buckets.add(new ArrayList<Integer>());//we use frequency as index, so <= length
        }
        for (int key : map.keySet()) {//unlike heap solution, we only need keySet() here
            buckets.get(map.get(key)).add(key);//get the id(key), add the id to its frequency bucket
        }
        for (int i = buckets.size() - 1; i >= 0; i--) {
            for (int j = 0; j < buckets.get(i).size(); j++) {//start adding the vals at the last bucket's last index
                res.add(buckets.get(i).get(j));
                if (res.size() == k) {
                    return res;//this two loops are O(k) time, when res has k nums, return it
                }
            }
        }
        return res;
    }
}

//Friend Recommendation: Quick Select, average O(m + n) time, O(1) space, worst case O(m + n^2) time
//m is num of person's friends' friends,n is num of valid friends
public class Solution {
    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;
        }
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int friend : person.friends) {
            for (int recommend : friend.friends) {
               int id = recommend.id;
               if (person.friends.contains(id) || id == person.id) {
                   continue;//if person already has this friend,or this is person himself/herself,continue
               }
               if (!map.containsKey(id)) {
                   map.put(id, 0);
               }
               map.put(id, map.get(id) + 1);
           }
        }
        
        ArrayList<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        int left = 0;
        int right = list.size() - 1;
        int index = -1;
        while (true) {
            int pos = partition(list, left, right);
            if (pos + 1 == k) {
                index = pos;
                break;
            } else if (pos + 1 > k) {
                right = pos - 1;
            } else {
                left = pos + 1;
            }
        }
        if (index == -1) {
            return res;
        }
        for (int i = 0; i <= index; i++) {
            int id = list.get(i).getKey();
            res.add(id);
        }
        return res;
    }
    
    private int partition(ArrayList<Map.Entry<Integer, Integer>> list, int left, int right) {
        Random rand = new Random();
        int index = rand.nextInt(right - left + 1) + left;//remember to add + left !!!
        Map.Entry<Integer, Integer> pivot = list.get(index);
        int pVal = pivot.getValue();
        swap(list, left, index);//index, not pivot !!
        int l = left + 1;
        int r = right;
        while (l <= r) {
            int lVal = list.get(l).getValue();
            int rVal = list.get(r).getValue();
            if (lVal < pVal && rVal > pVal) {
                swap(list, l, r);
            }
            if (lVal >= pVal) {
                l++;
            }
            if (rVal <= pVal) {
                r--;
            }
        }
        swap(list, left, r);
        return r;
    }
    
    private void swap(ArrayList<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);
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 9,959评论 0 23
  • 昨晚做了个梦,梦到你们了...很开心,醒来之后却很心酸,终究只是个梦,我也希望自己能被你说服...
    尘言呓语阅读 59评论 0 0
  • 我一直等到那些狗再也看不见了,才离开了秋芽子的坟,回到家中,胡乱吃了点东西,倒头就睡,这一天对我来说,不论是从身体...
    喵丿大王阅读 370评论 0 0
  • 突然想起来昨晚躺在床上脑海里一闪而过的问题。林徽因一生受尽三个男人专宠。胡兰成一生狐妖般爱尽各种女人。那这两个“祸...
    红豆红豆锁阅读 403评论 0 0