ds-forge — interview trainer

Understand it step by step (한국어로 이해 → 영어로 말하기)

LRU 캐시는 정해진 용량(capacity)만큼만 데이터를 저장하고, 가득 차면 가장 오래 안 쓴 항목을 먼저 버리는 캐시입니다. get(key)과 put(key, value) 두 동작을 평균 O(1)로 지원해야 합니다. 핵심 요구사항은 빠른 조회, 최근 사용 순서 추적, 그리고 용량 초과 시 가장 오래된 항목 제거입니다.

1
먼저 요구사항을 정리합니다. get과 put이 둘 다 O(1)이어야 하고, 어떤 항목이 가장 오래 안 쓰였는지 순서를 알아야 합니다. 그래서 두 가지 자료구조가 필요합니다: 빠른 조회용 해시맵과, 사용 순서용 자료구조입니다.
⚖️ Trade-off: 순서를 배열이나 ArrayList로 추적하면 가운데 항목을 맨 앞으로 옮길 때 O(n)이 걸립니다. O(1)을 맞출 수 없습니다.
✅ Fix: 이중 연결 리스트(doubly linked list)를 씁니다. 노드 참조만 있으면 어디 있든 O(1)에 떼어내고 다시 붙일 수 있습니다.
🔧 도구:composition-over-inheritanceSRP
```
// Requirements:
// - get(key): O(1)
// - put(key, value): O(1)
// - evict least-recently-used when full
// Plan: HashMap (lookup) + Doubly Linked List (recency order)
```
🗣 영어로 말해
“I need O(1) lookup and O(1) reordering, so a hash map plus a doubly linked list.”
checking microphone…
2
이중 연결 리스트의 기본 단위인 Node 클래스를 만듭니다. 각 노드는 key, value, 그리고 앞/뒤 노드를 가리키는 prev, next를 가집니다. key도 저장하는 이유는, 항목을 제거할 때 해시맵에서도 같이 지우려면 그 노드의 key를 알아야 하기 때문입니다.
🔧 도구:SRP
```
private static final class Node {
    int key;
    int value;
    Node prev;
    Node next;
    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
```
🗣 영어로 말해
“Each node stores its key too, so eviction can also remove it from the map.”
checking microphone…
3
캐시 본체 클래스를 만들고 필드를 정합니다: capacity, 해시맵(key -> Node), 그리고 리스트의 양 끝을 가리키는 head와 tail 더미(sentinel) 노드입니다. 더미 노드는 실제 데이터가 아니라 경계 표시용입니다.
⚖️ Trade-off: 더미 노드 없이 진짜 head/tail만 쓰면, 빈 리스트나 한 개짜리 리스트에서 null 체크 분기가 계속 생깁니다.
✅ Fix: head, tail 더미 노드 두 개를 두면 모든 추가/삭제가 항상 '가운데' 연산이 되어 null 분기가 사라집니다.
🔧 도구:composition-over-inheritance
```
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // sentinel: most recent side
private final Node tail = new Node(0, 0); // sentinel: least recent side

public LRUCache(int capacity) {
    this.capacity = capacity;
    head.next = tail;
    tail.prev = head;
}
```
🗣 영어로 말해
“I use dummy head and tail nodes to avoid null checks on every insert and remove.”
checking microphone…
4
리스트 조작을 작은 헬퍼 메서드로 분리합니다: remove(node)는 노드를 리스트에서 떼어내고, addFront(node)는 노드를 head 바로 뒤(가장 최근 위치)에 붙입니다. 이 두 개만 있으면 모든 동작을 조립할 수 있습니다.
🔧 도구:SRPDRY
```
private void remove(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private void addFront(Node node) {
    node.next = head.next;
    node.prev = head;
    head.next.prev = node;
    head.next = node;
}
```
🗣 영어로 말해
“I keep two private helpers, remove and addFront, and build everything from them.”
checking microphone…
5
get(key)를 구현합니다. 키가 없으면 -1을 반환합니다. 있으면 그 노드를 리스트에서 떼어내고 다시 맨 앞에 붙여서 '방금 사용함'으로 표시한 뒤 값을 반환합니다. 이것이 LRU의 핵심 동작입니다.
✅ Fix: remove 후 addFront를 호출해 '최근 사용' 순서를 갱신합니다. 둘 다 O(1)이라 get도 O(1)입니다.
🔧 도구:DRY
```
public int get(int key) {
    Node node = map.get(key);
    if (node == null) return -1;
    remove(node);
    addFront(node); // mark as most recently used
    return node.value;
}
```
🗣 영어로 말해
“On a hit I move the node to the front so it becomes most recently used.”
checking microphone…
6
put(key, value)를 구현합니다. 키가 이미 있으면 값만 갱신하고 맨 앞으로 옮깁니다. 새 키면 노드를 만들어 맨 앞에 넣고 맵에 등록합니다. 그리고 용량을 넘으면 가장 오래된 항목, 즉 tail 바로 앞 노드를 제거합니다.
⚖️ Trade-off: 용량 초과 검사를 put 안에서 직접 할지, 별도 evict() 메서드로 뺄지 고민됩니다.
✅ Fix: evict 로직을 작은 단위로 두면 put이 읽기 쉬워집니다. tail.prev가 가장 오래 안 쓴 노드이므로 그것을 remove하고 맵에서도 지웁니다.
🔧 도구:SRP
```
public void put(int key, int value) {
    Node node = map.get(key);
    if (node != null) {
        node.value = value;
        remove(node);
        addFront(node);
        return;
    }
    if (capacity <= 0) return; // guard: 0-cap cache stores nothing (else we'd remove the head sentinel)
    if (map.size() == capacity) {
        Node lru = tail.prev; // least recently used
        remove(lru);
        map.remove(lru.key);
    }
    Node fresh = new Node(key, value);
    map.put(key, fresh);
    addFront(fresh);
}
```
🗣 영어로 말해
“On put I update or insert at the front, and evict the tail node when full.”
checking microphone…
7
엣지 케이스를 짚습니다: capacity가 0이면 아무것도 저장하면 안 되므로 put 맨 앞에 `if (capacity <= 0) return;` 가드가 꼭 있어야 합니다. 이 가드가 없으면 빈 맵에서 map.size()==capacity(0==0)가 참이 되어 tail.prev(=head 센티넬)를 지우려다 리스트가 깨집니다. 같은 키를 다시 put하면 새로 추가가 아니라 갱신이어야 하고, 이때 맵 크기가 안 늘어나야 합니다.
✅ Fix: put에서 기존 키는 갱신 분기로 빠지므로 size가 늘지 않습니다. capacity<=0은 별도 early-return 가드로 막아야 하고, 가드 없이 evict 로직에 들어가면 센티넬을 제거해 깨집니다.
```
// Edge cases:
// - duplicate key on put -> update value + move front (no size growth)
// - capacity <= 0 -> early-return guard (else evict removes the head sentinel)
// - get on missing key -> returns -1
```
🗣 영어로 말해
“Duplicate puts update in place, and a missing get returns minus one.”
checking microphone…
8
마지막으로 확장/스레드 안전성을 언급합니다. 멀티스레드 환경이면 get/put을 synchronized로 감싸거나 외부 락을 쓸 수 있고, 만료시간(TTL)이나 다른 제거 정책(LFU)으로 확장하려면 제거 전략을 Strategy 패턴으로 뽑아낼 수 있습니다.
⚖️ Trade-off: 전체 메서드에 synchronized를 걸면 단순하지만 동시성이 낮아집니다. 더 높이려면 세분화된 락이나 ConcurrentHashMap + 별도 동기화가 필요한데 복잡도가 큽니다.
✅ Fix: 면접에서는 먼저 synchronized로 정확성을 보장하고, 필요하면 더 정교한 락으로 간다고 말합니다. 제거 정책은 EvictionPolicy 인터페이스로 추상화해 LFU 등을 끼울 수 있습니다.
🔧 도구:StrategyOCP
```
// Thread-safety: wrap get/put in synchronized for correctness first.
// Extension: pull out eviction as a Strategy.
interface EvictionPolicy {
    Node pickVictim(Node head, Node tail);
}
// LRU impl returns tail.prev; an LFU impl could pick by frequency.
```
🗣 영어로 말해
“For concurrency I'd synchronize first, and I'd extract eviction as a Strategy for LFU.”
checking microphone…

