当前位置: 面试刷题>> 推荐朋友 (经典算法题500道)


题目描述

在社交网络中,我们有一个用户系统,每个用户都有一个唯一的ID,并且用户可以互相关注形成关注关系。现在,我们想要实现一个功能,即给定一个用户ID,推荐给他/她一些可能感兴趣的新朋友。推荐规则基于该用户的已关注好友的共同关注者(即二度好友),但排除掉该用户已经关注的人。

输入

  • 用户ID(表示当前用户)
  • 用户关注关系表(假设为二维数组或类似结构,包含关注者和被关注者的ID对)

输出

  • 一个列表,包含推荐给当前用户的新朋友ID(即共同关注者中未被当前用户关注的用户)

示例

假设用户关注关系表如下([关注者ID, 被关注者ID]):

[[1, 2], [1, 3], [2, 3], [3, 4], [4, 5], [5, 2]]
  • 用户1关注了用户2和用户3。
  • 用户2关注了用户3。
  • 用户3关注了用户4。
  • 用户4关注了用户5。
  • 用户5关注了用户2(这是一个双向关注示例,但不影响推荐逻辑)。

若给定用户ID为1,我们需要找出用户1的未关注但与其有共同关注者的用户。

输出

  • 对于用户1,推荐的新用户为:[4, 5](因为用户4和用户5都是用户1的已关注好友(用户2和用户3)的共同关注者,但用户1尚未关注他们)。

PHP代码示例

<?php

function recommendFriends($userId, $followRelations) {
    $followedByMe = []; // 存储用户已关注的人
    $friendsOfFriends = []; // 存储二度好友(共同关注者)

    // 遍历关注关系表,找出用户已关注的人
    foreach ($followRelations as $relation) {
        if ($relation[0] == $userId) {
            $followedByMe[] = $relation[1];
        }
    }

    // 遍历关注关系表,找出二度好友
    foreach ($followedByMe as $friend) {
        foreach ($followRelations as $relation) {
            if ($relation[0] == $friend && !in_array($relation[1], $followedByMe) && !in_array($relation[1], $friendsOfFriends)) {
                $friendsOfFriends[] = $relation[1];
            }
        }
    }

    return $friendsOfFriends;
}

// 示例
$userId = 1;
$followRelations = [[1, 2], [1, 3], [2, 3], [3, 4], [4, 5], [5, 2]];
$result = recommendFriends($userId, $followRelations);
print_r($result); // 输出:[4, 5]

?>

Python代码示例

def recommend_friends(user_id, follow_relations):
    followed_by_me = set()  # 存储用户已关注的人
    friends_of_friends = set()  # 存储二度好友(共同关注者)

    # 找出用户已关注的人
    for relation in follow_relations:
        if relation[0] == user_id:
            followed_by_me.add(relation[1])

    # 找出二度好友
    for friend in followed_by_me:
        for relation in follow_relations:
            if relation[0] == friend and relation[1] not in followed_by_me:
                friends_of_friends.add(relation[1])

    return list(friends_of_friends)

# 示例
user_id = 1
follow_relations = [[1, 2], [1, 3], [2, 3], [3, 4], [4, 5], [5, 2]]
result = recommend_friends(user_id, follow_relations)
print(result)  # 输出:[4, 5]

JavaScript代码示例

function recommendFriends(userId, followRelations) {
    const followedByMe = new Set(); // 存储用户已关注的人
    const friendsOfFriends = new Set(); // 存储二度好友(共同关注者)

    // 找出用户已关注的人
    for (const [follower, followee] of followRelations) {
        if (follower === userId) {
            followedByMe.add(followee);
        }
    }

    // 找出二度好友
    for (const friend of followedByMe) {
        for (const [f, fee] of followRelations) {
            if (f === friend && !followedByMe.has(fee)) {
                friendsOfFriends.add(fee);
            }
        }
    }

    return [...friendsOfFriends];
}

// 示例
const userId = 1;
const followRelations = [[1, 2], [1, 3], [2, 3], [3, 4], [4, 5], [5, 2]];
const result = recommendFriends(userId, followRelations);
console.log(result); // 输出:[4, 5]

码小课:在码小课网站中,你可以找到更多关于算法和数据结构、网络编程、Web开发等相关内容的分享,帮助你提升编程技能,解决实际问题。

推荐面试题