DEV Community: Solomon Yunana

Memoization

Solomon Yunana — Fri, 08 Jul 2022 06:52:10 +0000

Introduction

One of the common ways of increasing the efficiency of an algorithm is using the hash, map or dictionary data structure which is a key/value pair data structure. This technique is used to improve the efficiency of recursive algorithms which is called Memoization in dynamic programming.

what is Memoization ?

Memoization is a technique for improving the performance of recursive algorithms. It involves rewriting the recursive algorithm so that as answers to problems are found, they are stored in an array, hash, map or dictionary. Recursive calls can look up results in the array rather than having to recalculate them.

Motivation

Applying this technique into formulas that heavily uses the factorial(n!) of numbers can have a huge performance increase in any algorithm.

Problem

Let's consider a simple factorial equation (x! + y!) / (z! + x!). Where x,y,z are any natural numbers (positive integer) and are not equal to zero. We will solve this equation with and without memoization into consideration.

Solution 1

   let functionCall = 0;
   // factorial function without memoization
   function factorial(n:number){
      functionCall++;
      if(n === 1){
        return 1;
      }

      return n * factorial(n-1);

   }

  // equation solution with factorial function
  const x = 20, y = 15, z = 10
  const result = (factorial(x) + factorial(y)) / (factorial(z) + factorial(x));
  console.log(result);
  console.log(functionCall);

This works well but there is a huge performance issue here because the overall function calls 65 times plus there is always an overhead with recursive operations making them costly.

Solution 2


   // factorial function with memoization

   let functionCall = 0;
   let memo = {};

   function factorial(n:number){

      functionCall++;

      if(n === 1){
        return 1;
      };

      if(memo[n]){
        return memo[n];
      } else {
        memo[n] = n * factorial(n - 1);
        return memo[n];
      }

   }

  // equation solution with memoized factorial function
  const x = 20, y = 15, z = 10
  const result = (factorial(x) + factorial(y)) / (factorial(z) + factorial(x));
  console.log(result);
  console.log(functionCall);

Now this algorithm is efficient because functionCall is now 23 and Why ? because the function calls factorial(x=20) and stores the factorial of all numbers below it in the hash map which looks like this ...

  {
  '2': 2,
  '3': 6,
  '4': 24,
  '5': 120,
  '6': 720,
  '7': 5040,
  '8': 40320,
  '9': 362880,
  '10': 3628800,
  '11': 39916800,
  '12': 479001600,
  '13': 6227020800,
  '14': 87178291200,
  '15': 1307674368000,
  '16': 20922789888000,
  '17': 355687428096000,
  '18': 6402373705728000,
  '19': 121645100408832000,
  '20': 2432902008176640000
}

Now for the other functions in the equation it just looks for the factorial of x,y,z which exist as keys 20, 15 and 10 in the hashmap and returns it instead of recalculating the value again. It doesn't matter the order at which the values passed to the factorial function are called once a value exist on the hash map it doesn't recompute.

Conclusion

Thinking recursively unlocks a world of it own when solving algorithm and improves your thinking capability. By applying memoization we are able to increase the efficiency of the algorithm. Thanks

Implementing array methods on a linked list

Solomon Yunana — Mon, 28 Mar 2022 19:29:17 +0000

Introduction

Having a good understanding of data structure is the key that enables one thinks fast when it comes to solving problems, while lots of tech interviews use it as a roadblock to getting a job I will emphasize it should be a daily practice and routine because it results can not be undermined.To learn more on datastructure i recomend you get the book below,

A common sense to Data structures and algorithm - Jay Wengrow

Moltivation

Curiosity got me thinking, since an array has lots of built-in methods in Javascript and a linked list is an abstract data type in javascript that can be implemented. I decided to implement a linked list that has all the methods of javascript methods. The linked list shines where an array is terrible from the Big O!! guy and seriously none is better than the other but the type of problem at hand determines the champion. I know this will be an unending post if i post all methods of an array in a linked list that's why this post will be divided into different parts to be posted seperately.

Hold on!!! What is a linked list ?

A linked list is a linear collection of data in a non-contiguous manner. This means a linked list is the opposite of an array which is contiguous in design. When it comes to data placement in the computer memory, contiguous means array items must be placed next to each other in memory and the reverse is the case for a linked list.

Linked list

Linked Node

Since linked list is define by a node where one item points us to the next item in the list we will define a class of node using typescript

     class LinkedNode<T> {
        data: T;
        next?: LinkedNode<T>;

        constructor(data: T, next?: LinkedNode<T>){
            this.data = data;
            this.next = next;
         }
     }

Linked List

