Top JavaScript Algorithms

✋ Binary Search Algorithm

Binary search is a faster and more efficient search to find an element in a given sorted Array.

Linear search checks every array index element while a given element does not found. If we have an array of 1 to 16 Like [1,2,3…,16].
So to search number 15, for loop will run 15 times.
With Binary search loop will run only 4 times.

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];

linearSearch = (arr, target) => {
  for (let i = 0; i < arr.length; i++) {
    console.count("linearSearch loop"); // it count how many numbers of this for loop will run.
    if (arr[i] === target) {
      return "Number is found at index - " + i;
    }
  }
  return "Number is not found";
};

***Run program***
linearSearch(arr, 15) >
linearSearch loop: 15 (it runs 15 times)
"Number is found at index - 14"

💡 Binary Search Working:

1. Array should be sorted. Binary search only works for the sorted array.
2. First, find startIndex that is 0 initially means first array index and find endIndex, that is arr.length – 1;
3. Now find middleIndex and that will be – Math.floor((startIndex + endIndex) / 2);
4. If the target element is equal to middleIndex of the array means arr[middleIndex] so our search is done and just returns that middleIndex.
5. If target is greater then arr[middleIndex] element, then we can left 'LEFT PART' of array from middle index and now startIndex will be – startIndex = middleIndex + 1;
6. If target is less then arr[middleIndex] element, then we can left 'RIGHT PART' of array from middle index and now endIndex will be – endIndex = middleIndex – 1;
7. Repeat step 3,4,5,6 in while loop with condition – while (startIndex <= endIndex).

Binary Search works on the concept of divide and conquers policy and that’s why also called the Dividing and Conquering Algorithm.

binarySearch = (arr, target) => {
  let startIndex = 0; 
  let endIndex = arr.length - 1;

  while (startIndex <= endIndex) {
    console.count('binarySearch loop');
    const middleIndex = Math.floor((startIndex + endIndex) / 2);
    if (arr[middleIndex] === target) {
      return 'Number is found at index - ' + middleIndex;
    } else if (target > arr[middleIndex]) {
      startIndex = middleIndex + 1;
    } else if (target < arr[middleIndex]) {
      endIndex = middleIndex - 1;
    }
  }
  return 'Number is not found';
};

***Run program****

binarySearch(arr, 15);
binarySearch loop: 4 (4 times) that is much much faster.
"Number is found at index - 14"

As compared to linear, binary search is much faster with Time Complexity of O(logN) whereas linear search algorithm works in O(N) time complexity.

✋ Palindromes

A Palindrome is a word or a sequence that is the same if readen in a forwarding or backward direction.

Example: Madam

checkPalindrome = (str) => {
  if (str) {
    // first remove spaces and special chars from given string
    const pattern = /[^a-zA-z]+/g; 
    console.time("checkPalindrome runs"); // Log time
    str = str.replace(pattern, "").toLowerCase();
    let backwardStr = "";
    for (let char of str) {
      backwardStr = char + backwardStr;
    }
    console.log(backwardStr);
    console.timeEnd("checkPalindrome runs");
    if (backwardStr === str) {
      return "This is Palindrome";
    } else {
      return "This is not Palindrome";
    }
  } else {
    throw new Error("Input string is required");
  }
};

Steps:

1. Check input parameter is defined or not. If an input parameter is not provided throw an error.
2. Remove spaces and special chars from the given string and convert them into lowerCase or upperCase. (Case should be consistent for each char).
3. Use a for-of loop and append every char to backwardStr at the start position.
4. If given string and formatted string are the same means backwardStr === str, then this is Palindrome else not.
   

**Run Program**

checkPalindrome('Step on no pets')
checkPalindrome('Eva, can I see bees in a cave?')

We have recorded the total time taken by the above program by
console.time(“checkPalindrome runs”);
checkPalindrome runs: 0.371826171875 ms

💡 Let’s Optimize above Program, Optimized way of Palindrome.

