有一个社交网站有2000万用户，用户的某些行为可以获得积分，比如登录+5分、评论+3分。现需设计一种合适的数据结构或算法，实现高效地更改用户积分，查询用户积分排名。

题干

面试回答

version0
用一个map记录用户的积分，即key=user_uuid, value=credit。cpp的map底层是红黑树，本身是有序的，插入、查找、删除的平均/最坏时间复杂度都是 $\log(n)$ 。为了获得用户的排名，我们在创建map时指定按照credit进行排序。

version1
version0显然有问题，虽然复杂度是 $\log(n)$ ，但是在2000万这一量级还是会很慢。面试官提醒了该题的一个特点，也就是积分不会发生突变，而是缓慢变化。于是稍加思考给出下面解答：

使用双向链表，链表节点保存用户信息，如credit、rank、prev和next。
使用一个map记录用户节点在链表中的位置，也即map<string, *UserNode>。

这样，当一个用户的积分发生变化时（积分增加时）：

首先通过用户名在map中获取用户节点cur = userNode。
然后从cur开始遍历，知道new_credit == cur.credit。在遍历过程中，修改被遍历节点的rank（名次都要+1），以及记录被遍历节点数量num，那么该用户的名次会提升num，也就是rank -= num。

面试官询问一会后，又给出几个特点，如积分只会增加、处于同一积分的人数会很多。

积分只会增加，那么把双向链表改为单向链表。
处于同一积分的人数很多，会导致基于链表遍历的复杂度较大。

version2
面试官提醒用credit分段。然后就在version1的基础上天马行空（如对某个credit，保存链表中处于该credit的left和right节点位置，以及该区间数量，方便快速修改），给面试官都说糊涂了，后面让我自己下来理理。

事后复盘

面试版本没让面试官满意，因为在2000万这一数量级可能效率没那么高，主要还是没有利用到该题目中的一些特点。经过面试官的提示以及下来后思考，该题目有如下特点：

积分只增不减。
积分缓慢增加，不会突变。
积分范围不大，同一积分下存在很多用户。

基于上述特点，重新设计如下数据结构及算法。

一个hash表unordered_map<string, int> _user_credits，用于记录用户的积分。
一个hash表unordered_map<int, pair<int, set<string>>> _credit_ranks，记录每个credit等级的排名以及处于该credit的用户集(也可以只记录处于该credit的用户数量，此处使用set记录用户是为了方便扩展其它功能，如获取某个credit下（此时积分都一样）按照先后顺序的排名)。

文末代码提供一个CreditRank的类，主要的方法AddCredit(), GetRank(), GetCredit()。
GetCredit(string user_uuid)
从user_credits中获取当前用户的credit。时间复杂度为 $O(1)$ 。
GetRank(string user_uuid)
获取用户对应的credit，从credit_ranks中获取当前credit的排名并返回。时间复杂度为 $O(1)$ 。
AddCredit(string user_uuid, int delta_credit)
改变某用户积分时，步骤如下：

获取该用户的old_credit，new_credit。更新用户的credit，并将用户从credit_ranks[old_credit].second集合中删除。
更新credit_ranks在区间[old_credit, new_credit)内的排名，均下降一名。
将用户插入到credit_ranks[new_credit].second集合中去。如果credit_ranks[new_credit]本来为空，则需要新建。而该new_credit的排名需要计算，也就是计算[new_credit+1, max_credit]之间的任务。
时间复杂度主要在更新[old_credit, new_credit)，以及credit_ranks[new_credit]不存在时，需要遍历[new_credit+1, max_credit]计算rank。另外，对set的插入和删除是 $\log(n)$ 。

代码实现

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <chrono>
using namespace std;

class CreditRank {
public:
    CreditRank(): _max_credit(0) {
        set<string> users;
        _credit_ranks[0] = make_pair(1, users);
    }
    CreditRank(const CreditRank& other) = delete;

