DEV Community: Lizandro J. Ramírez

O(n*m) staircase with N steps

Lizandro J. Ramírez — Mon, 21 Sep 2020 21:34:20 +0000

Description:

This problem was asked by Amazon.

There exists a staircase with N steps, and you can climb up either 1 or 2 steps at a time. Given N, write a function that returns the number of unique ways you can climb the staircase. The order of the steps matters.

Example:

For example, if N is 4, then there are 5 unique ways:

1, 1, 1, 1
2, 1, 1
1, 2, 1
1, 1, 2
2, 2

Fibonacci:

N = [0, 1, 2, 3, 4, 5, 6]

Output Ways = [1, 1, 2, 3, 5, 8, 13]

Fibonacci in the output.

Extra:

What if, instead of being able to climb 1 or 2 steps at a time, you could climb any number from a set of positive integers X? For example, if X = [1, 3, 5], you could climb 1, 3, or 5 steps at a time.

Solution in JS:

O(n * m)
n --> staircase steps ( N )
m --> valid climb up steps ( X.length )


let staircase = (n, X) => {

    // Steps climb up
    let setX = new Set(X)

    // Positions arrays step staircase
    // Included  0  
    let cache = Array(n + 1).fill(0);

    // The position 0 is always 1 way.
    cache[0] = 1;


    for (let i = 0; i <= n; ++i) {

        let temp = 0;

        // Valid Steps add
        for (let x of X) {
            if (i - x > 0) {
                temp += cache[i - x]
            }
        }

        //Update cache.
        cache[i] += temp;
        // position numbers 
        // is included (1) or not (0)
        cache[i] += setX.has(i) ? 1 : 0;
    }

    // The last position in cache have the
    // # of ways.
    return cache.pop();
}

Simple Test:


// Case 1
let X = [1, 2 ];
let n = 4;

console.log(staircase(n, X))

// Case 2 
let X = [1, 3, 5];
let n = 4;

console.log(staircase(n, X))

You can check

code by @difo23

Technique Sliding Windows algorithms

Lizandro J. Ramírez — Sat, 29 Aug 2020 01:13:51 +0000

Coding Problem: Given a string s and a character c, find the distance for all characters in the string to the character c in the string s. You can assume that the character c will appear at least once in the string. This problem was recently asked by Uber.

Example:

For example, given shortest_dist('helloworld', 'l') , you should return [2, 1, 0, 0, 1, 2, 2, 1, 0, 1].

Problem solution:

1) Technique: Sliding Windows (in this case two windows right and left)

Window start and end pointers:

The start and end pointers of the window allow us to go through the chain increasing or decreasing the size of the window itself = end -start, at the beginning the 'end' pointer is the only one that is increasing, the start pointer maintains the position until that the char appears on the scene. With the appearance of char, the pivot is updated, the size of the window and the distances between the pivot and the elements that formed the window up to that moment are updated.

Resize the windows:

We can resize the windows when we find an occurrence of the character in char = 'l'. The index 'end' of the window goes through the entire chain and the start maintains the position until we find a pivot = (char occurrences).

Pivot:

The pivot variables allow us to have a reference point for the last appearance of char = 'l' in the chain, with this pivot we calculate the distance between the end pointer and the last appearance of char.

Big O(N):

In short, I can say that this solution has an O (n * m) where 'n' is the length of 'st' and 'm' are the occurrences of the 'char'. So the inner loop is just to update the 'start' pointer and 'pivot', the more occurrences of the character, the more times this loop will run. Finally, O (n) is the best pattern to describe the behavior of these algorithms. We highlight the fact of using two windows to go through the chain, this reduces to a certain extent the size of the update cycles.

Code:

function shortestDist(st, char) {

    let len = st.length - 1
    let [
        winLeftStart,
        winLeftEnd,
        winRightStart,
        winRightEnd
    ] = [0, 0, len, len];
    let [pivotLeft, pivotRight] = [null, null];
    let dist = [];

    while (winLeftEnd <= len) {

        /** Window Left*/
        if (st[winLeftEnd] === char) {

            pivotLeft = winLeftEnd;
            while (winLeftStart <= pivotLeft) {
                dist[winLeftStart] = pivotLeft - winLeftStart;
                ++winLeftStart;

            }

        } if (!!pivotLeft) {

            if (dist[winLeftEnd]) {
                //End when have first match in dist
                dist[winLeftEnd] =
                    dist[winLeftEnd] < winLeftEnd - pivotLeft ?
                        dist[winLeftEnd] :
                        winLeftEnd - pivotLeft;
                return dist;
            }

            dist[winLeftEnd] = winLeftEnd - pivotLeft;
        }


        /** Window right*/
        if (st[winRightEnd] === char) {

            pivotRight = winRightEnd;
            while (winRightStart >= pivotRight) {

                dist[winRightStart] = winRightStart - pivotRight;
                --winRightStart;
            }

        } else if (!!pivotRight) {

            dist[winRightEnd] = pivotRight - winRightEnd;
        }

        /** Grow Windows*/
        --winRightEnd;
        ++winLeftEnd;
    }
 return [];
}

