Introduction

Four common algorithms with solutions written in Typescript. This is my starting point working with TypeScript so this project is nothing special. Idea was to write solutions for the algorithm problems, which will be run through commander, when the application is started commander prompt 4 choices. When user chooses one from the list it get executed with the execution time. I hope I will add more in near future but for now it was just a good excercise.

Fibonnaci numbers

About

This is well known algorithm if not the best known because everybody was doing it at least once. Fibonnaci numbers or sequence is a sequence of numbers that is calculated by adding values of two preceding numbers, also known as golden ratio which can be found in nature. We count the sequence starting with the index n = 0 which has value of 0. Next in sequence is n = 1 which has the value of 1. Next in sequence is n = 2 with value 1 . If you ask why , it is simple we add values of previous two and that is 0 + 1 , to be easier for you to understand here is the formula.

Formula for calculating Fibonnaci number is :

F(n) = F(n-2) + F(n-1)

So if we want to calculate Fibonacci number for 3 result will be F(1) + F(2) = 1 + 1 = 2 as we got already Fibonacci for 1 and 2 which is 1 and 1.

Solution

My solution is:

let storedFibNums: any = {};

export const calculateFibonacci = (n: number): number => {
    if (n <= 1) return n;
    if (storedFibNums[n]) {
        return storedFibNums[n]
    }
    storedFibNums[n] = calculateFibonacci(n - 1) + calculateFibonacci(n - 2)
    return storedFibNums[n];
}

Calculate century

About

This is really simple one, if you want it to be simple. The point of the algorithm is that you are provided year and you have to return in which century it belongs. For me easiest solution was to divide year by 100 and then use Math.ceil to get century. Math.ceil is great for this solution because it will round number to greater than or equal to a given number.

Solution

Solution is pretty simple, it took only 2 lines of code.

export const century = (year: number) => {
    const cent = year / 100;a
    return Math.ceil(cent)
}

Palindrome

About

What is Palindrome?

a word, phrase, or sequence that reads the same backwards as forwards, e.g. madam or nurses run. So basically you are given a word and you need to check wheather it is palindrome.

Solution

Solution for this one is also very trivial, you just need to loop through the word from the behind and check if it match with the given word.

export const isPalindrom = (inputString: string): boolean => {
    let palindrom = "";
    for (let i = inputString.length - 1; i >= 0; i--) {
        palindrom += inputString[i];
    }
    if (palindrom === inputString) {
        return true
    }
    return false;
}

First duplicate

About

You are given array of numbers and you have to return first number that is duplicate. Array provided can be of size n so this means that we can have array with million of elements.

Solution

When we measure performance as well, in the million sized array, for loop can be an issue. While can be as well even though it is faster than for loop. Best solution I found is to create Set and loop over array of numbers, check if we have it in Set if not add it. So we will use Set.has() instead of having dual loop and if we have it in set we return it.

export const removeFirstDuplicate = (a: number[]) => {
    const x = new Set<Number>()
    for (const num of a) {
        if (x.has(num)) {
            return num
        } else {
            x.add(num)
        }
    }
    return -1
}

Algorithms are great way for improving your technical skills and the way of thinking, so it is great excercise and way of learning. So I strongly suggest to checkout if you dont already know for this great platforms where you can solve algorithm problems, my personal favorites are Leetcode and Code Signal