    void AddCredit(string user_uuid, int delta_credit) {
        auto it = _user_credits.find(user_uuid);
        int old_credit = 0, new_credit= 0;
        if (it != _user_credits.end()) {
            old_credit = it->second;
            new_credit = old_credit + delta_credit;
            // erase userId from old_credit rank
            _credit_ranks[old_credit].second.erase(user_uuid);
        } else {
            new_credit = delta_credit;
        }
        _max_credit = max(_max_credit, new_credit);
        if (_credit_ranks[old_credit].second.size() == 0 && old_credit > 0) {
            _credit_ranks.erase(old_credit);
        }
        // update credit of userId
        _user_credits[user_uuid] = new_credit;
        // update rank of a credit which in [old_credit, new_credit)
        //printf("update _credit_ranks between [%d, %d)\n", old_credit, new_credit);
        for (int start_credit = old_credit; start_credit < new_credit; ++start_credit) {
            // 使用的unorder_map，查找复杂度为O(1)
            if (_credit_ranks.find(start_credit) == _credit_ranks.end()) continue;
            int& rank = _credit_ranks[start_credit].first;
            rank += 1;
            //printf("credit=%d from rank=%d to rank=%d\n", start_credit, rank - 1, rank);
        }
        // add userId in new_credit rank
        if (_credit_ranks.find(new_credit) != _credit_ranks.end()) {
            _credit_ranks[new_credit].second.insert(user_uuid);
            return;
        }
        set<string> users = { user_uuid };
        int rank = 1;
        for (int start_credit = new_credit + 1; start_credit <= _max_credit; ++start_credit) {
            if (_credit_ranks.find(start_credit) == _credit_ranks.end()) continue;
            rank += _credit_ranks[start_credit].second.size();        // 比new_credit排名更前的人数
        }
        _credit_ranks[new_credit] = make_pair(rank, users);
    }

    int GetRank(string user_uuid) {
        auto it = _user_credits.find(user_uuid);
        if (it == _user_credits.end()) {
            return -1;
        }
        return _credit_ranks[it->second].first;
    }

    int GetCredit(string user_uuid) {
        auto it = _user_credits.find(user_uuid);
        if (it == _user_credits.end()) {
            return -1;
        }
        return _user_credits[user_uuid];
    }

    void PrintCreditAndRank() {
        auto it = _credit_ranks.begin();
        for (; it != _credit_ranks.end(); ++it) {
            printf("credit=%d, rank=%d: \n", it->first, it->second.first);
            auto& users = it->second.second;
            for (auto& u : users) {
                cout << u << ", ";
            }
            cout << endl;
        }
    }

private:
    unordered_map<string, int> _user_credits;                   // key=userId, value=credit
    unordered_map<int, pair<int, set<string>>> _credit_ranks;   // key=credit, value={rank, set<string>}
    int _max_credit;
};

int main() {
    CreditRank cr;
    struct TestCase {
        string user_id;
        int delta_credit;
        int rank;
    };
    // user1: 3, user2: 2, user3: 4
    vector<TestCase> ts = {
        {"user1", 1, 1},
        {"user2", 1, 1},
        {"user1", 1, 1},
        {"user3", 4, 1},
        {"user1", 1, 2},
        {"user2", 1, 3}
    };
    vector<TestCase> result = {
        {"user1", 3, 2},
        {"user2", 2, 3},
        {"user3", 4, 1}
    };
    // Unit Test
    for (int i = 0; i < ts.size(); ++i) {
        auto& t = ts[i];
        cr.AddCredit(t.user_id, t.delta_credit);
        int rank = cr.GetRank(t.user_id);
        if (rank != t.rank) {
            printf("error#i=%d: %s wrong. expect rank = %d, practical rank = %d\n", i, t.user_id.c_str(), t.rank, rank);
        }
    }
    for (int i = 0; i < result.size(); ++i) {
        auto& t = result[i];
        int rank = cr.GetRank(t.user_id);
        int credit = cr.GetCredit(t.user_id);
        if (rank != t.rank || credit != t.delta_credit) {
            printf("error#i=%d: %s wrong. [expect vs. practical] rank[e=%d,p=%d], credit[e=%d,p=%d]\n",
                i, t.user_id.c_str(), t.rank, rank, t.delta_credit, credit);
        }
    }
    // Performance Test
    auto start = chrono::high_resolution_clock::now();
    // add some other testcase
    int user_num = 2000_000;
    int operation_num = 3;
    for (int i = 0; i < operation_num; ++i) {
        for (int j = 0; j < user_num; ++j) {
            cr.AddCredit("user" + to_string(j), rand() % 10 + 1);
        }
    }
    auto end = chrono::high_resolution_clock::now();
    auto duration = chrono::duration_cast<chrono::seconds>(end - start);
    //cr.PrintCreditAndRank();
    printf("%d user insert %d items spend %llds\n", user_num, user_num * operation_num, duration.count());
    return 0;
}

上面在main中对CreditRank进行了简单的性能测试。社交网站2000万用户，假设每天上线率为10％，也就是每天有200万用户登录。更进一步，假设平均每个用户每天有3个操作会增加积分（大部分用户只会登录，很少评论）。因此，在上面代码中我们设置了用户数量user_num=2000_000，operation_num=3，每个操作的积分在[1, 10]之间。
输出：2000000 user insert 6000000 items spend 97s。仅供参考，测试时各种软件开满了。

面试题 - 设计数据结构高效地获取用户积分排名

题干

面试回答

事后复盘

感谢您的支持，我会继续努力的!