answer2.cpp

#include <iostream>
#include <string>
#include <iostream>
#include <algorithm>
#include <math.h> 
#include <limits.h>
#include <vector>
#include <unordered_map>
using namespace std;

class Cache {
private:
    struct Node{
        int weight;
        int last_access_time;
        int key;
        int value;
        double score;
        Node(int key, int value, int weight): key(key), value(value), weight(weight){
            last_access_time = 0;
            score = 0;
        };
        void updateScore(){
            // Tip: I modify the calculation of score as below:
            // old: score = weight / ln(current_time - last_access_time)
            // new: score = weight / - (ln(last_access_time)) =>
            // Because I must ensure the new value score that always larger than others for weight/-100.
            // weight / - (ln(last_access_time)) < weight/-100
            // According to the score formula, the order of all score are equal the origin formula
            if(last_access_time == 0){
                score = weight/-100;
            }else{
                score = weight/-(log(last_access_time));
            }
        }
    };
    unordered_map<int, Node*> map;
    int capacity_;

    /**
    * Set a Node to Cache 
    * Tip: the score of new node must larger than others in cache.
    * Time complexity: O(1)
    * 
    * @param key .
    * @param value .
    * @param weight .
    */
    void set(int key, int value, int weight){
        Node* node = map[key];
        node->value = value;
        node->weight = weight;
        node->updateScore();
    };
    /**
    * Insert a new Node to Cache 
    * Tip: the score of new node must larger than others in cache.
    * Time complexity: O(1)
    * 
    * @param key .
    * @param value .
    * @param weight .
    */
    void insert(int key,int value, int weight){
        Node* node = new Node(key,value, weight);
        node->updateScore();
        map[key] = node;
    };
    /**
    * Remove the node of least scroe from Cache 
    * When cache size larger than capacity.
    * Time complexity: O(capacity)
    */
    void removeLeastScoreNode(){
        if(map.size() <= capacity_) return;

        int target;
        double min = INT_MAX;
        for (auto& it: map){
            Node* node = it.second;
            int key = it.first;
            if(node->score <= min){
                min = node->score;
                target = key;
            }
        }
        map.erase(target);
    }
public:
    Cache(int capacity) {
        capacity_ = capacity; 
    }
    
    /**
    * Get a value by key from Cache 
    * Time complexity: O(1)
    * 
    * @param key .
    */
    int get(int key) {
        if(!map.count(key)) return -1;

        Node* node = map[key];
        node->last_access_time = std::time(0);
        node->updateScore();
        return node->value;
    }
    
    /**
    * Put a key and value to Cache
    * Time complexity: O(capacity)
    * 
    * @param key .
    * @param value .
    * @param weight .
    */
    void put(int key, int value, int weight) {
        if(map.count(key)){
            set(key, value, weight);
        }else{
            insert(key, value, weight);
            removeLeastScoreNode();
        }
    }
};

int main()
{
    Cache* cache = new Cache(2); 
    cache->put(1,1, 1);
    cache->get(1);
    cache->put(2,2, 1);
    cache->get(2);
    cache->put(3,3, 1);
    cache->get(1); // return -1;
    cache->get(3); // return 3;
}