Forem: Bvnkumar

LRU (Least Recently Used) Cache Data Structure

Bvnkumar — Tue, 22 Oct 2024 04:01:27 +0000

LRU (Least Recently Used) Cache is a type of cache that evicts the least recently accessed item when the cache exceeds its capacity. It's useful in scenarios where memory is limited, and you want to cache only the most frequently accessed data.

In JavaScript, an LRU Cache can be implemented using a combination of a Map (for fast lookups and maintaining insertion order) and a Doubly Linked List (for efficient insertions and deletions at both ends). However, for simplicity, we'll use a Map in the following implementation.

Here’s a JavaScript implementation of an LRU Cache:

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map(); // Using Map to maintain key-value pairs
    }
    // Get the value from the cache
    get(key) {
        if (!this.cache.has(key)) {
            return -1; // If the key is not found, return -1
        }

        // Key is found, move the key to the most recent position
        const value = this.cache.get(key);
        this.cache.delete(key); // Remove the old entry
        this.cache.set(key, value); // Reinsert to update its position (most recently used)

        return value;
    }

    // Add or update the value in the cache
    put(key, value) {
        if (this.cache.has(key)) {
            // If the key already exists, remove it to update its position
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // If the cache is at capacity, delete the least recently used item
            const leastRecentlyUsedKey = this.cache.keys().next().value;
            this.cache.delete(leastRecentlyUsedKey);
        }

        // Insert the new key-value pair (most recent)
        this.cache.set(key, value);
    }
}

Explanation:
Constructor: The LRUCache class is initialized with a given capacity, and it uses a Map to store the cached key-value pairs. The Map keeps track of the insertion order, which helps identify the least recently used (LRU) item.

get(key):

If the key exists in the cache, the method returns its value and moves the key to the most recent position by first deleting the key and then reinserting it.
If the key doesn't exist, it returns -1.

put(key, value):

If the key already exists in the cache, it removes the key and reinserts it (updating its position as the most recently used).
If the cache reaches its capacity, it removes the least recently used key (the first one in the Map).
Finally, the new key-value pair is added to the cache.

Usage Example:

const lruCache = new LRUCache(3); // Cache with a capacity of 3

lruCache.put(1, 'one');   // Add key 1
lruCache.put(2, 'two');   // Add key 2
lruCache.put(3, 'three'); // Add key 3

console.log(lruCache.get(1)); // Output: 'one' (key 1 becomes the most recently used)

lruCache.put(4, 'four'); // Cache is full, so it evicts key 2 (least recently used)

console.log(lruCache.get(2)); // Output: -1 (key 2 has been evicted)
console.log(lruCache.get(3)); // Output: 'three' (key 3 is still in the cache)
console.log(lruCache.get(4)); // Output: 'four' (key 4 is in the cache)

Observer Design Pattern using Javascript

Bvnkumar — Mon, 27 Mar 2023 23:27:29 +0000

Design patterns are used to solve the specific problems in the software. Today we will be discussed about Observer Pattern in javascript.

Observer pattern is a software design pattern in which an object, called subject, maintains a list of its dependencies called observers and notify them automatically of any state changes.

For Example, In react if state changes then components will re-render accordingly. this process is similar to observer pattern functionality.

Below is the sample program for observer pattern.


function Subject(){
  this.obeservers=[];
}

Subject.prototype={
  add:function(fn){
    this.obeservers.push(fn)
  },
  remove:function(fn){
    this.obeservers=this.obeservers.filter(fun=>f!=fn)
  },
  notify:function(){
    this.obeservers.forEach(fun=>{
      fun.call()
    })
  }
}
function observer1(){
  console.log("in the observer1")
}
function observer2(){
  console.log("in the observer2")
}
const subject=new Subject();
subject.add(observer1);
subject.add(observer2);
subject.notify() // It will loop through all the observers.

In the above example, we have created the Subject constructor function. And it has observers list property, add, delete and notify methods.

