提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

设计推特（思维游戏01）

2023-03-07 09:05:58 时间

接口要求

  • void postTweet(int userId, int tweetId) 根据给定的 tweetId 和 userId 创建一条新推文。每次调用此函数都会使用一个不同的 tweetId 。
  • List<Integer> getNewsFeed(int userId) 检索当前用户新闻推送中最近 10 条推文的 ID 。新闻推送中的每一项都必须是由用户关注的人或者是用户自己发布的推文。推文必须 按照时间顺序由最近到最远排序 。
  • void follow(int followerId, int followeeId) ID 为 followerId 的用户开始关注 ID 为 followeeId 的用户。
  • void unfollow(int followerId, int followeeId) ID 为 followerId 的用户不再关注 ID 为 followeeId 的用户。

数据结构设计

用户系统

用户之间存在 关注、被关注、互相关注三种关系，逻辑上形成网状结构，可以使用关系型数据库保存，可以快速检索用户之间的关系。但本系统没有查询一度、二度、N度关系的需求，可以简化为k:v存储，k为用户ID，v为关注列表，关注列表需要去重，考虑set结构。

用户数量少考虑关系矩阵

推文系统

推文

  • 推文由几部分组成，信息、时间戳、发推人组成。
  • 直观上推文在逻辑上是属于用户的，用户对自己的推文有增删改查的需求，查询都是需要返回一段连续时间范围内的推文，有删除的需求，有不等宽更新的需求，假如不用DB应该是一个list基础的数据结构比较合适。当然实际业务场景一定是会用到数据库的。
  • 查询也有另外两个特殊的要求：1、需要能看到自己和被关注者的推文 2、按时间戳顺序返回推文，且限定10条。

查询（方案一）拉取合并

  • 如果以用户角度保存推文，每个用户有一个时间排序链表，则选择推文链表并按时间顺序返回10条，直观上是一个K排序链表合并的问题。
  • 主动查询+合并会带来大量查询、计算，但实时性会好一些，类似于惰性拉取，需要时在计算，所以该方案需要深入优化查询（DB层）和合并算法（K路归并按业务场景优化）。

查询（方案二）拉取遍历

  • 如果所有推文形成一个链表，可以从头遍历链表按关注关系选择推文即可，这种方法也属于惰性拉取，但预期的关注关系应该是稀疏的，这种拉去效率会很低，带来大量miss查询，只适合纯内存解题场景（比如文末code）

查询（方案三）推送

  • 相对于惰性拉取，可以在每个用户发布推特后，主动把推文发送到被关注者，这样在用户读取推文时，无需检索关注者，只需读出收到的最新10条即可。
  • 优点是读取时省去了K路归并、省去了检索关注者推文的动作，读取复杂度大大降低。
  • 缺点是发布推文时需要广播到所有被关注者，时效性差；大量冗余数据发布、保存（用户不登录但是也需要广播）；如果有热点用户（大量关注者）频繁发布推文，很容易造成热点问题。

简化实现

struct Tweet 
{
    int uid;
    int tid;
    struct Tweet *next;
};

typedef struct 
{
    int user[512][512];
    struct Tweet *tweet;
} Twitter;

Twitter* twitterCreate()
{
    Twitter *tw = (Twitter*)malloc(sizeof(Twitter));
    tw->tweet = (struct Tweet*)malloc(sizeof(struct Tweet));
    tw->tweet->next = NULL;
    memset(tw->user, 0, 512 * 512 * sizeof(int));
    return tw;
}

void twitterPostTweet(Twitter* obj, int uid, int tid)
{
    struct Tweet *tweet = malloc(sizeof(struct Tweet));
    tweet->uid  = uid;
    tweet->tid = tid;
    tweet->next = obj->tweet->next;
    obj->tweet->next = tweet;
}

int* twitterGetNewsFeed(Twitter* obj, int uid, int* retSize)
{
    int i = 0;
    int *result = malloc(10 * sizeof(int));

    struct Tweet *tweet = obj->tweet->next;
    while (tweet && i < 10) 
    {
        if (tweet->uid == uid || obj->user[uid][tweet->uid] == 1) 
        {
            result[i++] = tweet->tid;
        }
        tweet = tweet->next;
    }

    *retSize = i;
    return result;
}

void twitterFollow(Twitter* obj, int followerId, int followeeId)
{
    obj->user[followerId][followeeId] = 1;
}

void twitterUnfollow(Twitter* obj, int followerId, int followeeId)
{
    obj->user[followerId][followeeId] = 0;
}

void twitterFree(Twitter* obj)
{
    if (obj && obj->tweet) {
        free(obj->tweet);
    }
    free(obj);
}

相关文章