#include <iostream>
#include <unordered_map>
using namespace std;
// Abstract class for the LRUCache
class LRUCache {
public:
virtual int get(int key) = 0;
virtual void set(int key, int value) = 0;
};
// Node class for the doubly linked list
class Node {
public:
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) {
key = k;
value = v;
prev = nullptr;
next = nullptr;
}
};
// Doubly linked list implementation
class DoublyLinkedList {
private:
Node* head;
Node* tail;
int size;
public:
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
void addToHead(Node* node) {
if (head == nullptr) {
head = node;
tail = node;
} else {
node->next = head;
head->prev = node;
head = node;
}
size++;
}
void removeNode(Node* node) {
if (node == head) {
head = head->next;
} else if (node == tail) {
tail = tail->prev;
} else {
node->prev->next = node->next;
node->next->prev = node->prev;
}
size--;
}
Node* getTail() {
return tail;
}
int getSize() {
return size;
}
};
// LRUCache implementation using the abstract class
class LRUCacheImpl : public LRUCache {
private:
int capacity;
DoublyLinkedList cache;
unordered_map map;
public:
LRUCacheImpl(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if (map.find(key) != map.end()) {
Node* node = map[key];
// Move the accessed node to the head of the list
cache.removeNode(node);
cache.addToHead(node);
return node->value;
}
return -1;
}
void set(int key, int value) {
if (map.find(key) != map.end()) {
// Update the value of an existing key
Node* node = map[key];
node->value = value;
// Move the updated node to the head of the list
cache.removeNode(node);
cache.addToHead(node);
} else {
if (cache.getSize() == capacity) {
// Remove the least recently used node from the tail
Node* tail = cache.getTail();
map.erase(tail->key);
cache.removeNode(tail);
delete tail;
}
// Create a new node and add it to the head of the list
Node* newNode = new Node(key, value);
cache.addToHead(newNode);
map[key] = newNode;
}
}
};
// Main function
int main() {
int capacity, queries;
cin >> capacity >> queries;
LRUCacheImpl cache(capacity);
for (int i = 0; i < queries; i++) {
string operation;
cin >> operation;
if (operation == "GET") {
int key;
cin >> key;
cout << cache.get(key) << endl;
} else if (operation == "SET") {
int key, value;
cin >> key >> value;
cache.set(key, value);
}
}
return 0;
}
Explanation:
The code starts by defining the abstract class LRUCache with pure virtual functions get and set.
Next, the Node class is defined to represent a node in the doubly linked list. It contains the key, value, and pointers to the previous and next nodes.
The DoublyLinkedList class is implemented to handle the operations of adding nodes to the head and removing nodes from the list.
The LRUCacheImpl class inherits from the LRUCache abstract class and implements the get and set functions.
In the LRUCacheImpl class, a doubly linked list cache is used to store the nodes, and an unordered map map is used to store the mapping between keys and nodes.
The get function checks if the key exists in the cache. If it does, the corresponding node is moved to the head of the list, indicating it was recently accessed.
The set function checks if the key exists in the cache. If it does, the value is updated, and the corresponding node is moved to the head of the list. If the cache is full, the least recently used node is removed from the tail.
In the main function, the capacity and number of queries are input from the user. Then, a LRUCacheImpl object is created.
The queries are processed using a loop. If the operation is "GET," the key is input, and the get function is called to retrieve the value. If the operation is "SET," the key and value are input, and the set function is called to insert/update the key-value pair.
Finally, the output is displayed according to the requirements of the problem.
Example Input
2 8
SET 1 1
SET 2 2
GET 1
GET 2
SET 3 3
GET 1
GET 3
GET 2
Example Output
1
2
-1
3
Explanation:
The cache has a capacity of 2.
In the first two queries, the key-value pairs (1, 1) and (2, 2) are inserted into the cache.
The next two queries perform "GET" operations for keys 1 and 2, respectively. The corresponding values are retrieved from the cache.
In the fifth query, the key-value pair (3, 3) is inserted into the cache. Since the cache is full, the least recently used node (key=2) is removed.
The last three queries perform "GET" operations for keys 1, 3, and 2, respectively. The corresponding values are retrieved from the cache.
Note: The code provided is a complete solution for the "Abstract Classes - Polymorphism" problem on HackerRank and should be submittable without any issues.