Observers: It will have no.of observers.
Add: It will add observers(functions) to that list.
Remove: this method will remove the function from the list based on its argument.
Notify: this will notify all the observers in the list.

Comments and suggestions are always welcome.

Javascript Factory Design Pattern

Bvnkumar — Mon, 20 Mar 2023 20:58:11 +0000

Design patterns are templates or solutions for common software development problems.

Design patterns are divided into three categories.

Behavioral
Creational
Structural

The factory pattern is a creational design pattern that provides a generic interface for creating objects.

EX:-

function Developer(name , experience) {
    this.name = name;
    this.type = "Developer";
    this.experience = experience;
}
function Tester(name, experience) {
    this.name = name;
    this.type = "Tester";
    this.experience = experience;
}
function EmployeeFactory() {
    this.create = (name, type) => {
        switch (type) {
            case 1:
                return new Developer(name,4);
                break;
            case 2:
                return new Tester(name,6);
                break;
        }
    }
}

function say() {
    console.log("i am " + this.name + " i am a " + this.type +" and having a "+ this.experience +"years of experience ");
}

let employees = [];
const employeeFactory = new EmployeeFactory();
employees.push(employeeFactory.create("Sam", 1));
employees.forEach((employee) => {
    say.call(employee);
});

As you can see, we have created developer and Tester objects with their names. Using this pattern you could create as many objects you require each with their own name and experience.

Longest string without repeating characters in javaascript

Bvnkumar — Tue, 07 Jun 2022 00:52:01 +0000

 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
  let map = new Map();
    if (!s.length) {
        return null
    }
    for (let i = 0; i < s.length; i++) {
        let count = 0;
        let checkString = s.substring(0, i + 1)
        let start = 0;
        while (s.substring(start, s.length - 1).indexOf(checkString) > -1) {
            count++;
            if (map.has(checkString)) {
                let existedCount = map.get(checkString);
                map.set(checkString, existedCount + 1)
                existedCount = 0;
            } else {
                map.set(checkString, count)
            }
            start++;
        }
    }
    if (map.size) {
        let keys = Array.from(map.keys());
        return keys.reduce((a, b) => map.get(a) > map.get(b) ? map.get(a) : map.get(b))
    }
};
//console.log("Higest", lengthOfLongestSubstring('abcabcbb'))
//console.log("map", map)`

Any suggestions or comments are welcome.

Print left view of binary tree

Bvnkumar — Tue, 24 May 2022 02:40:50 +0000

class Node{
  constructor(data,left,right){
    this.data=data;
    this.left=left;
    this.right=right;
  }
}

const tree=new Node(10);
tree.left=new Node(1)
tree.right=new Node(3)
tree.left.left=new Node(4)
tree.left.right=new Node(5)
tree.right.right=new Node(6)
tree.right.left=new Node(2);
tree.right.right.left=new Node(7)
tree.left.right.left=new Node(8)
tree.left.right.right=new Node(9)
tree.left.right.left.left=new Node(10);

let max_level=0;
function leftsideView(node,level){
  if(node==null){
    return null;
  }
  if(max_level<level){
    console.log(node.data)
    max_level=level;
  }
  leftsideView(node.left,level+1);
  leftsideView(node.right,level+1);
}
leftsideView(tree,1)

Binary search algorithm implementation in JavaScript

Bvnkumar — Fri, 13 May 2022 03:01:31 +0000

Mastering Binary Search: The Efficient Way to Find Elements in a Sorted Array

Binary Search is a powerful algorithm based on the divide-and-conquer approach, allowing us to search elements efficiently in a sorted array. Compared to a linear search, which has a time complexity of O(n), binary search significantly reduces the search time to O(log n) by halving the search space at each step.

Key Features:

Works only on sorted arrays.
Much faster than linear search due to its logarithmic time complexity.
Splits the search space in half with each iteration, narrowing down the target efficiently.

