ออกแบบ Leaderboard ใน C++

เราต้องออกแบบคลาส Leaderboard ที่มีฟังก์ชัน 3 อย่าง:

• addScore(playerId, score) - อัปเดตคะแนนผู้เล่น เพิ่มคะแนน ถ้ายังไม่มีผู้เล่นให้เพิ่มเข้าไป
• top(K) - คืนผลรวมคะแนนของผู้เล่นอันดับ 1 ถึง K
• reset(playerId) - รีเซ็ตคะแนนผู้เล่นเป็น 0 (รับประกันว่าผู้เล่นมีอยู่แล้ว)

เริ่มต้น Leaderboard ว่างเปล่า

ขั้นตอนการแก้ปัญหา (Priority Queue + Hash Map)

• ใช้ Priority Queue (max-heap) เก็บคู่ (score, playerId)
• ใช้ Hash Map m เก็บคะแนนปัจจุบันของแต่ละผู้เล่น
• addScore: อัปเดต m[playerId] ใส่คู่ใหม่เข้า PQ
• top(K): ดึงจาก PQ จนได้ K ผู้เล่นที่คะแนนตรงกับ m (ล้างข้อมูลเก่า) รวมคะแนน แล้วใส่กลับเข้า PQ
• reset: กำหนด m[playerId] = 0

ตัวอย่างโค้ด (C++)

#include <bits/stdc++.h> 
using namespace std; 

class Leaderboard {
public:
    priority_queue< pair <int,int> > pq;
    map < int, int > m;
    Leaderboard() {
        m.clear();
        while(!pq.empty()) pq.pop();
    }
    void addScore(int playerId, int score) {
        if(m.find(playerId) != m.end()) {
            m[playerId] += score;
        } else {
            m[playerId] = score;
        }
        pq.push({m[playerId], playerId});
    }
    int top(int k) {
        vector < pair <int,int> > temp;
        int sum = 0;
        while(k) {
            pair <int, int> curr = pq.top();
            pq.pop();
            if(m[curr.second] == curr.first) {
                k--;
                sum += curr.first;
                temp.push_back(curr);
            }
        }
        for(int i = 0; i < temp.size(); i++) pq.push(temp[i]);
        return sum;
    }
    void reset(int playerId) {
        m[playerId] = 0;
    }
};

int main() {
    Leaderboard ob;
    ob.addScore(1,73);
    ob.addScore(2,56);
    ob.addScore(3,39);
    ob.addScore(4,51);
    ob.addScore(5,4);
    cout << ob.top(1) << endl;
    ob.reset(1);
    ob.reset(2);
    ob.addScore(2,51);
    cout << ob.top(3) << endl;
}

อินพุต

Initialize leader board then use the functions to see different results. See the main() function

เอาต์พุต

73 102