13 months ago

Anand Kumar • 10

Mumbai

#include <bits/stdc++.h>

using namespace std;

class LRUCache {
public:
    class node {
    public: 
        int key;
        string value;
        node * prev;
        node * next;
          
        node(int _key, string _value) {
            key = _key;
            value = _value;
        }
    };
      
    node* head = new node(-1,"-1");
    node* tail = new node(-1,"-1");
    int cap;
    map<int, node *> m;
      
    LRUCache(int capacity) {
        cap = capacity;
        head->next = tail;
        tail->prev = head;
    }
      
    void addnode(node * temp) {
        node * dummy = head->next;
        head->next = temp;
        temp->prev = head;
        temp->next = dummy;
        dummy->prev = temp;
    }
      
    void deletenode(node * temp) {
        node * delnext = temp->next;
        node * delprev = temp->prev;
        delnext->prev = delprev;
        delprev->next = delnext;
    }
      
    string get(int key) {
        if (m.find(key) != m.end()) {
            node * res =  m[key];
            m.erase(key);
            string ans = res->value;
            deletenode(res);
            addnode(res);
            m[key] = head->next;
           
            return ans;
        }
        return "-1";
    }
      
    void set(int key, string value) {
        if (m.find(key) != m.end()) {
            node * exist = m[key];
            m.erase(key);
            deletenode(exist);
        }
          
        if (m.size() == cap) {
            m.erase(tail->prev->key);
            deletenode(tail->prev);
        }
        addnode(new node(key, value));
        m[key] = head->next;
    }
};

bool code(vector<string> res, int mid, int k) {
    LRUCache* cache = new LRUCache(mid);
    int count = 0;
    int c = 0;
    int n = res.size();
    map<string,int> m;
    for(int t = 0; t < n; t++) {
        if(m.find(res[t]) == m.end()) {
            c++;
            m[res[t]] = c;
            cache->set(c, res[t]);
        } else {
            if(cache->get(m[res[t]]) == "-1") {
                cache->set(m[res[t]], res[t]);
            } else {
                count++;
            }
        }
    }
    return count >= k;
}

int solve(vector<string> res, int k) {
    int s = 1;
    int n = res.size();
    int e = n;
    while(s <= e) {
        int mid = s + (e - s) / 2;
        if(code(res, mid, k)) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return (s == n + 1) ? -1 : s;
}

7 months ago

unicornme707 • 20

Mumbai

LRU for each cache size to check ? 

T.C. : - O(N* cache_size)

13 months ago

Anand Kumar • 10

Mumbai

#include <bits/stdc++.h>

using namespace std;

class LRUCache {
public:
    class node {
    public: 
        int key;
        string value;
        node * prev;
        node * next;
          
        node(int _key, string _value) {
            key = _key;
            value = _value;
        }
    };
      
    node* head = new node(-1,"-1");
    node* tail = new node(-1,"-1");
    int cap;
    map<int, node *> m;
      
    LRUCache(int capacity) {
        cap = capacity;
        head->next = tail;
        tail->prev = head;
    }
      
    void addnode(node * temp) {
        node * dummy = head->next;
        head->next = temp;
        temp->prev = head;
        temp->next = dummy;
        dummy->prev = temp;
    }
      
    void deletenode(node * temp) {
        node * delnext = temp->next;
        node * delprev = temp->prev;
        delnext->prev = delprev;
        delprev->next = delnext;
    }
      
    string get(int key) {
        if (m.find(key) != m.end()) {
            node * res =  m[key];
            m.erase(key);
            string ans = res->value;
            deletenode(res);
            addnode(res);
            m[key] = head->next;
           
            return ans;
        }
        return "-1";
    }
      
    void set(int key, string value) {
        if (m.find(key) != m.end()) {
            node * exist = m[key];
            m.erase(key);
            deletenode(exist);
        }
          
        if (m.size() == cap) {
            m.erase(tail->prev->key);
            deletenode(tail->prev);
        }
        addnode(new node(key, value));
        m[key] = head->next;
    }
};

bool code(vector<string> res, int mid, int k) {
    LRUCache* cache = new LRUCache(mid);
    int count = 0;
    int c = 0;
    int n = res.size();
    map<string,int> m;
    for(int t = 0; t < n; t++) {
        if(m.find(res[t]) == m.end()) {
            c++;
            m[res[t]] = c;
            cache->set(c, res[t]);
        } else {
            if(cache->get(m[res[t]]) == "-1") {
                cache->set(m[res[t]], res[t]);
            } else {
                count++;
            }
        }
    }
    return count >= k;
}

int solve(vector<string> res, int k) {
    int s = 1;
    int n = res.size();
    int e = n;
    while(s <= e) {
        int mid = s + (e - s) / 2;
        if(code(res, mid, k)) {
            e = mid - 1;
        } else {
            s = mid + 1;
        }
    }
    return (s == n + 1) ? -1 : s;
}