fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5.     int key, value, freq, time;
  6.     Node(int k, int v, int f, int t): key(k), value(v), freq(f), time(t) {}
  7. };
  8.  
  9. vector<int> implementLFU(int cacheSize, vector<string> queries) {
  10.     vector<int> result;
  11.     if (cacheSize == 0) return result;
  12.  
  13.     unordered_map<int, Node*> cache; 
  14.     int time = 0; 
  15.  
  16.     for (auto &q : queries) {
  17.         stringstream ss(q);
  18.         string type;
  19.         ss >> type;
  20.  
  21.         if (type == "PUT") {
  22.             int key, value;
  23.             ss >> key >> value;
  24.             time++;
  25.  
  26.             if (cache.find(key) != cache.end()) {
  27.                 cache[key]->value = value;
  28.                 cache[key]->freq++;
  29.                 cache[key]->time = time;
  30.             } else {
  31.                 if ((int)cache.size() >= cacheSize) {
  32.                     int minFreq = INT_MAX, oldestTime = INT_MAX, evictKey = -1;
  33.                     for (auto &p : cache) {
  34.                         Node* node = p.second;
  35.                         if (node->freq < minFreq || 
  36.                            (node->freq == minFreq && node->time < oldestTime)) {
  37.                             minFreq = node->freq;
  38.                             oldestTime = node->time;
  39.                             evictKey = node->key;
  40.                         }
  41.                     }
  42.                     delete cache[evictKey];
  43.                     cache.erase(evictKey);
  44.                 }
  45.                 cache[key] = new Node(key, value, 1, time);
  46.             }
  47.         } 
  48.         else if (type == "GET") {
  49.             int key;
  50.             ss >> key;
  51.             time++;
  52.             if (cache.find(key) != cache.end()) {
  53.                 cache[key]->freq++;
  54.                 cache[key]->time = time;
  55.                 result.push_back(cache[key]->value);
  56.             } else {
  57.                 result.push_back(-1);
  58.             }
  59.         }
  60.     }
  61.     return result;
  62. }
  63.  
  64. int main() {
  65.     int cacheSize, q;
  66.     cin >> cacheSize >> q;
  67.     cin.ignore();
  68.  
  69.     vector<string> queries(q);
  70.     for (int i = 0; i < q; i++) {
  71.         getline(cin, queries[i]);
  72.     }
  73.  
  74.     vector<int> ans = implementLFU(cacheSize, queries);
  75.     for (int x : ans) cout << x << endl;
  76.     return 0;
  77. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
5
PUT 1 1
PUT 2 2
GET 1
PUT 3 3
GET 2
stdout
copy 
1
-1
https://ideone.com/Xsr8dH
language:
C++14 (gcc 8.3)
created:
16 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!