/* Optmized way we are running loop only over half string length
 * checkPalindromeOtherway runs: 0.007080078125 ms
*/
checkPalindromeOtherway = (str) => {
 if(str) {
  const pattern = /[^a-zA-z]+/g; // first remove spaces and special chars from given string
  console.time("checkPalindromeOtherway runs");
  str = str.replace(pattern, "").toLowerCase();
  const len = str.length;
  for (let i = 0; i < len / 2; i++) {
    if (str[i] !== str[len - 1 - i]) {
      return "This is not Palidrome";
    }
  }
  console.timeEnd("checkPalindromeOtherway runs");
  return "This is Palidrome";
 }
};

Steps:

1. Looping only half of the string length instead of all chars.
2. Comparing firstIndex char to string last index char and so on.
3. If for all cases, #2 is true means the given string is Palindrome.

Let’s see the difference in timing and now the timing is:
checkPalindromeOtherway runs: 0.07080078125 ms

✋ Remove all spaces and special chars from a string.

//
const str = 'js Mount Web Tutorials';
const pattern = /[^a-zA-z]+/g;
str.replace(pattern, "");
//

✋ Hamming distance Algorithm

Hamming distance is a measure of the minimum number of changes that are required to turn one given string into another given string. One important condition is here that both strings should be of equal length for Hamming distance algorithm.

hammingDistance(‘JsMount’, ‘Ngmount’) : so here hamming distance 
is 2

hammingDistance = (strA, strB) => {
  let result = 0; // store number if chars which are not equal in both given string

  if (strA.length == strB.length) {
    for (let i = 0; i < strA.length; i++) {
      if (strA[i].toLowerCase() != strB[i].toLowerCase()) {
        result++;
      }
    }
    return result;
  } else {
    throw new Error("Strings do not have equal length");
  }
}

✋ Anagrams

Anagrams are words or phrases you spell by rearranging the letters of 
another word or phrase.

checkAnagram = (strOne, strTwo) => {
  const pattern = /[^a-zA-z]+/g; // first remove spaces and special chars from given string
  strOne = strOne.toLowerCase().replace(pattern, "");
  strTwo = strTwo.toLowerCase().replace(pattern, "");
  const charObjOne = {};
  const charObjTwo = {};
  for (let char of strOne) {
    if (charObjOne.hasOwnProperty(char)) {
      charObjOne[char]++;
    } else {
      charObjOne[char] = 1;
    }
  }
  for (let char of strTwo) {
    if (charObjTwo.hasOwnProperty(char)) {
      charObjTwo[char]++;
    } else {
      charObjTwo[char] = 1;
    }
  }
  for (let key in charObjOne) {
    if (charObjOne[key] !== charObjTwo[key]) {
      return false;
    }
  }
  return true;
};

Steps:

1. First, convert both strings in the same case and remove all special chars.
2. Create two empty objects to store each char and its occurrence in the string.
3. Use for-of loop over the first string and put all char in charObjOne and it’s counting as a value.
4. Again Use for-of loop over the second given string and put all char as a key in charObjTwo and its counting as a value.
5. Now use for-in loop on first mapping means charObjOne and compare all char and its max occurrence with charObjTwo data.
6. For any char, if the number of occurrences is not same then return false else return true.

***Run Program**

checkAnagram('older and wiser', 'I learned words')
true

💡 Another Way of Anagram using JavaScript inbuilt method

isAnagram = (inputA, inputB) => {
  const pattern = /[^a-zA-z]+/g;
  const strOne = inputA.toLowerCase().replace(pattern, "");
  const strTwo = inputB.toLowerCase().replace(pattern, "");
  console.log(strOne, strTwo);
  return strOne.split("").sort().join("") === strTwo.split("").sort().join("");
};

****Run Program*****
isAnagram('video game', 'give a demo') > true
isAnagram('older and wiser', 'I learned words') > true

✋ Find Max Recurring Char in a string

findMaxRecurringChar = (str) => {
  const charObj = {};
  let maxCharCount = 0;
  let maxChar = "";

  if (str) {
    for (let char of str) {
      if (charObj.hasOwnProperty(char)) {
        charObj[char]++;
      } else {
        charObj[char] = 1;
      }
      if (charObj[char] > maxCharCount) {
        maxCharCount = charObj[char];
        maxChar = char;
      }
    }
    console.log(charObj);
    console.log(maxChar, maxCharCount);
    return maxChar;
  }
};

