LRU 캐시 Leetcode 솔루션

난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 골드 피처 블룸버그 게시물에서 ByteDance 자본 하나 시스코 시트릭스 응집력 DocuSign의 드롭 박스 이베이 Expedia Facebook 에서 GoDaddy 골드만 삭스 구글 인포시스 인텔 인튜이트 JP 모건 링크드인 MakeMyTrip Microsoft 모건 스탠리 (Morgan Stanley) 뉴타 닉스 엔비디아 신탁 Palantir Technologies 페이팔 Roblox 세일즈 포스 ServiceNow Snapchat 스플 렁크 스프링클러 사각형. 테슬라 Twilio 씰룩 씰룩 움직이다 Twitter 동네 짱 VM웨어 Yahoo Yandex 주차 Zenefits Zillow
디자인 해시맵 연결된 목록 감독자 서모로직 Tik의 톡 월마트 글로벌 테크조회수 44

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

또한 LRU 캐시 LeetCode 솔루션 – "LRU 캐시"는 다음과 같은 데이터 구조를 설계하도록 요청합니다. LRU (최소 최근 사용) 캐시

다음 기능을 가진 LRUCache 클래스를 구현해야 합니다.

  • LRUCache(int capacity): LRU 캐시를 양수 크기로 초기화합니다. 생산 능력.
  • int get(int key): 키 값이 있으면 반환하고 그렇지 않으면 -1을 반환합니다.
  • void put(int key, int value): 키 값이 있으면 업데이트하고, 그렇지 않으면 키-값 쌍을 캐시에 삽입합니다. 캐시 크기가 캐시 용량을 초과하면 가장 최근에 사용한 키를 제거합니다.

예:

LRU 캐시 Leetcode 솔루션

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]

설명 :

  • LRUCache lRUCache = 새로운 LRUCache(2);
  • lRUCache.put(1,1); [캐시는 {1=1}임 ]
  • lRUCache.put(2,2); [캐시는 {1=1,2=2}임 ]
  • lRUCache.get(1); [리턴 1]
  • lRUCache.put(3,3); [LRU 키 2, 키 2 제거, 캐시는 {1=1,3=3} ]
  • lRUCache.get(2); [리턴 -1]
  • lRUCache.put(4,4); [LRU 키 1, 키 1 제거, 캐시는 {4=4,3=3} ]
  • lRUCache.get(1); [리턴 -1]
  • lRUCache.get(3); [리턴 3]
  • lRUCache.get(4); [리턴 4]

접근

아이디어 :

  1. 이 문제를 해결하기 위한 주요 아이디어는 해시 맵 이중 연결 목록.
  2. 이중 연결 목록과 이중 연결 목록에 있는 노드 주소에 대한 키 매핑을 유지하는 해시맵을 유지합니다.
  3. 생성자가 호출되면 캐시의 현재 크기를 XNUMX으로 초기화하고 더미 노드 이중 연결 리스트의 또한 해시 테이블의 항목을 지우십시오.
  4. 업데이트 캐시() 함수는 특정 키가 이미 이중 연결 목록에 있는 경우 캐시를 업데이트하고 이중 연결 목록도 업데이트하는 데 사용됩니다.
  5. 다음과 같은 경우 -1을 반환합니다. 가져 오기() 함수가 호출되고 키가 캐시에 없으면 값을 반환하고 캐시를 업데이트합니다.
  6. 놓다() 메서드가 호출되고 키가 이미 캐시에 있는 경우 키-값 쌍을 업데이트하고 캐시도 업데이트하고 이중 연결 목록을 수정합니다.
  7. 놓다() 메서드가 호출되고 키가 캐시에 없으면 새 노드를 만들고 이중 연결 목록에 노드를 삽입하고 해시에 키-노드 주소도 삽입합니다. 또한 캐시의 크기가 최대 용량을 초과합니다, 캐시에서 가장 최근에 사용한 키 값을 제거해야 합니다. 이것은 연결 목록의 도움으로 효율적으로 수행할 수 있습니다.

암호

LRU 캐시 Leetcode C++ 솔루션:

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 캐시 Leetcode Java 솔루션:

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 캐시 Leetcode 솔루션에 대한 복잡성 분석

시간 복잡성

위 코드의 시간 복잡성은 O (1) O(1) 시간에 삽입 및 삭제를 허용하는 효율적인 해시 함수를 사용하는 경우. 또한 이중 연결 목록에서 노드를 추가하고 제거하는 데 O(1) 시간이 걸립니다.

공간 복잡성

위 코드의 공간 복잡성은 다음과 같습니다. 의 위에) 해시맵의 최대 크기는 O(N)일 수 있기 때문입니다.

참조 : https://en.wikipedia.org/wiki/Cache_replacement_policies

균열 시스템 설계 인터뷰
Translate »