LRU Cache Leetcode Həlli

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Amazon alma Atlassian Bloomberg ByteDance Capital One Cisco Citadel Citrix Birlik DocuSign Dropbox eBay Expedia Facebook GoDaddy Goldman Sachs google Ağır Infosys Intel Intuit JPMorgan LinkedIn MakeMyTrip microsoft Morgan Stanley Nutanix Nvidia Kahin Palantir Texnologiyaları PayPal ROBLOX Salesforce XidmətNow Snapchat Boşalmaq Sprinklr kvadrat Tesla Twilio Twitch cuqquldamaq Über VMware Yahoo Yandex Zenefits Zillow
Layihə HashMap Bağlı siyahı Mağaza Sumoloji tiktok Walmart Qlobal texnologiyaBaxılıb 45

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

The LRU Cache LeetCode Həlli - “LRU Cache” sizdən aşağıdakı məlumat strukturunu tərtib etməyi xahiş edir Ən az istifadə olunan (LRU) önbellek

Aşağıdakı funksiyaları olan LRUCache sinfini tətbiq etməliyik:

  • LRUCache(int tutumu): LRU keşini müsbət ölçü ilə işə salır tutum.
  • int get(int açarı): Əgər açar varsa, dəyərini qaytarın, əks halda -1 qaytarın.
  • void put(int açarı, int dəyəri): açar varsa, onun dəyərini yeniləyin, əks halda açar-dəyər cütünü keş yaddaşa daxil edin. Keşin ölçüsü keşin tutumundan artıqdırsa, ən az istifadə olunan açarı çıxarın.

Misal:

LRU Cache Leetcode HəlliPin

