1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

package leetcode.datastructures

class LFUCache(private val capacity: Int) {
    class Node(val key: Int, var value: Int) {
        var frequency: Int = 1
        var prev: Node? = null
        var next: Node? = null
    }

    class DoublyLinkedList {
        var head = Node(0, 0)
        var tail = Node(0, 0)

        init {
            tail.prev = head
            head.next = tail
        }

        fun addNode(node: Node) {
            node.next = tail
            node.prev = tail.prev
            tail.prev?.next = node
            tail.prev = node
        }

        fun removeNode(node: Node) {
            node.prev?.next = node.next
            node.next?.prev = node.prev
        }
    }

    private val cache = mutableMapOf<Int, Node>()
    private val frequencyMap = mutableMapOf<Int, DoublyLinkedList>()
    private var minFrequency = 0

    fun get(key: Int): Int {
        if (!cache.containsKey(key)) return -1

        val node = cache[key]!!
        update(node)

        return node.value
    }

    fun put(key: Int, value: Int) {
        if (capacity <= 0) return

        if (cache.containsKey(key)) {
            val node = cache[key]!!
            node.value = value
            update(node)
            return
        } else {
            if (cache.size == capacity) {
                val node = frequencyMap[minFrequency]!!.head.next!!
                frequencyMap[minFrequency]!!.removeNode(node)
                cache.remove(node.key)
            }
            val newNode = Node(key, value)
            cache[key] = newNode
            if (!frequencyMap.containsKey(newNode.frequency)) {
                frequencyMap[newNode.frequency] = DoublyLinkedList()
            }
            frequencyMap[newNode.frequency]!!.addNode(newNode)
            minFrequency = 1
        }
    }

    private fun update(node: Node) {
        val frequency = node.frequency
        node.frequency++
        val keys = frequencyMap[frequency]!!
        keys.removeNode(node)
        if (minFrequency == frequency && keys.head.next == keys.tail) {
            minFrequency++
        }
        if (!frequencyMap.containsKey(frequency + 1)) {
            frequencyMap[frequency + 1] = DoublyLinkedList()
        }
        frequencyMap[frequency + 1]!!.addNode(node)
    }
}