fork download
copy 
  1. /*
  2. QUESTION 2: Minimum LRU Cache Capacity
  3.  
  4. Problem Statement:
  5. You are given a sequence of item requests.
  6.  
  7. A cache follows Least Recently Used replacement:
  8. - If the requested item is already in cache, it is a hit.
  9. - Otherwise, it is a miss.
  10. - If the cache is full, the least recently used item is removed.
  11. - Every accessed item becomes most recently used.
  12.  
  13. Return the smallest cache capacity that produces at least K hits.
  14. If even unlimited cache cannot produce K hits, return -1.
  15.  
  16. Hard Constraints:
  17. 1 <= number of requests <= 100000
  18. 1 <= K <= number of requests
  19.  
  20. Example:
  21. requests = ["x", "y", "x", "z", "y", "x"]
  22. K = 2
  23.  
  24. Expected Output:
  25. 3
  26.  
  27. Explanation:
  28. With cache size 2, only the second "x" becomes a hit.
  29. With cache size 3, both "x" and "y" can stay long enough to become hits.
  30.  
  31. Brute Force:
  32. Try every possible cache size.
  33. For each size, simulate LRU and count hits.
  34.  
  35. Time Complexity:
  36. O(n * unique)
  37.  
  38. Optimized Approach:
  39. For a repeated item, suppose it appeared earlier at index p and appears again at index i.
  40. This request becomes a hit if the cache can store all distinct items from p to i - 1.
  41.  
  42. So every repeated request gives one required cache size.
  43. Collect all required sizes, sort them, and take the K-th smallest one.
  44.  
  45. Use Fenwick Tree to count distinct items in a range.
  46.  
  47. Time Complexity:
  48. O(n log n)
  49.  
  50. Space Complexity:
  51. O(n)
  52. */
  53.  
  54. #include <bits/stdc++.h>
  55. using namespace std;
  56.  
  57. class Solution {
  58. public:
  59.     struct Fenwick {
  60.         int n;
  61.         vector<int> bit;
  62.  
  63.         Fenwick(int n) : n(n), bit(n + 1, 0) {}
  64.  
  65.         void add(int idx, int val) {
  66.             idx++;
  67.             while (idx <= n) {
  68.                 bit[idx] += val;
  69.                 idx += idx & -idx;
  70.             }
  71.         }
  72.  
  73.         int sumPrefix(int idx) {
  74.             idx++;
  75.             int res = 0;
  76.  
  77.             while (idx > 0) {
  78.                 res += bit[idx];
  79.                 idx -= idx & -idx;
  80.             }
  81.  
  82.             return res;
  83.         }
  84.  
  85.         int rangeSum(int l, int r) {
  86.             if (l > r) return 0;
  87.             return sumPrefix(r) - (l ? sumPrefix(l - 1) : 0);
  88.         }
  89.     };
  90.  
  91.     int minimumCacheSize(vector<string>& requests, int k) {
  92.         int n = requests.size();
  93.  
  94.         unordered_map<string, int> lastPos;
  95.         Fenwick fw(n);
  96.  
  97.         vector<int> required;
  98.  
  99.         for (int i = 0; i < n; i++) {
  100.             string item = requests[i];
  101.  
  102.             if (lastPos.count(item)) {
  103.                 int prev = lastPos[item];
  104.  
  105.                 int need = fw.rangeSum(prev, i - 1);
  106.                 required.push_back(need);
  107.  
  108.                 fw.add(prev, -1);
  109.             }
  110.  
  111.             fw.add(i, 1);
  112.             lastPos[item] = i;
  113.         }
  114.  
  115.         if ((int)required.size() < k) return -1;
  116.  
  117.         sort(required.begin(), required.end());
  118.         return required[k - 1];
  119.     }
  120. };
  121.  
  122. int main() {
  123.     Solution sol;
  124.  
  125.     vector<string> requests = {"x", "y", "x", "z", "y", "x"};
  126.     int K = 2;
  127.  
  128.     cout << sol.minimumCacheSize(requests, K) << endl;
  129.  
  130.     return 0;
  131. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3
https://ideone.com/J1EpZt
language:
C++14 (gcc 8.3)
created:
9 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!