Steps:

1. const charObj = {}; Created a blank object to save input string character and its max count value as key-value pair.
2. Use for-of loop over the string, it will return char one by one.
3. If char is already in charObj then simply increase its count by 1: charObj[char]++;
4. Else just put that char into object and make its count 1
5. (charObj[char] > maxCharCount) : With this condition we check if char count is max then maxCharCount

***Run Program*****

findMaxRecurringChar('TopJavaScriptCommonlyaskedAlgorithmsinInterview')
output is > "o" // 4 times

✋ Balanced Parentheses in JavaScript

1. Created 2 arrays named opening and closing with corresponding values of open and close parentheses.
2. Create an array named stack to store all open brackets.
3. Once any close bracket comes – pop element from the stack and match with this, if this does not match return false.
4. At last, if stack is empty means all brackets match and returns true.

checkPattern = (pattern) => {
  const opening = ["[", "{", "("];
  const closed = ["]", "}", ")"];
  const stack = [];

  for (let i = 0; i < pattern.length; i++) {
    const char = pattern[i];
    if (closed.includes(char)) {
      const matchChar = opening[closed.indexOf(char)];
      if (stack.pop() !== matchChar) {
        return false;
      }
    } else {
      stack.push(char);
    }
  }
  return stack.length === 0 ? true : false;
};

console.log(checkPattern("[{{(())}}]")); // true
console.log(checkPattern("[]{}({[()]})")); // true
console.log(checkPattern('[(]){}')) // false
console.log(checkPattern('{}[][{}]]')); // false

✋Find all pairs in an array of integers whose sum is equal to a given number.

Input > findSubArray([1, 5, 4, 2, 3, 3], 6)
Output > [1, 5], [4, 2], [3, 3]

findSubArray = (arr, sum) => {
  const output = [];
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] + arr[j] === sum) {
        output.push([arr[i], arr[j]]);
      }
    }
  }
  return output;
};

console.log(findSubArray([1, 5, 4, 2, 3, 3], 6));

console.log(findSubArray([8, 3, 5, 4, 7, 1, 2, 4], 8));

Output >
0: (2) [1, 5]
1: (2) [4, 2]
2: (2) [3, 3]

0: (2) [3, 5]
1: (2) [4, 4]
2: (2) [7, 1]

✋Find the length of the longest consecutive elements sequence?

Input > findLongestConseqSubseq([3, 11, 1, 4, 5, 8, 9, 10, 12, 13, 54])
Output > [8, 9, 10, 11, 12, 13]

function findLongestConseqSubseq(inputArr) {
  // instead of using array.sort direct, we are passing a native function inside this, because array.sort does not work for negative numbers.
  const arr = inputArr.sort((a, b) => a - b);
  const output = [];

  for (let i = 0; i < arr.length; i++) {
    if (arr[i + 1] - arr[i] === 1) {
      const existIndexArr = output.find((item) => item.includes(arr[i]));
      if (existIndexArr) {
        existIndexArr.push(arr[i + 1]);
      } else {
        output.push([arr[i], arr[i + 1]]);
      }
    }
  }
  if (output.length) {
    const lengths = output.map((item) => item.length);

    // If you need to find maxLength, you can return this.
    const maxLength = Math.max.apply(null, lengths);

    const index = lengths.indexOf(maxLength);
    return output[index];
  } else {
    return [];
  }
}

console.log(findLongestConseqSubseq([3, 11, 1, 4, 5, 8, 9, 10, 12, 13, 54]));
console.log(findLongestConseqSubseq([3, 11, 1]));
console.log(findLongestConseqSubseq([0, -2, 3, -1, 2, 1]));

Output >
[8, 9, 10, 11, 12, 13]
[]
[-3, -2, -1, 0, 1, 2, 3]

JavaScript Hoisting Interview Questions & Answers | Console Programs

Typescript Latest Feature read here…
https://www.jsmount.com/typescript-new-latest-features/

JavaScript String Permutation Program with nice explanation

JavaScript Console Interview Questions | Input Output Program

Top JavaScript Algorithms