Input:  ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
        [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation:

  • LRUCache lRUCache = yeni LRUCache(2);
  • lRUCache.put(1,1); [keş {1=1} ]
  • lRUCache.put(2,2); [keş {1=1,2=2} ]
  • lRUCache.get(1); [1-i qaytarın]
  • lRUCache.put(3,3); [LRU açarı 2 idi, açar 2-ni çıxarın, keş {1=1,3=3} ]
  • lRUCache.get(2); [qayıt -1 ]
  • lRUCache.put(4,4); [LRU açarı 1 idi, açar 1-ni çıxarın, keş {4=4,3=3} ]
  • lRUCache.get(1); [qayıt -1 ]
  • lRUCache.get(3); [3-i qaytarın]
  • lRUCache.get(4); [4-i qaytarın]

Yanaşma

Idea:

  1. Bu problemi həll etmək üçün əsas fikir istifadə etməkdir Hashmap və bir ikiqat əlaqəli siyahı.
  2. İkiqat əlaqəli siyahı və ikiqat əlaqəli siyahıda mövcud olan node ünvanı üçün açarın xəritəsini saxlayan bir heşməp saxlayın.
  3. Konstruktor çağırıldıqda, keşin cari ölçüsünü sıfır olaraq işə salın və yaradın dummy node ikiqat əlaqəli siyahıdan. Həmçinin, hashtable-in girişlərini təmizləyin.
  4. updateCache() funksiyası ikiqat əlaqəli siyahıda müəyyən bir açar artıq varsa, keşi yeniləmək və həmçinin ikiqat əlaqəli siyahını yeniləmək üçün istifadə olunur.
  5. -1 nə vaxt geri dönəcəyik almaq () funksiya çağırılır və açar keşdə yoxdur, əks halda dəyəri qaytarın və keşi yeniləyin.
  6. Zaman qoy() metodu çağırılır və açar artıq keşdə mövcuddur, açar-dəyər cütlüyünü yeniləyin, həmçinin keşi yeniləyin və ikiqat əlaqəli siyahını dəyişdirin.
  7. Zaman qoy() metodu çağırılır və açar ön yaddaşda yoxdur, biz yeni qovşaq yaradacağıq və qovşağı ikiqat əlaqəli siyahıya daxil edəcəyik və həmçinin açar qovşağının ünvanını hash-a daxil edəcəyik. Həmçinin, əgər önbelleğin ölçüsü maksimum tutumunu üstələyir, biz ən az istifadə olunan açar dəyərini keşdən silməliyik. Bu, əlaqəli siyahının köməyi ilə səmərəli şəkildə edilə bilər.

Kodu

LRU Cache Leetcode C++ Həlli:

class LRUCache {
public:
    struct Node{
        Node* prev;
        Node* next;
        int data,key;
        
        Node(int key,int data){
            this->key = key;
            this->data = data;
            prev = next = nullptr;
        }
    };
    Node *dummy,*curr;
    unordered_map<int,Node*> hash;
    int max_size,curr_size;
    
    void updateCache(int key){
        if(hash[key]==curr){
            return;
        }  
        Node *node1 = hash[key]->prev,*node2 = hash[key]->next;
        node1->next = node2;
        node2->prev = node1;
        curr->next = hash[key];
        hash[key]->prev = curr;
        hash[key]->next = nullptr;
        curr = curr->next;
    }
    LRUCache(int capacity) {
        curr_size = 0;
        max_size = capacity;   
        dummy = new Node(-1,-1);
        curr = dummy;
        hash.clear();
    }
    int get(int key) {
        if(!hash.count(key)){
            return -1;
        }
        updateCache(key);
        return hash[key]->data;
    }
    void put(int key, int data) {
        if(hash.count(key)){
            hash[key]->data = data;
            updateCache(key);
        }
        else{
            if(curr_size==max_size){
                hash.erase(dummy->next->key);           
                Node *node1 = dummy,*node2 = dummy->next->next;
                node1->next = node2;
                if(node2!=nullptr){
                    node2->prev = node1;
                }
                else{
                    curr = node1;
                }
                curr_size--;
            }
            Node* newNode = new Node(key,data);
            curr->next = newNode;
            newNode->prev = curr;
            curr = curr->next;
            hash[key] = newNode;
            curr_size++;
        }
    }
};

LRU Cache Leetcode Java Həlli:

import java.util.Hashtable;
public class LRUCache {
class DLinkedNode {
  int key;
  int value;
  DLinkedNode pre;
  DLinkedNode post;
}
private void addNode(DLinkedNode node) {   
  node.pre = head;
  node.post = head.post;
  head.post.pre = node;
  head.post = node;
}
private void removeNode(DLinkedNode node){
  DLinkedNode pre = node.pre;
  DLinkedNode post = node.post;
  pre.post = post;
  post.pre = pre;
}
private void moveToHead(DLinkedNode node){
  this.removeNode(node);
  this.addNode(node);
} 
private DLinkedNode popTail(){
  DLinkedNode res = tail.pre;
  this.removeNode(res);
  return res;
}
private Hashtable<Integer, DLinkedNode> 
  cache = new Hashtable<Integer, DLinkedNode>();
private int count;
private int capacity;
private DLinkedNode head, tail;

public LRUCache(int capacity) {
  this.count = 0;
  this.capacity = capacity;
  head = new DLinkedNode();
  head.pre = null;
  tail = new DLinkedNode();
  tail.post = null;
  head.post = tail;
  tail.pre = head;
}
public int get(int key) {
  DLinkedNode node = cache.get(key);
  if(node == null){
    return -1;
  }
  this.moveToHead(node);
  return node.value;
}
public void put(int key, int value) {
  DLinkedNode node = cache.get(key);
  if(node == null){
    DLinkedNode newNode = new DLinkedNode();
    newNode.key = key;
    newNode.value = value;
    this.cache.put(key, newNode);
    this.addNode(newNode);
    ++count;
    if(count > capacity){
      DLinkedNode tail = this.popTail();
      this.cache.remove(tail.key);
      --count;
    }
  }else{
    node.value = value;
    this.moveToHead(node);
  }
}
}

LRU Cache Leetcode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

Yuxarıdakı kodun zaman mürəkkəbliyi O (1) O(1) vaxtda daxil etməyə və silməyə imkan verən səmərəli hash funksiyasından istifadə etsək. Həmçinin, ikiqat əlaqəli siyahıdan qovşaqların əlavə edilməsi və çıxarılması O(1) vaxtını alır.

Kosmik Mürəkkəblik

Yuxarıdakı kodun kosmik mürəkkəbliyi O (N) çünki həşmənin maksimum ölçüsü O(N) ola bilər.

Referans: https://en.wikipedia.org/wiki/Cache_replacement_policies

Crack Sistemi Dizayn Müsahibələri
Translate »