Algorithms and solutions in Javascript
I am going to write some collection of algorithm that are very important to improve your skill as well as for the interview. In every section I will first write the question and then answer of given problem.
Q. Write a function to accept two string and return true if second array is anagram of first. Anagram means from second array can we construct the word of first or not.So before looking into the answer of each question I will suggest you to try by your self.
example:
str1= nmz; str2= mnz; → true
str1=lobe; str2= eboe →false
Answer:
function same (str1, str2){
//if requirement is to have same frequency then put length condition if both string have same length then only search else return false;if(str1.length!==str2.length)return false;
let obj={};
for(let value of str1){
obj[value]= ++ obj[value] ||1;
}
for(let value of str2){
if(obj[value]> 0){
- -obj[value];
}
else{
return false;
}
}
return true;
}
Q: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Answer:
function longestPallindrome(s){
let startIndex=0;
let maxLength=1;function expandAroundMiddle(left,right){
while(left>=0&& right <s.length && s[left]===s[right]){
const currentPalLength= right -left +1;
if(currentPalLength> maxLength){
maxLength= currentPalLength;
startIndex=left;
}
left -=1;
right+=1;
}
}
for(let i=0;i<s.length;i++){
expandAroundMiddle(i-1,i+1);
expandAroundMiddle(i,i+1);
}
return s.slice(startIndex, startIndex+ maxLength);
}
Q. Write a function which accept string and a number of swift and it should return the string which should swift to the given number.
example: fn(‘abcde’,4) => it should return string as eabcd
Answer:
function rotLeft2(a, d) {
let length = a.length;
let b=[];
for (let key in a) {
let swiftIndex = key — d;
if (swiftIndex > length) {
swiftIndex = swiftIndex — length;
}
else if (swiftIndex < 0) {
swiftIndex = swiftIndex + length;
}
b[swiftIndex]=a[key];
}
return b.join(“”);
}
Q: write a function which accept the array and return the first possible
combination in which sum is equal to zero.
Here we can see in the same sorted array we have to find the sum so if we
nested same array and check with each item then sum then complexity will be o(n2). So we will create two pointer one from start and one from end and try to find the sum.here complexity will be o(n)
Note: we are passing sorted array.
Answer:
function sumZero(arr, sum) {
//now we know that array is sorted
let firstIndex = 0;
let lastIndex = arr.length — 1;
while (firstIndex < lastIndex) {
let addedData=arr[firstIndex] + arr[lastIndex];
if (addedData === sum) {
//we returning from here so it will give us the first pair
// if want to check all possible pair then don’t return we can push
//to the array and at last we can return.
return [arr[firstIndex] ,arr[lastIndex]];
}
else if(addedData>0) {
lastIndex — ;
}
else{
firstIndex ++;
}
}
}
Q: Write a function which accept the array of date and return the sorted array of date.
Answer :
I will write the answer for two date format in which the above question can be asked.
let dateArray=[“09/06/2015”, “25/06/2015”, “22/06/2015”, “25/07/2015];
dateArray.sorfunction(a,b) {
a = a.split(‘/’).reverse().join(‘’);
b = b.split(‘/’).reverse().join(‘’);
return a-b
// return a.localeCompare(b); // ← alternative
});
let arr= [“1-jun-15”, “1-feb-15”, “1-apr-15”, “1-may-15”];
let month = { jan: 1, feb: 2, mar: 3, apr: 4, may: 5, jun: 6, jul: 7, aug: 8, sep: 9, oct: 10, nov: 11, dec: 12 };
arr.sort(function (a, b) {
var aa = a.split(‘-’),
bb = b.split(‘-’);return aa[2] — bb[2] || MONTHS[aa[1]] — MONTHS[bb[1]] || aa[0] — bb[0];
});}
Q: Write a function which accept string and returns true if the string is palindrome.
Answer:
function isPallindrome(k){
let i=0;let s= k.toLowerCase().replace(/[\W_]/g,””);
let j=s.length-1;
while(i<j){
if(s[i]!==s[j]){
return false;
}
i++;
j — ;
}
return true;
Q: Write a function which accept two array and return merged sorted array of two array.
Note: Here two array that we are passing is unsorted array,we have to return the merged sorted array.
Answer:
function mergeSort(a){
//the main idea is to break the array into two seaprate array and
//do the check recursivly
if(a.length<=1) return a;
let midIndex=Math.floor(a.length/2);
let first = mergeSort(a.slice(0, midIndex));
let second= mergeSort(a.slice(midIndex));
return sort(first,second);
}
function sort(arr, arr2){
let result=[];
let i =0;
let j=0;
while(i<arr.length && j<arr2.length){
if(arr[i]<arr2[j]){
result.push(arr[i]);
i++;
}
else{
result.push(arr2[j]);
j++;
}
}
while(i<arr.length){
result.push(arr[i]);
i++;
}
while(j<arr2.length){
result.push(arr2[j]);
j++
}return result;
}
Q: Write a function which group the anagrams together and return the array of anagrams
Answer:
function groupAnagrams(strs){
let grouped={};
for(let i=0;i<strs.length;i++){
const word= strs[i];
const key= word.split(‘’).sort().join(‘’);if(!grouped[key]){
grouped[key]=[];
}
grouped[key].push(word);
}
return Object.values(grouped);
}
Q: Write a function which accept a string and return the max length of the sub string.
Example: ‘abcddfghrhiertyesloce’ => it should return 7
Answer:
function findLongSubString(str){
let startWindow=0;
let windowObj={};
let maxLength=0;
for(let i=0;i<str.length;i++){
let char=str[i];
if(windowObj[char]>=startWindow){
startWindow = windowObj[char] +1;
}
windowObj[char]= i;
maxLength= Math.max(maxLength, i — startWindow);
}return maxLength;
}
Q: Find the pattern in the given sentance and return the index of the pattern
that found in the sentence.
Answer:
function findPattern(stringValue, pattern) {
let count = 0;/*
Note: we cant use (for(let i in arr)) because below we are adding
the index so string + j index will give string*/
for (let i = 0; i < stringValue.length; i++) {
if (stringValue[i] === pattern[0]) {
for (let j = 1; j < pattern.length; j++) {
if (stringValue[i + j] !== pattern[j]) { // here i and j should be integer, thats what metione in note above
break;
}
if(j===pattern.length-1) count++;
}
}
}
return count;
}
Q: If we can construct a WORD OR SENTANCE from MAGAZINE word then return true.
Here we have to check the number of letter present in magazine and compare
the count of the number of letter of magazine to the number of letter of word that we have to construct.
Similar Question:
Q. Check the exact number of word present in the magazine or not if it contains then return true.
Here we have to check the exact word that is present in magazine or not, so we can split the sentence that will return the array of array and then we can check the count of magazine and the sentence that we have to construct form the magazine.
Answer:
/* This is solution of first problem*/
function findSame( str1, str2){
let obj={};
for(let value of str2){
obj[value]= ++obj[value] ||1;
}for(let value of str1){
if(obj[value]<1){
return false;
}
obj[value]= — obj[value]
}
return true;
}/* This solution of second problem*/
function harmlessRansomNote(noteText, magazineText) {
var noteArr = noteText.split(‘ ‘);
var magazineArr = magazineText.split(‘ ‘);
var magazineObj = {};
magazineArr.forEach(word => {
if (!magazineObj[word]) magazineObj[word] = 0;
magazineObj[word]++;
});
var noteIsPossible = true;
noteArr.forEach(word => {
if (magazineObj[word]) {
magazineObj[word] — ;
if (magazineObj[word] < 0) noteIsPossible = false;
}
else noteIsPossible = false;
});
return noteIsPossible;
}
Q: Find the max sum of the consecutive 3 three digit from the
unsorted array.
Answer:
In this type of question we will create a window pattern
function maxSum2(arr, num){
let sum= 0;
let maxNum=0;
for(let i= 0; i<num;i++){
sum += arr[i];
}
for(let j=num;j < arr.length ; j++){
sum= sum — arr[j-num] + arr[j];
maxNum= Math.max(sum,maxNum);
}
return maxNum;
}
Q: find the number of combination in array in which sum is equal to the number pass as parameter,same number should not be added.
Note: assuming unsorted array.
Answer:
function sumZero(arr, sum){
let tempArr=[];
let sumArr=[];
for(let value of arr){
let numRequired= sum — value;
let index= tempArr.indexOf(numRequired);
if(index >-1){
sumArr.push([value, numRequired]);
tempArr.splice(index,1);// dont forget this step otherwise same num added twice in array
}
else{
tempArr[value]= value;
}
}
return sumArr;
}
Q: Write a function which accepts two array and true true if the second array contains the square of the corresponding element of first array.The frequency of the number should be same for both.
ex: arr1=[1,2,3] arr2= [4,1,9] //true
arr1=[4,6,2,6] arr2= [16,4,36,12] //false frequency not matches here
arr1=[1,2] arr2=[4,1,2] //false array length not same
Note: here we are passing unsorted array;
Asnwer:
function findArraynewar,newar2){
if(newar.length !== newar2.length){
return false;
}
let obj={};
for(let value of newar){
obj [value **2] = ++obj[value **2] ||1;
}
for(let key of newar2){
if(obj[key]>0){
obj[key]= — obj[key];
}
else{
console.log(key,obj[key]);
return false;
}
}return true;
};
Q: Find the index of the num in given array using binary search.
Note: assuming sorted array
Answer:
In this type of question we will create two window and swift our first and last counter
function findNum(arr, num) {
let middleIndex = Math.floor(arr.length / 2);
let first= 0;
let last= arr.length-1;
while(arr[middleIndex]!==num && first<=last){
/*
here the num is greater than middle index then we will decrease
the last window to middle index -1
*/
if(arr[middleIndex]>num){
last = middleIndex -1;
}
else{
/*
here num is greater than middle index so we will swift the first window to middleIndex +1;
*/
first =middleIndex + 1;
}
middleIndex =Math.floor((first+last) /2);
console.log(middleIndex);
}
return middleIndex;
}
Q: Write function which return true or false based on the value present in the array.
Note: assuming sorted array.
Answer:
here we only have to return true or false not the index of the number, so we can use slice and called the array recursively, but if there is requirement to find the index of the number then binary search using window pattern is based solution.
function findNum(arr, num) {
let middleIndex = Math.floor(arr.length / 2);
if(arr[middleIndex]===num){
return true;
}
else if(arr.length ===1){
return arr[0] ===num;
}
if(arr[middleIndex]<num){
return findNum(arr.slice(middleIndex),num);
}
else{
return findNum(arr.slice(0, middleIndex),num);
}
}
Question: Write a function that takes in an array of string .Return true if all strings are anagrams of one another and false if even a single is not n anagram of the other.
Ex: let str=[“abcd”, “dbca”, “dbac”, “adcb”]; should return true
Answer:
function anagram(a){
let sorted= a.map(t=>t.split(‘’).sort().join(‘’));
for(let i=1; i<sorted.length;i++){
if(sorted[0]!==sorted[i]){
return false;
}
}
return true;
}
Wrapping Up
I tried to cover some important algorithm, still many more still are there like algorithm for BinaryTree, LinkedList,HeapBinaryTree,Graph,Matrix you can find question and answer in javascript to the below github account.
All the best!!!