Coding Interview

coding interview questions part 1

Pinterest LinkedIn Tumblr

LRU Cache

Least Recently Used (LRU) cache algorithm removes the least recently used items first.
This algorithm keeps track of all items insertion order to delete the least recently used items first. If any item inserts or delete, the cache items lifetime change and update the cache.
LRU size 4.
Insert 0,1,2,3.
Insert two number 4 and 5.
The LRU data updated with 2,3,4,5

Source Code

package com.dsacode.Probelms;

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache< K, V >{
    Map< K, V > map = new LinkedHashMap< K, V >(  );
    public LRUCache (final int limit) {
      map = new LinkedHashMap < K, V > (16, 0.75f, true) {
    	  		private static final long serialVersionUID = 1L;       
    	  		protected boolean removeEldestEntry(final Map.Entry< K, V > eldest) {
                   return super.size() > limit;
    public void put ( K key, V value ) {
        map.put ( key, value );
    public V get ( K key ) {
        return map.get(key);
    public void remove ( K key ) {
        map.remove ( key );
    public int size () {
        return map.size ();
    public String toString() {
        return map.toString ();
    public static void main(String[] args) {
    	int size=4;
    	LRUCache < Integer, Integer > cache = new LRUCache< > ( size );
    	for(int i = 0; i < size; i++)
        System.out.print("size:"+ cache.size() +" Items:");
        for(int i = 0; i < size; i++){
        		System.out.print(cache.get(i) +" ");		
        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        System.out.print("\nsize:"+ cache.size() +" Items:");
        for(int i=0; i < size+2; i++){
        		System.out.print(cache.get(i) +" ");		
#include "stdafx.h"

#include < stdio.h >
#include < stdlib.h >
#include < iostream >
using namespace std;

class QueueNode
	 QueueNode *prev, *next;
	unsigned pageNumber;  
} ;

class Queue
	unsigned count;  
	unsigned numberOfFrames; 
	QueueNode *front, *rear;
} ;

class Hash
	int capacity; 
	QueueNode* *array; 
} ;

QueueNode* newQNode(unsigned pageNumber)
	QueueNode* temp = (QueueNode *)malloc(sizeof(QueueNode));
	temp->pageNumber = pageNumber;

	temp->prev = temp->next = NULL;

	return temp;

Queue* createQueue(int numberOfFrames)
	Queue* queue = (Queue *)malloc(sizeof(Queue));

	queue->count = 0;
	queue->front = queue->rear = NULL;

	queue->numberOfFrames = numberOfFrames;

	return queue;

Hash* createHash(int capacity)
	Hash* hash = (Hash *)malloc(sizeof(Hash));
	hash->capacity = capacity;

	hash->array = (QueueNode **)malloc(hash->capacity * sizeof(QueueNode*));

	int i;
	for (i = 0; i < hash->capacity; ++i)
		hash->array[i] = NULL;

	return hash;

int AreAllFramesFull(Queue* queue)
	return queue->count == queue->numberOfFrames;

int isQueueEmpty(Queue* queue)
	return queue->rear == NULL;

void deQueue(Queue* queue)
	if (isQueueEmpty(queue))

	if (queue->front == queue->rear)
		queue->front = NULL;

	QueueNode* temp = queue->rear;
	queue->rear = queue->rear->prev;

	if (queue->rear)
		queue->rear->next = NULL;



void Enqueue(Queue* queue, Hash* hash, unsigned pageNumber)
	if (AreAllFramesFull(queue))
		hash->array[queue->rear->pageNumber] = NULL;

	QueueNode* temp = newQNode(pageNumber);
	temp->next = queue->front;

	if (isQueueEmpty(queue))
		queue->rear = queue->front = temp;
		queue->front->prev = temp;
		queue->front = temp;

	hash->array[pageNumber] = temp;


void ReferencePage(Queue* queue, Hash* hash, unsigned pageNumber)
	QueueNode* reqPage = hash->array[pageNumber];

	if (reqPage == NULL)
		Enqueue(queue, hash, pageNumber);
	else if (reqPage != queue->front)
		reqPage->prev->next = reqPage->next;
		if (reqPage->next)
			reqPage->next->prev = reqPage->prev;

		if (reqPage == queue->rear)
			queue->rear = reqPage->prev;
			queue->rear->next = NULL;

		reqPage->next = queue->front;
		reqPage->prev = NULL;

		reqPage->next->prev = reqPage;

		queue->front = reqPage;

int _tmain(int argc, _TCHAR* argv[])
	Queue* q = createQueue(4);

	Hash* hash = createHash(10);
	ReferencePage(q, hash, 0);
	ReferencePage(q, hash, 1);
	ReferencePage(q, hash, 2);
	ReferencePage(q, hash, 3);

	cout << "size : 4 Items : ";
	cout << q->front->pageNumber << " ";
	cout << q->front->next->pageNumber << " ";
	cout << q->front->next->next->pageNumber << " ";
	cout << q->front->next->next->next->pageNumber << endl;

	ReferencePage(q, hash, 4);
	ReferencePage(q, hash, 5);

	cout << "size : 4 Items : ";
	cout << q->front->pageNumber << " ";
	cout << q->front->next->pageNumber << " ";
	cout << q->front->next->next->pageNumber << " ";
	cout << q->front->next->next->next->pageNumber << endl;

	return 0;


size:4 Items:0 1 2 3
size:4 Items:2 3 4 5

Algorithm Explanation

Create an instance of LinkedHashMap with override removeEldestEntry function.
If the limit is greater than size, remove the oldest entry in LinkedHashMap.
Put add the element and get use get the element from the map.
Remove delete the key and value.
1 2 3 4 5


  1. Excellent post. I was checking continuously this blog and I’m impressed! Extremely helpful information particularly the last part 🙂 I care for such information much. I was seeking this certain information for a long time. Thank you and good luck.

  2. I know this if off topic but I’m looking into starting my own weblog and was curious what all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very web smart so I’m not 100 certain. Any suggestions or advice would be greatly appreciated. Thanks

  3. The subsequent time I read a weblog, I hope that it doesnt disappoint me as much as this one. I mean, I do know it was my option to learn, but I actually thought youd have something interesting to say. All I hear is a bunch of whining about something that you could repair if you werent too busy in search of attention.

  4. whoah this weblog is magnificent i love studying your posts. Keep up the great paintings! You understand, many individuals are looking around for this info, you can aid them greatly.

  5. magnificent points altogether, you simply gained a logo new reader. What may you recommend about your put up that you simply made a few days in the past? Any positive?

  6. My brother suggested I might like this blog. He was totally right. This post truly made my day. You cann’t imagine simply how much time I had spent for this information! Thanks!

  7. Just about all of what you state is astonishingly legitimate and that makes me ponder why I hadn’t looked at this in this light previously. Your article truly did switch the light on for me personally as far as this issue goes. Nonetheless there is actually just one factor I am not too comfortable with so while I attempt to reconcile that with the core theme of your point, allow me observe what all the rest of your readers have to say.Very well done.

  8. Hey! This is my first visit to your blog! We are a team of volunteers and starting a new initiative in a community in the same niche. Your blog provided us useful information to work on. You have done a outstanding job!

  9. With the whole thing that appears to be developing throughout this particular subject matter, all your points of view are actually fairly stimulating. However, I beg your pardon, but I do not give credence to your entire strategy, all be it exciting none the less. It seems to us that your opinions are actually not entirely validated and in actuality you are yourself not even entirely certain of your point. In any event I did appreciate reading through it.

  10. There are some interesting time limits on this article however I don’t know if I see all of them heart to heart. There is some validity however I’ll take maintain opinion until I look into it further. Good article , thanks and we would like more! Added to FeedBurner as effectively

  11. Hi! Someone in my Myspace group shared this website with us so I came to look it over. I’m definitely enjoying the information. I’m book-marking and will be tweeting this to my followers! Great blog and fantastic style and design.

  12. Aw, this was a really nice post. In concept I want to put in writing like this additionally – taking time and precise effort to make a very good article… but what can I say… I procrastinate alot and not at all seem to get something done.

  13. I believe that is among the such a lot significant info for me. And i’m glad reading your article. However want to observation on few basic things, The site style is great, the articles is truly excellent : D. Good job, cheers

  14. I do agree with all the ideas you have presented in your post. They’re very convincing and will certainly work. Still, the posts are too short for beginners. Could you please extend them a little from next time? Thanks for the post.

  15. Amazing blog! Do you have any helpful hints for aspiring writers? I’m hoping to start my own blog soon but I’m a little lost on everything. Would you propose starting with a free platform like WordPress or go for a paid option? There are so many options out there that I’m completely overwhelmed .. Any tips? Cheers!

  16. you’re really a excellent webmaster. The web site loading velocity is incredible. It kind of feels that you’re doing any distinctive trick. Furthermore, The contents are masterwork. you’ve performed a excellent task in this topic!

  17. Nice read, I just passed this onto a friend who was doing some research on that. And he actually bought me lunch since I found it for him smile Therefore let me rephrase that: Thanks for lunch!

  18. I enjoy what you guys are usually up too. This sort of clever work and exposure! Keep up the superb works guys I’ve incorporated you guys to blogroll.

  19. Thank you for any other great post. Where else may anybody get that type of info in such a perfect method of writing? I have a presentation next week, and I am at the look for such info.

  20. Hey there I am so excited I found your weblog, I really found you by accident, while I was looking on Askjeeve for something else, Nonetheless I am here now and would just like to say many thanks for a fantastic post and a all round entertaining blog (I also love the theme/design), I don’t have time to read it all at the minute but I have book-marked it and also added your RSS feeds, so when I have time I will be back to read more, Please do keep up the awesome job.

  21. With havin so much content do you ever run into any issues of plagorism or copyright violation? My website has a lot of completely unique content I’ve either written myself or outsourced but it looks like a lot of it is popping it up all over the web without my authorization. Do you know any solutions to help reduce content from being ripped off? I’d truly appreciate it.

  22. I do believe all of the ideas you’ve presented in your post. They’re really convincing and can certainly work. Still, the posts are very short for beginners. May you please extend them a bit from next time? Thanks for the post.

  23. Hey there! I just wanted to ask if you ever have any problems with hackers? My last blog (wordpress) was hacked and I ended up losing a few months of hard work due to no backup. Do you have any solutions to prevent hackers?

Write A Comment