Q1. The least recently used (LRU) cache algorithm exists the element from the cache(when it’s full) that was least recently used. After an element is requested from the cache, it should be added to the cache (if not already there) and considered the most recently used element in the cache.
rnInitially, the cache is empty. The input to the function LruCountMiss shall consist of an integer max_cache_size, an array pages and its length Len
rnThe function should return an integer for the number of cache misses using the LRU cache algorithm.
rnAssume that the array pages always have pages numbered from 1 to 50.
rnTEST CASES:
rnTEST CASE1:
rnINPUT:
3,[7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0],16
EXPECTED RETURN VALUE:
11
TESTCASE 2:
rnINPUT:
2,[2,3,1,3,2,1,4,3,2],9
EXPECTED RETURN VALUE:
8
EXPLANATION:
The following page numbers are missed one after the other 2,3,1,2,1,4,3,2.This results in 8 page misses.
Existing Program
rnint lruCountMiss(int max_cache_size, int *pages,int len)
rn{/
rn/write tour code
rn}
rnSolved Program
rn#include<iostream>
rnusing namespace std;
rnint lruCountMiss(int max_cache_size, int *pages,int len)
rn{
rnint miss=0,cache[max_cache_size]; /*variable miss and cache declared*/
rnfor (int i=0;i<max_cache_size;i++){
rn/*this is for clearing value of cache i.e. to empty cache. I used any value here*/
rncache[i]=0x87787;
rn}
rnfor (int i=0;i<len;i++){ /*for loop for all the value from list one by one*/
rnfor(int j=0;j<max_cache_size;j++){
rn/*loop to check the cache value, if it matches the value*/
rnif (pages[i]==cache[j]){
rnfor (int k=i; k<max_cache_size;k++){
rn/*if the value is already present in the cache then shifting values from the present value.*/
rncache[i]=cache[i+1];
rn}
rncache[max_cache_size-1]=pages[i]; /*updating the last value of cache*/
rnrn
break;
rn}
rnelse if(j==(max_cache_size-1)){
rnfor (int l=0; l<max_cache_size;l++){
rn/*if the value is not present in the cache then shifting values from starting.*/
rncache[l]=cache[l+1];
rn}
rncache[max_cache_size-1]=pages[i];
rn/*updating the last value of cache*/
rnmiss++;
rnrn
}
rn}}
rnreturn miss;}/*returning the Miss*/
rnrn
int main(){ /*main function*/
rncout<< “We are checking two cases.n”<<”Case 1:t”<<”Array values are [7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0] nand cache size= 3; and total values to check are 16: n We got the miss. “;
rnint days,pages[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0};
rn/*array to pass through function*/
rnint *cellsptr=pages;
rn/*creating array values to pointer*/
rncout<<”Miss =t”<<lruCountMiss(3,cellsptr,16);//passing to function
rncout<<”nnCase 2:t”<<”Array values are [2,3,1,3,2,1,4,3,2] nand cache size= 2; and total values to check are 9: n We got the miss. “;
rnint pages2[]={2,3,1,3,2,1,4,3,2};
rnint *cellsptr2=pages2;
rn/*creating array values to pointer*/
rncout<<”Miss =t”<<lruCountMiss(2,cellsptr2,9);//passing to function
rnreturn 0;
rn}
rnrn
One practice question for you.
rnWrite a function to insert an integer into a circular linked _list whose elements are sorted in ascending order 9smallest to largest). The input to the function insert Sorted List is a pointer start to some node in the circular list and an integer n between 0 and 100. Return a pointer to the newly inserted node…
rnThe structure to follow for a node of the circular linked list is
Struct CNode ;
Typedef struct CNode cnode;
Struct CNode
{I
nt value;
Cnode* next;
};C
node* insertSortedList (cnode* start,int n
{/
/WRITE YOUR CODE HERE
}/
/FUNCTION SIGNATURE ENDS
Test Case 1:
Input:
[3>4>6>1>2>^],5
Expected Return Value:
[5>6>1>2>3>4>^]
Test Case 2:
Input:
[1>2>3>4>5>^],0
Expected Return Value:
[0>1>2>3>4>5>^]
Given the maximum size of the cache and a list of integers (to request from the cache), calculate the number of cache misses using the LRU cache algorithm. A cache miss occur when the requested integer does not exist in the cache.
rnAttention!!
rnTCS off-campus drive for freshers is coming soon.
rnThe number of students aspiring to join TCS is very high and the TCS drive is being conducted pan-India. Hence, it is not going to be easy to stand out in this pool drive.
rnFACE has helped thousands of students get placed in TCS. From the 35 thousand students TCS recruited last year, 30 thousand had been trained by FACE. With requests of TCS coaching pouring in, we are coming up with a first-of-its-kind 2 day online webinar to help you crack the TCS drive.
rnOur webinar will consist of 5 sessions:
rn1. TCS – Email writing
rn2. TCS – Most Repeated Aptitude Questions
rn3. TCS – Most Repeated Programs
rn4. TCS – Frequently asked Technical MCQ
rn5. TCS – Interview questions
rnWe will provide intensive training for each section. Additionally, 3 to 5 practice tests will be provided for each section.
rnOnly 500 seats, on first come first serve basis.
rnDates of the Webinar: 25th and 26th January, 2018
rnDuration: 15 hours (2 days)
rnPrice: INR 2999
rnFACE Prep students can avail this course at Rs 1999 (till seats remain).
rnUse the coupon code TCSMAR at the time of purchase.
rn