Now we will define an interface for our linked list


    type CallBack<T> = (item: T, index: number)=> void;

    interface LinkedListProp<T> {
        length: number;
        push: (...data: T[]) => number;
        pop: ()=> LinkedNode<T>;
        printList: ()=> void;
        shift: ()=> LinkedNode<T>;
        unshift: (...data: T[]) => number;
        forEach: (callBack: CallBack<LinkedNode<T>>)=>void;
    }

    class LinkedList<T> implements LinkedListProp<T> {

         private linkedList: LinkedNode<T>;
         public length = 0;

         private isEmpty(): boolean{
           if(!this.linkedList){
             return true;
            }
           return false;
         }

    }

Note the Generic CallBack type alias is for defining the forEach method of an array that we are about to implement.Also notice the isEmpty methode which returns a boolean true | false to tell us if our list is empty or not.

printList Method

we want to be able to print all the list on the terminal but our terminal will print few LinkedNodes and tells us the rests are LinkedNodes so we will stringify our output and format it nicely so that we can see our linked list functions correctly.

public printList(){
 console.log(JSON.stringify(this.linkedList,null,4))
}

pop() Method

We want to be able to remove the last item from an array and return it so we have the following code ...


    pop():LinkedNode<T>{

        if(this.isEmpty()){
            return;
        }

        let removedNode:LinkedNode<T>

        let previousNode: LinkedNode<T>;
        let currentNode = this.linkedList;

        while (currentNode.next){
           previousNode = currentNode;
           currentNode = currentNode.next
        }

        if(!previousNode.next){
            removedNode = this.linkedList;
            this.linkedList = null;
            this.length = 0;
        }else{
            this.length -= 1;
            removedNode = currentNode;
            previousNode.next = null;            
        }
        return removedNode;
   }

push() method

we want to be able to add an item to end of thelinked-list, but note since we want to implement it the same as javascript arrays we want a user to be able to add multiple items to the end of the array by passing desired number of items to the push method, to achieve this we will use rest parameters for our push method.


    push(...data: T[]): number{

        let newNodes: LinkedNode<T>;
        let currentNode: LinkedNode<T>

        data.forEach((nodeData)=> {
         let newNode = new LinkedNode(nodeData);
         if(!newNodes){
             newNodes = newNode;
             currentNode = newNode;
         }else{
             currentNode.next = newNode;
             currentNode = newNode;
         }
        })

        // connect the new nodes to linkedlist
        if(this.isEmpty()){
            this.linkedList = newNodes;
        }else{
            let current = this.linkedList;
            while(current.next){
                current = current.next;
            }

            current.next = newNodes;
        }

        this.length = data.length + this.length;
        return this.length;
    };

Let me explain shortly. The thought process here is if we have two linked-list were the first is our existing linked-list and the second is linked-list containing our new items, we can connect them by having reference to the last item in the first list. So what we do is..

link up all items to be added to the linked list
if the list is empty our new linked list becomes our list
otherwise we grab the last item in our existing linked list and set the next property to point to our new list.

Shift() Method

Opposite to pop() we want to be able to remove an item from the begining of the list, so we have the following code.

    shift(){

       if(this.isEmpty()) return;

       let currentList: LinkedNode<T>;
       let removedNode : LinkedNode<T>;

       currentList = this.linkedList.next;
       this.linkedList.next = null;
       removedNode  = this.linkedList;
       this.linkedList = currentList;

       return removedNode;

     }

This method is simple, all we have to do is

store the reference to the rest of our list except the first.
set our current list to the list which exempts the first one
set the next of the removed node to null
finally we - return the removed node

Unshift() method

Opposite to push() method we will want to be able to add these numerous item to the begining of the array and again rest parameters to the rescue

      unshift(...data: T[]): number{
        let newNodes: LinkedNode<T>;
        let currentNode: LinkedNode<T>
         data.forEach((nodeData)=> {
         let newNode = new LinkedNode(nodeData);
         if(!newNodes){
             newNodes = newNode;
             currentNode = newNode;
         }else{
             currentNode.next = newNode;
             currentNode = newNode;
         }
        })

        if(this.isEmpty()){
            this.linkedList = newNodes;
        }else{

            let current = newNodes;
            while(current.next){
                current = current.next;
            }

            current.next = this.linkedList;
            this.linkedList = newNodes;
        }

        this.length = data.length + this.length;
        return this.length;
     };

Let me explain shortly again. The thought process here is if we have two linked-list were the first is our existing linked-list and the second is linked-list containing our new items, we can connect them by having reference to the last item in the second list. So what we do is...

link up all items to be added to the linked list.
if the list is empty our new linked list becomes our list.
otherwise we grab the last item in our second linked list and set the next property to point to our existing list.

forEach() method

lastly we want to implement the foreach method. this method should allow us iterate through each item in the array using a callBack function that allow us access the item and index. Note i didnt pass the linked list which is suppose to be the last parameter of the callback if we are to implement it same as array


