How to implement LRU caching scheme? What data structures should be used?
We are given total possible page numbers that can be referred. We are also given cache (or memory) size (Number of page frames that cache can hold at a time). The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache. Please see the Galvin book for more details (see the LRU page replacement slide here).
We use two data structures to implement an LRU Cache.
1. A Queue which is implemented using a doubly linked list. The maximum size of the queue will be equal to the total number of frames available (cache size).
The most recently used pages will be near front end and least recently pages will be near rear end.
2. A Hash with page number as key and address of the corresponding queue node as value.
When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
If the required page is not in the memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of queue, and add the new node to the front of queue.
Note: Initially no page is in the memory.
Below is C implementation:
// A C program to show implementation of LRU cache
// A Queue Node (Queue is implemented using Doubly Linked List)
structQNode *prev, *next;
unsigned pageNumber; // the page number stored in this QNode
// A Queue (A FIFO collection of Queue Nodes)
unsigned count; // Number of filled frames
unsigned numberOfFrames; // total number of frames
QNode *front, *rear;
// A hash (Collection of pointers to Queue Nodes)
intcapacity; // how many pages can be there
QNode* *array; // an array of queue nodes
// A utility function to create a new Queue Node. The queue Node
// will store the given 'pageNumber'
QNode* newQNode( unsigned pageNumber )
// Allocate memory and assign 'pageNumber'
QNode* temp = (QNode *)malloc( sizeof( QNode ) );
temp->pageNumber = pageNumber;
// Initialize prev and next as NULL
temp->prev = temp->next = NULL;
// A utility function to create an empty Queue.
// The queue can have at most 'numberOfFrames' nodes
Measuring Time Logic Puzzle
You are given with two ropes with variable width. However if we start burning both the ropes, they will burn at exactly same time i.e. an hour. The ropes are non-homogeneous in nature. You are asked to measure 45 minutes by using these two ropes.
How can you do it?
Please note that you can’t break the rope in half as it is being clearly stated that the ropes are non-homogeneous in nature. Answer & ExplanationSolution:
All you have to do is burn the first rope from both the ends and the second rope from one end only simultaneously. The first rope will burn in 30 minutes (half of an hour since we burned from both sides) while the other rope would have burnt half. At this moment, light the second rope from the other end as well. Where, the second rope would have taken half an hour more to burn completely, it will take just 15 minutes as we have lit it from the other end too.
Thus you have successfully calculated 30+15 = 45 minutes …
Select 01-Select All Given a City table, whose fields are described
as +-------------+----------+ |
Field | Type | +-------------+----------+ |
ID | int(11) | |
Name | char(35) | |
CountryCode | char(3) | |
District | char(20) | |
Population | int(11) | +-------------+----------+ write a query that will fetch all columns for every row in the
table. My Solution SELECT*FROM city; --------------------------------------------------------------------------------- 02-Select by ID Given a City table, whose fields are described