AMCAT Automata Question bank | Set-2

AMCAT Automata Question bank | Set-2

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.

rn

Initially, 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

rn

The function should return an integer for the number of cache misses using the LRU cache algorithm.

rn

Assume that the array pages always have pages numbered from 1 to 50.

rn

TEST CASES:

rn

TEST CASE1:

rn

INPUT:
3,[7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0],16

rn

EXPECTED RETURN VALUE:
11

rn

TESTCASE 2:

rn

INPUT:
2,[2,3,1,3,2,1,4,3,2],9

rn

EXPECTED RETURN VALUE:
8

rn

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.

rn

Existing Program

rn

int lruCountMiss(int max_cache_size, int *pages,int len)

rn

{/

rn

/write tour code

rn

}

rn

Solved Program

rn

#include<iostream>

rn

using namespace std;

rn

int lruCountMiss(int max_cache_size, int *pages,int len)

rn

{

rn

int miss=0,cache[max_cache_size]; /*variable miss and cache declared*/

rn

for (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*/

rn

cache[i]=0x87787;

rn

}

rn

for (int i=0;i<len;i++){ /*for loop for all the value from list one by one*/

rn

for(int j=0;j<max_cache_size;j++){

rn

/*loop to check the cache value, if it matches the value*/

rn

if (pages[i]==cache[j]){

rn

for (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.*/

rn

 cache[i]=cache[i+1];

rn

}

rn

cache[max_cache_size-1]=pages[i]; /*updating the last value of cache*/

rn

 

rn

break;

rn

}

rn

else if(j==(max_cache_size-1)){

rn

for (int l=0; l<max_cache_size;l++){

rn

/*if the value is not present in the cache then shifting values from starting.*/

rn

cache[l]=cache[l+1];

rn

}

rn

cache[max_cache_size-1]=pages[i];

rn

/*updating the last value of cache*/

rn

 miss++;

rn

 

rn

}

rn

}}

rn

return miss;}/*returning the Miss*/

rn

 

rn

int main(){ /*main function*/

rn

cout<< “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. “;

rn

int days,pages[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0};

rn

/*array to pass through function*/

rn

int *cellsptr=pages;

rn

/*creating array values to pointer*/

rn

cout<<”Miss =t”<<lruCountMiss(3,cellsptr,16);//passing to function

rn

cout<<”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. “;

rn

int pages2[]={2,3,1,3,2,1,4,3,2};

rn

int *cellsptr2=pages2;

rn

/*creating array values to pointer*/

rn

cout<<”Miss =t”<<lruCountMiss(2,cellsptr2,9);//passing to function

rn

return 0;

rn

}

rn

 

rn

One practice question for you.

rn

Write 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…

rn

The 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

rn


Test Case 1:

rn


Input:
[3>4>6>1>2>^],5
Expected Return Value:
[5>6>1>2>3>4>^]

rn

Test Case 2:

Input:
[1>2>3>4>5>^],0
Expected Return Value:
[0>1>2>3>4>5>^]

rn

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.

rn

Attention!!

rn

TCS off-campus drive for freshers is coming soon.

rn

The 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.

rn

FACE 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.

rn

Our webinar will consist of 5 sessions:

rn

1. TCS – Email writing

rn

2. TCS – Most Repeated Aptitude Questions

rn

3. TCS – Most Repeated Programs

rn

4. TCS – Frequently asked Technical MCQ

rn

5. TCS – Interview questions

rn

We will provide intensive training for each section. Additionally, 3 to 5 practice tests will be provided for each section.

rn

Only 500 seats, on first come first serve basis.

rn

Dates of the Webinar: 25th and 26th January, 2018

rn

Duration: 15 hours (2 days)

rn

Price: INR 2999

rn

FACE Prep students can avail this course at Rs 1999 (till seats remain).

rn

Use the coupon code TCSMAR at the time of purchase.

rn

Click here to register. See you at the webinar!