function binarySearch(list, item, left, right) {
    let mid = Math.floor((left + right) / 2)
    if (left > right) {
        return false
    }

    // If the midpoint is the item we're looking for, return true.
    if (list[mid] == item) {
        return true;
    } else if (item < list[mid]) {

    // If the item is smaller than the midpoint, search the left half.
      return binarySearch(list, item, left, mid - 1)

    } else {

    // Otherwise, search the right half
        return binarySearch(list, item, mid + 1, right)
    }
}

let list=[1,2,3,5,6,7,8,9];
console.log(binarySearch(list,10,0,list.length-1))

Why is Binary Search Fast?

Because it halves the search space with each comparison. For an array of 1000 elements, instead of checking each one, binary search only takes about 10 checks (log₂(1000) ≈ 10), making it much faster for large datasets.

Example Walkthrough:
Let's say you want to search for the number 5 in the array [1, 2, 3, 5, 6, 7, 8, 9].

Step 1: Start with left = 0, right = 7. Calculate mid = (0 + 7) / 2 = 3.
list[mid] is 5, which is our target, so return true.
This simple, efficient process allows us to find the element quickly.

Feel free to drop your thoughts or suggestions on how to improve the algorithm further! 👇

Javascript Binary heap data structure

Bvnkumar — Mon, 09 May 2022 00:58:51 +0000

Binary heap:- A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

