Custom LRU Cache implementation In Javascript

Hello Folks,

It has been a long time since I wrote something new on my blog and now, This year’s resolution is to get back to writing 🙂

On that note, I have tried my hands on a very frequently asked question in the interviews, about custom LRU cache.

LRU cache is known as Least Recently Used cache, This is a caching strategy to determine how to make space in cache when it is full of its capacity. This strategy instructs to keeps the recently used items on the top and least recently used items on the bottom.

The approach to implement LRU Cache is very intuitive, The overall goal is to have a cache, where Reading/writing is constant time operation i.e. Big O(1), so we will use 2 famous data structures:
1. Map for constant lookup.
2. Double linked list for constant-time updates to cache collection.

Steps are as below: [Note this is a very basic idea for the implemenation]

  1. Define a custom implementation for a Node [ key, value, next, prev], remember we are using Double linked list for this purpose to get hold off prev and next pointers in constant time for updates.
  2. Define an LRUCache class and write the below common contracts:
    1. put (key, value)
    2  get (key)
  3. For Put API, Do the following:
    Any time an item is written to cache, We will check for the following:
    1. Ensure List has space, if not clean up by removing Tail node.
    2. If HEAD not exist, then add it on Head and Tail of the list
    3. Else Update HEAD => prev To this new node and make this new node HEAD
    4. Add the key mapping to our Map table for lookup
    5. Increment the length counter
  4. For Get API, Do the following:
    1. Look up the Key in Map table.
    2. Remove the key from List(update both prev/next references, remove from MAP table)
    3. Add it back to list (use PUT API)
    4. return the node.


That’s it for a basic implementation of the LRU map. There are tons of other optimization we can add to this above approach like making it time-based(TTL) i.e auto removing nodes if they cross the TTL on them etc.

Here is the implementation using Javascript example, I have also posted this in Github.

