오늘 의 특종 고주파 면접 문제 LRU

스스로 를 아 는가?https://zhuanlan.zhihu.com/p/34133067
제목.
당신 이 파악 한 데이터 구 조 를 활용 하여 LRU (최근 최소 사용) 캐 시 체 제 를 설계 하고 실현 합 니 다.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.
데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.
진급:
당신 은 O (1) 시간 복잡 도 내 에 이 두 가지 조작 을 완성 할 수 있 습 니까?

LRUCache cache = new LRUCache( 2 /*      */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       //     1
cache.put(3, 3);    //          2   
cache.get(2);       //    -1 (   )
cache.put(4, 4);    //          1   
cache.get(1);       //    -1 (   )
cache.get(3);       //     3
cache.get(4);       //     4

해제
이 문 제 는 오늘 톱기사, 빠 른 손 또는 실리콘밸리 회사 에서 흔히 볼 수 있 는 것 으로 코드 를 많이 쓰 고 난이도 도 hard 급 이다.
가장 중요 한 것 은 LRU 라 는 전략 을 어떻게 실현 하 느 냐 하 는 것 이다. 하나의 링크 로 최근 에 사용 한 것 을 링크 의 맨 앞 에 두 는 것 을 쉽게 생각 할 수 있다.예 를 들 어 get 요 소 는 사 용 된 것 과 같 습 니 다. 이 럴 때 는 맨 앞 에 놓 고 값 을 되 돌려 야 합 니 다. set 와 같 습 니 다.그러면 어떻게 체인 시계의 중간 요 소 를 체인 시계의 시작 부분 에 빠르게 놓 습 니까?자 연 스 럽 게 우 리 는 양 끝 링크 가 생각 났 다.
HashMap 과 양 방향 링크 를 바탕 으로 LRU 의
전체적인 디자인 방향 은 HashMap 으로 key 를 저장 할 수 있다 는 것 이다. 그러면 save 와 get key 의 시간 은 모두 O (1) 이 고 HashMap 의 Value 는 양 방향 링크 가 실현 하 는 LRU 의 Node 노드 를 가리킨다. 그림 과 같다.
LRU 저장 소 는 양 방향 링크 를 기반 으로 이 루어 졌 으 며 아래 그림 은 그 원 리 를 보 여 준다.그 중에서 헤드 는 양 방향 체인 시계의 머리 를 대표 하고 테 일 은 꼬리 를 대표 한다.먼저 LRU 의 용량 을 미리 설정 하고 저장 이 가득 차 면 O (1) 의 시간 을 통 해 양 방향 링크 의 끝 부분 을 탈락 시 킬 수 있다. 데 이 터 를 새로 추가 하고 방문 할 때마다 O (1) 의 효율 을 통 해 새로운 노드 를 정상 으로 늘 리 거나 이미 존재 하 는 노드 를 팀 으로 이동 시 킬 수 있다.
미리 설 정 된 크기 는 3 이 고 LRU 가 저장 하고 접근 하 는 과정 에서 의 변 화 를 보 여 준다.그림 의 복잡 도 를 간소화 하기 위해 그림 에서 HashMap 부분의 변 화 를 보 여주 지 않 고 위의 그림 LRU 양 방향 링크 의 변 화 를 보 여 주 었 다.이 LRU 캐 시 에 대한 작업 순 서 는 다음 과 같 습 니 다.

save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)

해당 LRU 양 방향 링크 부분 변 화 는 다음 과 같 습 니 다.
핵심 작업 의 절 차 를 정리 하 다.
save (key, value) 는 먼저 HashMap 에서 Key 에 대응 하 는 노드 를 찾 습 니 다. 노드 가 존재 하면 노드 의 값 을 업데이트 하고 이 노드 를 팀 헤드 로 이동 합 니 다.존재 하지 않 으 면 새로운 노드 를 만 들 고 노드 를 팀 머리 에 쑤 셔 넣 으 려 고 합 니 다. LRU 공간 이 부족 하면 tail 을 통 해 팀 의 끝 에 떨 어 진 노드 를 탈락 시 키 고 HashMap 에서 Key 를 제거 합 니 다.
get (key), HashMap 을 통 해 LRU 링크 노드 를 찾 습 니 다. LRU 원리 에 따라 이 노드 는 최신 으로 방 문 했 기 때문에 노드 를 팀 헤드 에 삽입 한 다음 캐 시 값 을 되 돌려 야 합 니 다.

    private static 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 HashMap
            cache = new HashMap();
    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; // cache    
        }

        // cache   ,    
        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 {
            // cache  ,  cache.
            node.value = value;
            this.moveToHead(node);
        }
    }

오늘 의 특종 고주파 면접 문제 LRU

좋은 웹페이지 즐겨찾기