forEach(callback:CallBack<LinkedNode<T>>){

         if(!this.linkedList) return ;

         let linkedList = this.linkedList;

         if(!linkedList.next){
             callback(this.linkedList,0);
         }else{

             let currentList = this.linkedList;
             let previousNode: LinkedNode<T>;
             let recomposeLinkedList: LinkedNode<T>;
             let recomposePrevItem: LinkedNode<T>
             let counter = 0;

             while (currentList.next){
                 currentList = currentList.next;
                 this.linkedList.next = null;
                 previousNode = this.linkedList;
                 callback(previousNode,counter)
                 if(!recomposeLinkedList){
                     recomposeLinkedList = previousNode;
                     recomposePrevItem = previousNode;
                 }else{
                     recomposePrevItem.next = previousNode;
                     recomposePrevItem = previousNode;
                 }

                 this.linkedList = currentList;
                 counter++;


             }

             callback(currentList,counter++);
             recomposePrevItem.next = currentList;
             this.linkedList = recomposeLinkedList;
         }
     }

Let me explain something that can make understanding this easier. We want to access each item in the list, but anytime we are accessing the current item it has bunch of other referenced object. The thought process here is...

Detatch item to be accessed from the list.
pass it to the callback function afterwards attatch it back.
we do this for each item in the array.

For accessing single item in the linked list without reference to bunch of others it is linked, I used a thought process that ..

stores the reference to only the previous item.
then set the next property to null
pass it to the callback function
add the previous node to a variable that recompose the list of accessed items.

But the issue now is our last item will not be read which is the result of the last callback function at the end of the method because our currentList will contain only our last item.

My Linked-List

  let testLinkedList = new LinkedList<number>();
  testLinkedList.push(100,200,300,400,500,600);
  // prints our link list showing how they are linked
  testLinkedList.printList() 

  testLinkedList.pop();
  // prints our link list showing how they are linked and the last item removed
  testLinkedList.printList();

  testLinkedList.unshift(800,900,700);
  // print our link list and show the items inserted at the begining of the linked list
  testLinkedList.printList();

  testLinkedList.unshift();
  // print our link list and show the first item removed from the beginning of the linked list
  testLinkedList.printList();

  testLinkedList.forEach((item,index)=>{
    console.log(item);
  })

Conclusion

There are couple of more efficient ways of doing this. This is my thoughts and i will really appreciate if there are any suggestion.

I know this is a long read. Watch out for part 2

Implementing "groupBy" function on array of object

Solomon Yunana — Mon, 14 Mar 2022 05:56:08 +0000

Moltivation

There is a an array method called groupBy, i checked the description of the method and saw it as a handy method for grouping array of object base on a key that exist on an object of the array.

MDN - groupBy reference

As of the time of this writing, i tried it out on my browser but OOPS!! no luck because it is not supported by any browser, i tried using it with typescript but no luck either, ran it with node(v16.14.0) REPL no luck either,i decided to implement it myself since i have read the description, thus the moltivation !!!!

Problem

Let's say we have have some group of data as array of object

  const inventory = [
    { name: 'asparagus', type: 'vegetables', quantity: 5 },
    { name: 'bananas',  type: 'fruit', quantity: 0 },
    { name: 'goat', type: 'meat', quantity: 23 },
    { name: 'cherries', type: 'fruit', quantity: 5 },
    { name: 'fish', type: 'meat', quantity: 22 }
  ];

using typescript we would define an interface over inventory as

 interface Inventory {
    name: string;
    type: string;
    quantity: number;
  }

Now we want to be able to group inventory base on a key that exist on inventory. typescript will let us do that with ease such that the result looks like this when we decide to group by type on inventory

{
  vegetables: [ 
    { name: 'asparagus', type: 'vegetables', quantity: 5 } ],

  fruit: [
    { name: 'bananas', type: 'fruit', quantity: 0 },
    { name: 'cherries', type: 'fruit', quantity: 5 }
  ],

  meat: [
    { name: 'goat', type: 'meat', quantity: 23 },
    { name: 'fish', type: 'meat', quantity: 22 }
  ]
}

My groupBy function

my solution function now looks like this

function groupBy<T>(collection:T[],key: keyof T){
   const groupedResult =  collection.reduce((previous,current)=>{

   if(!previous[current[key]]){
     previous[current[key]] = [] as T[];
    }

   previous[current[key]].push(current);
          return previous;
   },{} as any); // tried to figure this out, help!!!!!
     return groupedResult
 }

now we can call the inventory in this manner

  console.log(groupBy<Inventory>(inventory,"name"));
  console.log(groupBy<Inventory>(inventory,"quantity"));
  console.log(groupBy<Inventory>(inventory,"type"));

Notice the explicit indication of the generic type Inventory on the groupBy function at function call is for emphasis and not neccessarily needed since typescript will infer the generic type.

Conclusion

This is my implementation of the groupBy function and i have been using it for sometime now and i decided to share, let me know if there is more efficient way of doing this or if there is something i might do to improve the code. This approach is subject to change. Thanks.