Simple test:


console.log(shortestDist('helloworld', 'l'))


//        h  e  l  l  o  w  o  r  l  d
// resp. [2, 1, 0, 0, 1, 2, 2, 1, 0, 1]
//        0  1  2  3  4  5  6  7  8  9

You can check

code by @difo23

Technique Two Pointers and memoization.

Lizandro J. Ramírez — Thu, 27 Aug 2020 02:14:55 +0000

Coding Problem: Given an array of numbers and an index i, return the index of the nearest larger number of the number at index i, where distance is measured in array indices.

Example:

For example, given [4, 1, 3, 5, 6] and index 0, you should return 3.

Conditions:

1) If two distances to larger numbers are the equal, then return any one of them.
2) If the array at i doesn't have a nearest larger integer, then return null.

Extra:

Follow-up: If you can preprocess the array, can you do this in constant time?

Problem solution:

1) Technique: Two Pointers(in this case not order array)

const findNearestLarger = (idx, arr) => {

    const value = arr[idx], len = arr.length;

    //Two pointers start with the same value
    let [down, up] = [idx, idx]

    while (up < len || down >= 0) {
              ++up;
            --down;
        //  condition 1
        if (down >= 0 && arr[down] > value) { return down }
        if (up < len && arr[up] > value) { return up }
    }
    // condition 2
    return null;
 }

Extra O(1) with preprocessing and memoization:


function dynamic() {

    let cache = new Map();
    let ant_arr = [];

    const preprocessing= findNearestLarger; 


    return function nearestLarger(idx, arr) {

        // Compare previous arr with new arr received
        if (JSON.stringify(ant_arr) === JSON.stringify(arr)) {
            //Follow-up: If you can preprocess the array,
            // can you do this in constant time?
            return cache.get(idx);

        } else {

            // Update the new matrix for the first time
            ant_arr = arr;
            //Preprocessing
            for (let i = 0; i < ant_arr.length; i++) {
                cache.set(i, preprocessing(i, ant_arr));
            }
            // result
            return cache.get(idx);
        }

    }
}

Simple test:


let arr = [4, 1, 3, 5, 6];
let idx = 0; // you should return 3.

let fastNearestLarger = dynamic();

console.log(fastNearestLarger(0, [4, 1, 3, 5, 6]))

You can check

code by @difo23

Dynamic programming and memoization

Lizandro J. Ramírez — Tue, 25 Aug 2020 03:26:40 +0000

Description:

Dynamic programming technique (memoization) with factorial and Pascal triangle. Dynamic programming is a concept that tends to be quite confusing when it comes to applying it, but memoization (not memorization) is one of the characteristics that identifies it for me. In computing, memoization or memoisation is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Problem:

Implement pascal's triangle with combinations.

Recursive factorial function:

Example:

    factorial de 4! =  4*3*2*1*0!
    0! = 1

Factorial function with memoization and recursive:

function factorialDynamic() {

    let cache = new Map();

    return function factorial(n) {
        if (cache.has(n)) {
            return cache.get(n)
        } else {
            if (n <= 1) return 1;
            cache.set(n, n * factorial(n - 1));
            return cache.get(n);

    }

}
const factorial = factorialDynamic();

Combinatorial function:

Example:

    Function: (P Q) = P! / (Q!-(P-Q)!)

function combinatorial(p, q) {
    return (factorial(p) / (factorial(q) * factorial(p - q)));
}

Pascal triangle function:

Example:

Combinatorial:

fila          (p q)
0             (0 0)
1           (1 0) (1 1)
2        (2 0) (2 1) (2 2)
3     (3 0) (3 1) (3 2) (3 3)

Row function:

function row(p) {

    let row = [];

    for (let q = 0; q <= p; ++q) {
        row.push(combinatorial(p, q));
    }
    return row;

}

Triangle function (main):

function trianglePascal(rows) {

    let triangle = [];

    for (let p = 0; p < rows; ++p) {
        triangle.push(row(p))
    }
    return triangle;
}

Print funtion (test result):

function print(triangle) {

    for (let row of triangle) {
        console.log(row);
    }
}

print(trianglePascal(6));


1              [ 1 ]
2             [ 1, 1 ]
3           [ 1, 2, 1 ]
4         [ 1, 3, 3, 1 ]
5       [ 1, 4, 6, 4, 1 ]
6     [ 1, 5, 10, 10, 5, 1 ]

You can check code by @difo23