let MinHeap = function() {
    let head = [null];
    this.insert = function(element) {
        head.push(element);
        if (head.length > 2) {
            let idx = head.length - 1;
            while (head[idx] < head[Math.floor(idx / 2)]) {
                if (idx >= 1) {
                    [head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
                    if (Math.floor(idx / 2) > 1) {
                        idx = Math.floor(idx / 2);
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
let minHeap = new MinHeap();
minHeap.insert(2)
minHeap.insert(1)
minHeap.insert(3)
minHeap.insert(4)

let MaxHeap = function() {
    let head = [null];
    this.insert = function(element) {
        head.push(element);
        if (head.length > 2) {
            let idx = head.length - 1;
            while (head[idx] > head[Math.floor(idx / 2)]) {
                if (idx >= 1) {
                    [head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
                    if (Math.floor(idx / 2) > 1) {
                        idx = Math.floor(idx / 2);
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
let maxHeap = new MaxHeap();
maxHeap.insert(2)
maxHeap.insert(1)
maxHeap.insert(3)
maxHeap.insert(4)

Any comments or suggestions are welcome.

Javascript Linked List data structure

Bvnkumar — Tue, 26 Apr 2022 03:22:55 +0000

LinkedList:

A linked list is a linear data structure similar to an array. However, unlike arrays, elements are not stored in a particular memory location or index. Rather each element is a separate object that contains a pointer or a link to the next object in that list.

Advantages:

Nodes can easily be added or removed from a linked list without re-organizing the entire data structure.

Disadvantages:

Search operations are slow in linked list over arrays, random access of data element is not allowed. Nodes are accessed sequentially from first node.
It uses more memory than arrays because of storage of the pointer.

Internal Design of linked list

function LinkedList() {
    let length = 0;
    let head = null;
    const Node = function(element) {
        this.element = element;
        this.next = null;
    }
    this.size = function() {
        return length;
    }
    this.head = function() {
        return head;
    }
    this.add = function(element) {
        let node = new Node(element);
        if (head == null) {
            head = node;
        } else {
            let currentNode = head;
            while (currentNode.next) {
                currentNode = currentNode.next;
            }
            currentNode.next = node;
        }
        length++
    }

    this.remove = function(element) {
        let currentNode = head;
        let previousNode;
        if (currentNode.element == element) {
            head = currentNode.next;
        } else {
            while (currentNode.element !== element) {
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
            previousNode.next = currentNode.next;
        }
        length--;
    }
    this.isEmpty = function() {
        return length == 0;
    }
    this.indexOf = function(element) {
        let currentNode = head;
        let index = -1;
        while (currentNode) {
            index++;
            if (currentNode.element == element) {
                return index;
            }
            currentNode = currentNode.next;
        }
        return -1;
    }
    this.elementAt = function(index) {
        let currentNode = head;
        let count = 0;
        while (count < index) {
            count++
            currentNode = currentNode.next;
        }
        return currentNode.element;
    }
}
var link = new LinkedList();
link.add("hello");
link.add("hello")
console.log(link)
console.log("elementAt", link.elementAt(0))
console.log("indexOf", link.indexOf("bye"))
link.remove("hello")
link.remove("hello")
console.log("isEmpty", link.isEmpty())
console.log("length", link.size())

Any comments or suggestions are welcome.

Javascript Binary Tree data structure

Bvnkumar — Wed, 20 Apr 2022 04:01:09 +0000

Binary Tree:
A binary tree is a data structure consisting of a set of linked nodes that represent a hierarchical tree structure. Each node is linked to others via parent child relationship.
Any given node can have at most two children(left&right).

Internal structure of binary tree:

class Node {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BST {
    constructor() {
        this.root = null;
    }
    add(data) {
        const node = this.root;
        if (node == null) {
            this.root = new Node(data);
        } else {
            const searchTree = function(data) {
                if (data < node.data) {
                    if (node.left == null) {
                        node.left = new Node(data);
                        return;
                    } else if (node.left != null) {
                        return searchTree(node.left)
                    }
                } else if (data > node.data) {
                    if (node.right == null) {
                        node.right = new Node(data)
                        return;
                    } else if (node.right != null) {
                        return searchTree(node.right)
                    }
                } else {
                    return null;
                }
            }
            return searchTree(data)
        }
    }
    findMax() {
        let current = this.root;
        while (current.right != null) {
            current = current.right;
        }
        return current.data;
    }
    findMin() {
        let current = this.root;
        while (current.left != null) {
            current = current.left
        }
        return current.data;
    }
    find(data) {
        let current = this.root;
        while (current.data != null) {
            if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }
    isPresent(data) {
        let current = this.root;
        while (current) {
            if (data == current.data) {
                return true
            }
            if (data < current.data) {
                current = current.left;
            } else {
                current = current.right;
            }
        }
        return false;
    }
}

const bst = new BST();
bst.add(1);
bst.add(2);
bst.add(3);
console.log(bst.findMin());
console.log(bst.findMax());
console.log(bst.find(1));
console.log(bst.isPresent(1));

Any comments or suggestions are welcome.

Javascript Queue data structure

Bvnkumar — Mon, 18 Apr 2022 18:23:18 +0000

QUEUE:
Queue is also one type of data structure and works like a stack but it follows a first in first out(FIFO) order.
Example: When you are in a line to pay a bill at the counter, we should follow the sequence like first in first out, queue also works same.

Internal design of queue:

const Queue = function() {
    let collections = [];
    this.add = function(item) {
        return collections.push(item);
    }
    this.size = function() {
        return collections.length;
    }
    this.isEmpty = function() {
        retun(collections.length == 0)
    }
    this.enqueue = function(item) {
        return collections.push(item)
    }
    this.dequeue = function(item) {
        return collections.shift();
    }
    this.front = function() {
        return collections[0];
    }
}

let queue = new Queue();
console.log(queue.size())
queue.enqueue("1");
queue.enqueue("2");
console.log(queue.size())
console.log(queue.front());
queue.dequeue();
console.log(queue.size())

Any comments or suggestions are welcome.

Javascript Set data structure

Bvnkumar — Sun, 17 Apr 2022 13:40:37 +0000

Set: Set data structure allow to add data to a container.

This custom Set implementation in JavaScript uses an array (collection[]) to store unique values, similar to the built-in Set object. It provides methods to add, remove, check, and retrieve the size of the collection while ensuring each element is unique.

Methods:

size(): Returns the number of elements in the set.
has(item): Checks if the set contains a specific item.
add(item): Adds a new item to the set if it doesn’t already exist.
delete(item): Removes an item from the set if it exists.
clear(): Removes all items from the set.
values(): Returns all the items in the set.

Here is an example of set internal implementation.

const Set=function(){
  let collection=[];
  this.size=function(){
    return collection.length;
  }
  this.has=function(item){
   return collection.indexOf(item)!==-1
  }
  this.add=function(item){
    if(!this.has(item)){
      collection.push(item)
      return true;
    }
    return false;
  }
  this.delete=function(item){
    if(!this.has(item)){
      return false;
    }else{
      let index=collection.indexOf(item);
      collection.splice(index,1);
      return true;
    }
  }
  this.clear=function(){
    collection=[];
  }
  this.values=function(){
    return collection;
  }
}
let set=new Set();
console.log(set.size());
console.log(set.add(1));
console.log(set.add(2));
console.log(set.size());
console.log(set.delete(2));
console.log(set.delete(2));
console.log(set.size());

Time Complexity:

size(): O(1) - Simply returns the length of the array.
has(item): O(n) - The indexOf() method is used, which performs a linear search through the array.
add(item): O(n) - Before adding, it calls has(item) which is O(n), and if the item doesn’t exist, push() is O(1).
delete(item): O(n) - It uses indexOf() to find the index of the item, which is O(n), and then splice() to remove it, which is also O(n).
clear(): O(1) - Just resets the array to an empty array.
values(): O(1) - Returns the reference to the array. > Any comments or suggestions are welcome.

Javascript Stack Data Structure.

Bvnkumar — Sat, 16 Apr 2022 03:45:00 +0000

Understanding JavaScript Call Stack and Stack Data Structure
JavaScript is a single-threaded language, meaning it uses a single call stack to manage the execution context of functions.

Whenever a function is called, the JavaScript engine creates a global execution context and pushes it onto the call stack. When a new function is invoked, a function-specific execution context is added on top of the global one.
The call stack follows the Last In, First Out (LIFO) order, meaning the most recent function added will be the first to be removed once it completes execution.
Here's a simple example of a stack data structure implemented in JavaScript. You can execute this code in any JavaScript environment and observe the console output:

class Stack {
  constructor() {
    this.count = 0;
    this.storage = {};
  }

  size() {
    return this.count;
  }

  push(item) {
    this.storage[this.count] = item;
    this.count++;
  }

  peek() {
    return this.isEmpty() ? undefined : this.storage[this.count - 1];
  }

  pop() {
    if (this.isEmpty()) return undefined;
    this.count--;
    const result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }

  isEmpty() {
    return this.count === 0;
  }
}

const stack = new Stack();
console.log(stack.size()); // 0
stack.push(1);
stack.push(2);
console.log(stack.peek()); // 2
console.log(stack.pop());  // 2
console.log(stack.size()); // 1

//Feel free to try it out and check the results!

> Breakdown of the time complexities:

Push (Adding an item): O(1)
The push operation simply adds an item to the top of the stack, and this happens in constant time, since it involves a direct assignment and increment of a counter.

Pop (Removing the top item): O(1)
Similarly, the pop operation just removes the item from the top of the stack, deletes the reference, and decrements the counter, all of which occur in constant time.

Peek (Retrieving the top item): O(1)
The peek operation only accesses the top item without modifying the stack, so it's also constant time.

Size (Retrieving the stack size): O(1)
Since the size of the stack is stored in a variable and updated with each push or pop, retrieving the size is a constant time operation.

Thus, all the primary operations on a stack—push, pop, peek, and size—have a time complexity of O(1), making the stack a very efficient data structure for managing collections of items where only the top item is of interest.

Any comments or suggestions are welcome