8단계 영어를 다 말하면 → 이 메커니즘 전체를 영어로 설명할 수 있게 된다.

Full Java (javac-verified)

import java.util.HashMap;
import java.util.Map;

public class Solution {

    static final class LRUCache {

        private static final class Node {
            int key;
            int value;
            Node prev;
            Node next;
            Node(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }

        private final int capacity;
        private final Map<Integer, Node> map = new HashMap<>();
        private final Node head = new Node(0, 0); // most recent side
        private final Node tail = new Node(0, 0); // least recent side

        LRUCache(int capacity) {
            this.capacity = capacity;
            head.next = tail;
            tail.prev = head;
        }

        private void remove(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        private void addFront(Node node) {
            node.next = head.next;
            node.prev = head;
            head.next.prev = node;
            head.next = node;
        }

        public synchronized int get(int key) {
            Node node = map.get(key);
            if (node == null) return -1;
            remove(node);
            addFront(node);
            return node.value;
        }

        public synchronized void put(int key, int value) {
            Node node = map.get(key);
            if (node != null) {
                node.value = value;
                remove(node);
                addFront(node);
                return;
            }
            if (capacity <= 0) return;
            if (map.size() == capacity) {
                Node lru = tail.prev;
                remove(lru);
                map.remove(lru.key);
            }
            Node fresh = new Node(key, value);
            map.put(key, fresh);
            addFront(fresh);
        }
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // 1
        cache.put(3, 3);                   // evicts key 2
        System.out.println(cache.get(2)); // -1
        cache.put(4, 4);                   // evicts key 1
        System.out.println(cache.get(1)); // -1
        System.out.println(cache.get(3)); // 3
        System.out.println(cache.get(4)); // 4
    }
}

🎙 이 카드 AI랑 음성 대화 · 기록 저장