LRU Cache Leetcode-løsning

Sværhedsniveau Medium
Ofte stillet ind Adobe Amazon æble Atlassian Bloomberg ByteDance One Capital Cisco Citadel Citrix Samhørighed DocuSign Dropbox eBay Expedia Facebook GoDaddy Goldman Sachs google Her er mulighed for et rigtig godt køb Infosys Intel Intuit JPMorgan LinkedIn MakeMyTrip microsoft Morgan Stanley Nutanix Nvidia Oracle Palantir Technologies PayPal Roblox Salesforce ServiceNow Snapchat splunk Sprinklr Firkant Tesla Twilio Twitch Twitter Uber VMware Yahoo Yandex Zenefits Zillow
Design HashMap Sammenkædet-liste Shopee Sumologisk TikTok Walmart Global teknologiViews 44

Systemdesign interviewspørgsmål kan være så åben, at det er for svært at kende den rigtige måde at forberede sig på. Nu er jeg i stand til at knække designrunderne fra Amazon, Microsoft og Adobe efter køb denne bog. Daglig revision af en design spørgsmål og jeg lover, at du kan knække designrunden.

Problemformulering

LRU Cache LeetCode Solution – "LRU Cache" beder dig designe en datastruktur, der følger Mindst brugt (LRU) cache

Vi skal implementere LRUCache-klassen, der har følgende funktioner:

  • LRUCache(int kapacitet): Initialiserer LRU-cachen med positiv størrelse kapacitet.
  • int get(int nøgle): Returner værdien af ​​nøglen, hvis den findes, ellers returner -1.
  • void put(int-nøgle, int-værdi): opdater nøglens værdi, hvis den findes, ellers indsæt nøgleværdi-parret i cachen. Hvis størrelsen af ​​cachen overstiger cachens kapacitet, skal du fjerne den senest brugte nøgle.

Eksempel:

LRU Cache Leetcode-løsningPin

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]

Forklaring:

  • LRUCache lRUCache = ny LRUCache(2);
  • lRUCache.put(1,1); [cachen er {1=1} ]
  • lRUCache.put(2,2); [cache er {1=1,2=2} ]
  • lRUCache.get(1); [retur 1]
  • lRUCache.put(3,3); [LRU-nøgle var 2, fjern nøgle 2, cache er {1=1,3=3} ]
  • lRUCache.get(2); [retur -1 ]
  • lRUCache.put(4,4); [LRU-nøgle var 1, fjern nøgle 1, cache er {4=4,3=3} ]
  • lRUCache.get(1); [retur -1 ]
  • lRUCache.get(3); [retur 3]
  • lRUCache.get(4); [retur 4]

Tilgang

Ide:

  1. Hovedideen til at løse dette problem er at bruge Hashmap og en dobbeltkædet liste.
  2. Vedligehold en dobbelt-linket liste og en hashmap, der holder en mapping af nøglen til nodens adresse, der er til stede i den dobbelt-linkede liste.
  3. Når konstruktøren kaldes, initialiser den aktuelle størrelse af cachen som nul og opret dummy node af den dobbeltforbundne liste. Ryd også posterne i hashtabellen.
  4. updateCache() funktionen bruges til at opdatere cachen, hvis en bestemt nøgle allerede er til stede i den dobbeltlinkede liste og også opdatere den dobbeltlinkede liste.
  5. Vi vender tilbage -1 når få() funktionen kaldes, og nøglen er ikke til stede i cachen, ellers returner værdien og opdater cachen.
  6. Når sætte() metode kaldes, og nøglen er allerede til stede i cachen, opdater nøgleværdi-parret og opdater også cachen og modificer den dobbeltforbundne liste.
  7. Når sætte() metode kaldes, og nøglen ikke er til stede i cachen, opretter vi en ny node og indsætter noden i den dobbeltforbundne liste og indsætter også nøglenodens adresse i hashen. Også, hvis størrelsen af ​​cachen overstiger sin maksimale kapacitet, skal vi fjerne den mindst nyligt brugte nøgleværdi fra cachen. Dette kan gøres effektivt ved hjælp af linket liste.

Kode

LRU Cache Leetcode C++ Løsning:

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-løsning:

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);
  }
}
}

Kompleksitetsanalyse for LRU Cache Leetcode-løsning

Tidskompleksitet

Tidskompleksiteten af ​​ovenstående kode er O (1) hvis vi bruger en effektiv hash-funktion, der tillader indsættelse og sletning i O(1) tid. Det tager også O(1) tid at tilføje og fjerne noder fra en dobbelt-linket liste.

Rumkompleksitet

Rumkompleksiteten af ​​ovenstående kode er PÅ) da hashkortets maksimale størrelse kan være O(N).

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

Crack System Design Interviews
Translate »