python coding question

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
What is considered as `used`?
Both get and put are considered as used.

Example 1:

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]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

class Node:
    def __init__(self, key, value, left=None, right=None):
        self.key = key
        self.value = value
        self.left = left
        self.right = right


class LRUCache(object):

    def __init__(self, capacity):
        self.cap = capacity
        self.head, self.tail = None, None
        self.keyMap = dict()

    def get(self, key):
        if key not in self.keyMap:
            return -1
        node = self.keyMap[key]
        self.removeNode(node)
        self.addingNodeFront(node)
        return node.value

    def put(self, key, value):
        if key in self.keyMap:
            # Move the key in the first.
            keyNode = self.keyMap[key]
            self.removeNode(keyNode)
            self.addingNodeFront(keyNode)

        else:
            # first check the capacity.
            if len(self.keyMap) < self.cap:
                # if less than capacity, add the key in the first
                newNode = Node(key, value)
                if self.head == None:
                    self.head = newNode
                    self.tail = newNode
                else:
                    self.addingNodeFront(newNode)
                    # add the node to Mapp
                self.keyMap[key] = newNode
            else:
                # else remove the last in the list and add the new key in the first. and add the node in keymap
                tmp = self.tail
                self.tail = tmp.left
                self.tail.right = None
                self.keyMap.pop(tmp.key)

                newNode = Node(key, value)
                self.addingNodeFront(newNode)
                self.keyMap[key] = newNode

        print(self.keyMap)

    def addingNodeFront(self, node):
        tmp = self.head
        self.head = node
        node.right = tmp
        tmp.left = node

    def removeNode(self, node):
        _prev = node.left
        _next = node.right

        if _prev == None:

            self.head = node.right
            _next.left = None

        elif _next == None:
            self.tail = node.left
            _prev.right = None

        else:
            _prev.right = _next
            _next.left = _prev
Test Code
lRUCache = LRUCache(2)
lRUCache.put(1, 1)  # cache is {1=1}
lRUCache.put(2, 2)  # cache is {1=1, 2=2}
print(lRUCache.get(1))  # // return 1
lRUCache.put(3, 3)  # // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
print(lRUCache.get(2))  # // returns -1 (not found)
lRUCache.put(4, 4)  # // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
# lRUCache.get(1);    // return -1 (not found)
# lRUCache.get(3);    // return 3
# lRUCache.get(4);    // return 4