The least recently used (LRU) cache
algorithm evicts the element from the cache that was least recently used when
the cache is full. After an element is requested from the cache, it should be
added to the cache (if not there) and considered the most recently used element
in the cache whether it is newly added or was already existing. Initially, the
cache is empty. Implement the function lruCountMiss so that the function
returns an integer indicating the number of cache misses M using the LRU cache
algorithm execution for the given input. Assume that the array pages always
have pages numbered from 0 to 50. (A hit means the requested page is already
existing in the cache and a miss means the requested page is not found in the
cache).
Input
Format:
The first line contains the cache size S
and the number of page requests N separated by a space. The second line
containing the N pages being requested from the cache.
Output
Format:
The first line contains the miss count M.
Boundary
Conditions:
2 <= S <= N 2 <= N <= 100
Example
Input/Output 1:
Input:
3 16
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0
Output: 11
Solution
1:
s,n=[int(i) for i in input().split()]
p=[int(i) for i in input().split()]
c,m=[],0
for i in p:
if i in c:
c.remove(i)
else:
if len(c)>=s:
c.pop(0)
m=m+1
c.append(i)
print(m)
Solution
2:
#include <bits/stdc++.h>
using namespace std;
int main()
{
int i,s,n,a,m=0;
list<int> c;
cin>>s>>n;
for(i=0;i<n;i++)
{
cin>>a;
if(find(c.begin(),c.end(),a)!=c.end())
c.remove(a);
else
{
if(c.size()>=s)
c.pop_front();
m++;
}
c.push_back(a);
}
cout<<m;
return 0;
}
Solution
3:
s,n=[int(i) for i
in input().split()]
arr_pages=[int(i)
for i in input().split()]
cache=[None]*s
x,miss=0,0
for i in arr_pages:
if not cache or x<s and not i in cache:
cache[x]=i
x+=1
miss+=1
else:
if i not in cache:
miss+=1
begin=0
else:
begin=cache.index(i)
for j in range(begin,s):
cache[j]=cache[j+1] if j<s-1 else i
print(miss)