Abstract Classes - Polymorphism in C++ - Hacker Rank Solution
Problem
Abstract base classes in C++ can only be used as base classes. Thus, they are allowed to have virtual member functions without definitions.
A cache is a component that stores data so future requests for that data can be served faster. The data stored in a cache might be the results of an earlier computation, or the duplicates of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache which is faster than recomputing a result or reading from a slower data store. Thus, the more requests that can be served from the cache, the faster the system performs.
One of the popular cache replacement
policies is: "least recently used" (LRU). It discards the least recently used
items first.
For example, if a cache with a capacity to store 5 keys has the following state(arranged from most recently used key to least recently used key) -
5 3 2 1 4
Now, If the next key comes as 1(which is a cache hit), then the cache state in the same order will be -
1 5 3 2 4
6 1 5 3 2
Given an abstract base class Cache with member variables and functions:
mp - Map the key to the node in the linked list
cp - Capacity
tail - Double linked list tail pointer
head - Double linked list head pointer
set() - Set/insert the value of the key, if present, otherwise add the key as the most recently used key. If the cache has reached its capacity, it should replace the least recently used key with a new key.
get() - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
You have to write a class LRUCache which extends the class Cache and uses the member functions and variables to implement an LRU cache.
Input Format :
The following N lines can either contain get or set commands.
An input line starting with get will be followed by a
key to be found in the cache. An input line starting with
set will be followed by the key and
value respectively to be inserted/replaced in the cache.
Constraints :
1 <= N <= 500000
1 <= M <= 1000
1 <= key <= 20
1 <= value <= 2000
Output Format :
The code provided in the editor will use your derived class
LRUCache to output the value whenever a get command is encountered.
Sample Input :
3 1 set 1 2 get 1 get 2
Sample Output :
2 -1
Explanation :
Since, the capacity of the cache is 1, the first set results in setting
up the key 1 with it's value 2. The first get results in a cache hit of
key 1, so 2 is printed as the value for the first get. The second
get is a cache miss, so -1 is printed.
Solution :
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 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
// Abstract Classes - Polymorphism in C++ - Hacker Rank Solution #include <iostream> #include <vector> #include <map> #include <string> #include <algorithm> #include <set> #include <cassert> using namespace std; struct Node { Node* next; Node* prev; int value; int key; Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){}; Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){}; }; class Cache { protected: map<int,Node*> mp; //map the key to the node in the linked list int cp; //capacity Node* tail; // double linked list tail pointer Node* head; // double linked list head pointer virtual void set(int, int) = 0; //set function virtual int get(int) = 0; //get function }; // Abstract Classes - Polymorphism in C++ - Hacker Rank Solution start class LRUCache: public Cache { public: LRUCache(int c) { cp = c; } void set(int k, int v) { Node* N; if ( mp.empty() ) { N = new Node(k,v); tail = head = N; mp[k] = N; return; } auto it = mp.find(k); if ( it != mp.end() ) { it->second->value = v; if ( head == it->second ) { return; } it->second->prev->next = it->second->next; if ( tail == it->second ) { tail = tail->prev; } else { it->second->next->prev = it->second->prev; } it->second->next = head; it->second->prev = nullptr; head->prev = it->second; head = it->second; } else { N = new Node(head->prev, head, k, v); head->prev = N; head = N; mp[k] = N; if ( mp.size() > cp ) { tail = tail->prev; mp.erase(tail->next->key); delete tail->next; tail->next = nullptr; } } } int get(int k) { auto it = mp.find(k); if ( it != mp.end() ) { return it->second->value; } return -1; } }; // Abstract Classes - Polymorphism in C++ - Hacker Rank Solution End int main() { int n, capacity,i; cin >> n >> capacity; LRUCache l(capacity); for(i=0;i<n;i++) { string command; cin >> command; if(command == "get") { int key; cin >> key; cout << l.get(key) << endl; } else if(command == "set") { int key, value; cin >> key >> value; l.set(key,value); } } return 0; } |
the above hole problem statement is given by hackerrank.com but the solution is generated by the codeworld19 authority if any of the query regarding this post or website fill the following contact form thank you.
CodeWorld19
Hey, I am Parthe Omkar