class Node {
constructor(key, value, next, prev) {
this.key = key;
this.value = value; = next ? next : null
this.prev = prev ? prev : null

class LruCache {

constructor(limit = 5) {
this.limit = limit; // default limit is 5
this.head = null;
this.tail = null
this.size = 0;
this.lookUpTable = {}

ensureCapacity() {
if(this.size === this.limit) {

makeSpace() {
const node = this.lookUpTable[this.tail.key];
if(node) {

removeKey(key) {
const node = this.lookUpTable[key];
if(!node) {
console.log(“Remove :: no node found”);

// e.g
// 1 2 3 4 5 6
// key = 4

// if prev of current node not null
// update 3 to point to 5 instead of 4
if(node.prev) { =;

// if next of current node not null
// update 5 to point back to 3 instead of 4
if( { = node.prev;

delete this.lookUpTable[key];

put(key, value) {
const node = new Node(key, value);
if(!this.head) {
this.head = node
this.tail = this.head;
} else {
// we need to add this to head = this.head;
this.head.prev = node;
this.head = node;

this.lookUpTable[key] = node;

get (key) {
const node = this.lookUpTable[key];
if (!node) {
console.log(“No key found.”)
return null;


return node;

peek() {
if(!this.head) {
console.log(“Empty cache”);

return this.lookUpTable[this.head.key];

clear() {
this.size =0;
this.lookUpTable = {}
this.head == null
this.tail = null;

log() {
let node = this.head;
while(node) {
const prev = node.prev;
const next =;
let logPrevKey = “.”
let logNextKey = “.”
if(prev) {
logPrevKey = prev.key;
if(next) {
logNextKey = next.key;
console.log(“[“+logPrevKey+ “]<- [” + node.key +”]” + ” ->[“+ logNextKey+”]”);
node =;

let cache = new LruCache(4);
cache.put(‘1’, 7777);
cache.put(‘2’, 9999);
cache.put(‘3’, 8888);

// should print 3
// do a lookup for 2
// should print 2

console.log(“#############Reading a key”)
console.log(“#############Cache Updated”)


Hope this helps. If you like please leave a comment, it will motivate me to improve.




Just keep goin..

Hello Readers,

I came across a very interesting question on Quora, and by reading the answer, I couldn’t resist myself to share with you all. Hope you all like it.



  1. var job = false;// may this come true
  2. cash = true;
  3. passionate = true;
  4. knowledgable = false;
  6. var action = function(){
  7. if (job) { // found a job?
  8. console.log(“Phew. That was close.”);
  9. return;
  10. }
  11. while (!job) {
  12. switch(true) {
  13. case (passionate && knowledgable && cash):
  14. console.log(“Meanwhile, consider contracting.”);
  15. break;
  16. case (!passionate && !knowledgable):
  17. console.log(“Do you want to explore other career options?”);
  18. break;
  19. case (!cash): // running out of savings
  20. console.log(“Find a dev job quickly.”);
  21. break;
  22. case (!passionate):
  23. console.log(“You are probably burnt out. Take a breather!”);
  24. //to become …
  25. passionate = true;
  26. action(); // recursive
  27. break;
  28. case (!knowledgable):
  29. console.log(“Learn as you go.”);
  30. //to become …
  31. knowledgable = true;
  32. action(); // recursive
  33. break;
  34. default:
  35. console.log(“Don’t give up!”);
  36. }
  37. return; // end
  38. }
  39. }
  41. action();

Angular JS in some Plain English..

If you are on this page, I am sure you have got an idea about how excellent the Angular JS framework is especially when it comes to comparing with the old legacy MVC frameworks, And also, the ease it brings to developers to develop loosely coupled testable components on the client-side.

For newbies, the obvious questions come is “Where to start?”

Frankly speaking, I have been gone through with this myself, being a backend developer for almost 9+ years now, It took me a while to realize the things which Angular JS brought on the table e.g controllers, services, directives, two-way data binding, scopes dependency injections, routing, etc.

Question for me was not about, What a controllers is? or What a Service or Directive is?

The main question on my mind was, HOW ON EARTH Angular is doing that smartly, and how these concepts are applied on the client-side to grasp away the MVC flavor from the popular MVC based backend frameworks.  As I kept reading and trying various things, It helped me understand the core functioning of Angular, In this Post, I am going to explain a few of those terms in pretty plain English.

So here goes the Angular JS Glossary in some pretty plain English.

What is Data Binding?

In actual computer general terms, it’s a process that basically provides a way to create a read/write link on the elements that are bound to the data. So in data binding, whenever the outer representation of the data changes, it also automatically changes the underlying data e.g on HTML page, The “InputBox” value and “Name” attribute(underlying data) of the “InputBox” are bound together, It means if user changes the value of “InputBox” with some input, The DOM controller updates that “Name” attribute variable on the DOM tree and if via some DOM function, if we change the “Name” attribute variable with some new value, It will change the display value  of the “InputBox“(outer representation) as well.

In the context of web programming, we might have done using javascript frameworks like jquery/prototypejs

$(‘p.someClass’).text(“New text”)

Here basically, We have asked the jquery to find the element with a class name “someClass” and change the inner value of that element to the “New Text”.

Now assume, If this “p” tag doesn’t have any class name, in that case, It would be very hard to traceback the behavior of this routine especially when it is somewhere in the bottom of a big function.  

So, This is where Angular brings something interesting (declarative programming and data binding),  we declare binding explicitly on elements, and it makes it very easier to see how the particular element will be affected by our code. It makes code understanding very easier.

What is a Controller?

A controller is basically responsible for managing the objects (views), events etc.

Now the question is what kinds of objects?
For example, Let’s think of a “Student”, a controller doesn’t know what a student name is, or which dept it belongs to or which course it is taking currently. All it knows, From where to get the name, dept or current course information and how to pass it to the view to display on the screen, also, it provides functions which we can attach to the events e.g onmousedown.

What is a Scope?

As we know so far that Angularjs is consist of below components e,g.

View (HTML
Model (Data Model object i.e data for the view)
Controller JS function which controls setter/getters/remove/controls the data.

so in this context, the 
$scope is a model object.

Now the next question comes is, What is a Rootscope?
All applications have a $rootScope which is the scope created on the HTML element that contains the ng-app directive.
e.g. <body ng-app=”myapp” >

What is a Directive/Custom Directive?

A directive is a plain custom HTML attributes/tags that angular knows what to do with.

When we use directives on the HTML page and when the HTML page renders, The browser doesn’t take any action because it has no metadata about those custom tags/attributes but Angular knows how to renders those elements into the HTML view, Its like browser ignores and Angular use that, it’s as simple as that.

Having a custom directive allows us to enforce the reusability of the code, as each custom directive is backed up by some HTML/Inline template (HTML Contents).
The following advantages come with the usage directives:

  1. Code reusability: Using directives across multiple views.
  2. Easy maintenance: As the code is shared, any future modification is easy to handle.

few examples:
core custom directives: ng-app, ng-controller, ng-bind, ng-click etc
custom application specific could be any name: myapp-checkbox, myapp-display etc

What is a Service?

As we read about the role of the controller above i.e which gets the data, access the scope and passes it to the view.
So the question is from where the controller is getting the data, This is where “
Services” comes into the picture, “Services” in angular acts like a layer which provide/resolve data request. There are some different flavors (recipes) of Services in Angular context e.g constant, value, factory, service. Each recipe has its own way of providing the data.

What is a Dependency Injection?

Dependency is a weak relationship where one object requires another object to perform some task. A dependency is an object that can be used (a service) and an injection is the passing of a dependency to a dependent object (a client) that would use it (wiki).

As a real-world example, When I was a kid, my parents were my DI framework, I mean whenever “I need something to drink with my food,” and then they will make sure I have something ready whenever “I sit down to eat :)”. I couldn’t think of any other example to demonstrate the outstanding work DI framework does in real-time applications. To conclude the Dependency Injection is a practice where objects are designed in a manner where they receive instances of the objects from other pieces of code, instead of constructing them internally. And it makes testing (junits) your code very easier.. trust me when I say “very easier..”

I hope this post clears your doubts if any and motivates you to start your journey on Angular. Suggestions/comments are most welcome to improve this post content.

Happy Learning 🙂


Angular Directives

I am sure if you are on this page, you must have already got an idea of how good Angular framework is.  This is my first post on Angular topic and I am trying for many in coming few days :), Lets start…

Angular provides many directive which are very helpful whenever it comes to manipulate DOM content tree, event routing, data binding etc. The framework contains a set of built-in directives which offers very helpful functionality to the applications. AngularJS also let us define our own custom directives. AngularJS directives are extended HTML attributes with the prefix “ng-”.

In this post I will talk about creating simple custom directive and how to read value from them or read from external template. Remember this is a very little overview of the functionality Angular directive provides but it will give some insights directives and their usage.

Step 1: Import the required Angular JS file in the HTML File.

<!DOCTYPE html>

Step 2: Define the NG App (Angular App), Along with I am also initializing  one array with some dummy values for our example.

<body ng-app=”myApp” ng-init=”msgs=[‘hello’,’hi’,’its’,’me’]”>

Step 3:   Define our Directives, you can name them anything meaningful, Fo this post I am going with the below name.

<!– new directive using external template, very useful for code reusability.–>
<test-directive> </test-directive>
<!– another directive, in page scope–>

Step 4: Define the Angular App.

var app = angular.module(“myApp”, []);

Step 5: Define our Custom Directives.

We define directive using .directive function, which takes the directive name and returns its corresponding function.

In this directive, I am using an external html template to renders the dom tree. Look at the “templateUrl” field which takes the path of html resides in same location.

app.directive(“testDirective”, function() {

return {

restrict :  ‘E’,

   templateUrl : ‘msg.tpl..html’



Contents of “msg.tpl..html

<p ng-repeat=”msg in msgs”>{{msg}}</p>

This is the another example of Directive, Here I am reading the value associated with the directive, weather it’s an tag or attribute value.

app.directive(“notify”, function(){

return function(scope, elem, attr){

alert(elem.html() + ” Tag Value”); //reads the value from Tag
OR if tag is restricted to ‘A’, then use the the below.
alert(attr.notify + ” attribute Value”); //reads the value from Tag attribute




Important to Know:


We can easily restrict  directives to tightly get invoked under some of  the methods.
The legal restrict values are:

  • C for Class
  • E for Element name
  • M for Comment
  • A for Attribute

Default values are ‘E’ and ‘A’, It means we can use the directive as element(Tag) name or as an attribute name.

Well, that’s it.

I hope the post make sense to you, I have just started working on using Angular with main focus on Rest Side Development, But I will make sure to post some interesting stuff coming my way while integrating both.

Happy Learning 🙂


Bubble Sort

It’s really been a very long time since I had wrote something, So many things were going which were kind of keeping me very busy, But I finally managed to get some time.. yay!!! yepeee!!, So to continue my journey towards CS algorithms,  I had tried the Bubble Sort with single loop.

Steps are like:
For any given Array:
Take the first two elements and move the largest to the right, and keep doing that unless the largest reached at the position where either its the last position of array or the the position where its right is already the largest and then again repeat and do until all the largest values moves to the right side of array.

Here is the example: Your inputs are highly appreciated 🙂

import java.util.Arrays;

import java.util.Random;

public class BubbleSortV1 {

public static void main(String[] args) {

int[] arr = fillArray();

System.out.println(“Unsorted Array :: “ + Arrays.toString(arr));


System.out.println(“Sorted Array :: “ + Arrays.toString(arr));



private static void verifyArray(int[] arr) {

booleans = true;

for (int i = 0; i < 99; i++) {

if (arr[i] > arr[i + 1]) {

System.out.println(“not sorted…”);

s = false;




if (s) {

System.out.println(“all sorted;”);



static int[] fillArray() {

int[] arr = new int[100];

Random r = new Random();

for (int i = 0; i < 100; i++) {

arr[i] = r.nextInt(500);




// read from left to right and

// move the largest item to the right

// that way all large would be on right side and small on left side

static void bubbleSort(int[] arr) {

// store the last unsorted index

int sortedPartIndex = arr.length;

// first bucket

int leftBucketIndex = 0;

// second bucket

int rightBucketIndex = 1;

// keep running until sorted index reaches 0 (right to left)

while (sortedPartIndex > 0) {

if (arr[leftBucketIndex] > arr[rightBucketIndex]) {

int tempBucket = arr[rightBucketIndex];

arr[rightBucketIndex] = arr[leftBucketIndex];

arr[leftBucketIndex] = tempBucket;




if (rightBucketIndex >= sortedPartIndex) {

// decrement the sorted part index

sortedPartIndex = sortedPartIndex – 1;

// reste the left and right bucket index to default, to start

// over

leftBucketIndex = 0;

rightBucketIndex = 1;





Random Shuffle of Array

Example of how to do a random shuffle of any Given Array. This example is based on a very famous shuffle algorithm knows as Fisher Yates Shuffle. Could be useful to implement in Poker Game to shuffle cards in Java.

Main Steps are:

1. loop from n to 1

2. generate the random index number k such that  0 <= k <= the length of array

3. swap the values between the random index and current iteration index

See below link for more details on this.

private static int[] shuffle(int[] a) {

Random rand = new Random();

for (int lc = a.length – 1; lc > 0; lc–) {

    int shuffleIdx = rand.nextInt(lc + 1);

    int v = a[shuffleIdx];

   a[shuffleIdx] = a[lc];

   a[lc] = v;


return a;