Common algorithms for Javascript interview -- from freecodecamp

Find equivalent difference

Knowledge summary: symmetric difference. Mathematically, the symmetric difference of two sets is A set composed of elements belonging to only one set but not the other set. For example, the symmetric difference of set let A = [1,2,3] and let B = [2,3,4] is A △ B = C = [1,4]. This operation in set theory is equivalent to XOR operation in Boolean logic.

Create a function sym, input two or more arrays as parameters, and then return an array with symmetric difference value

Idea: set two arrays (for example, let A = [1, 2, 3], let B = [2, 3, 4]) as parameters, and return A symmetric difference array (A △ B = C = [1, 4]) with no duplicates in the array.

```function sym() {
var args = [];
for (var i = 0; i < arguments.length; i++) {
args.push(arguments[i]);
}

function symDiff(arrayOne, arrayTwo) {
var result = [];

arrayOne.forEach(function(item) {
if (arrayTwo.indexOf(item) < 0 && result.indexOf(item) < 0) {
result.push(item);
}
});

arrayTwo.forEach(function(item) {
if (arrayOne.indexOf(item) < 0 && result.indexOf(item) < 0) {
result.push(item);
}
});

return result;
}

// Apply reduce method to args array, using the symDiff function
return args.reduce(symDiff);
}
```
``` function sym() {
let argv = Array.from(arguments).reduce(diffArray);
return argv.filter((element, index, array) => index === array.indexOf(element));//remove duplicates
}

function diffArray(arr1, arr2) {
return arr1
.filter(element => !arr2.includes(element))
.concat(arr2.filter(element => !arr1.includes(element)));
}

// test here
sym([1, 2, 3], [5, 2, 1, 4]);
```

Complementary array de duplication method

```function unique(a) {

var res = a.filter(function(item, index, array) {
return array.indexOf(item) === index;
});

return res;
}

var a = [1, 1, '1', '2', 1];
var ans = unique(a);
console.log(ans);//[1, '1', '2',]
```

Update inventory

Create a two-dimensional array, compare and update the "inventory" elements stored in the two-dimensional array, and then compare it with the newly generated second two-dimensional array, Update the current inventory item quantity (arr1). If the comparison object is not found, add the new object and quantity to the inventory array. Note: the returned inventory array should be sorted alphabetically by the array elements.

```function updateInventory(arr1, arr2) {

// Variable for location of product
var index;

// A helper method to return the index of a specified product (undefined if not found)
var getProductIndex = function (name) {
for (var i = 0; i < this.length; i++) {
if (this[i][1] === name) {
return i;
}
}
return undefined;
}

// For each item of the new Inventory
for (var i = 0; i < arr2.length; i++) {

// Invoke our helper function using arr1 as this
index = getProductIndex.call(arr1, arr2[i][1]);

// If the item doesn't exist
if (index === undefined) {
// Push the entire item
arr1.push(arr2[i]);
} else {
// Add the new quantity of the current item
arr1[index][0] += arr2[i][0];
}

}

// Sort alphabetically, by the product name of each item
arr1.sort(function (a, b) {
if (a[1] > b[1]) {
return 1;
}
if (a[1] < b[1]) {
return -1;
}
return 0;
});

return arr1;
}

// test here
// Example inventory lists
var curInv = [
[21, "Bowling Ball"],
[2, "Dirty Sock"],
[1, "Hair Pin"],
[5, "Microphone"]
];

var newInv = [
[2, "Hair Pin"],
[3, "Half-Eaten Apple"],
[67, "Bowling Ball"],
[7, "Toothpaste"]
];

updateInventory(curInv, newInv);
```
``` function updateInventory(arr1, arr2) {
// All inventory must be accounted for or you're fired!

var index;
var arrCurInvName = []; // Names of arr1's items
var arrNeInvName = []; // Names of arr2's items

// Same as using two for loops, this takes care of increasing the number of stock quantity.
arr1.map(function(item1) {
return arr2.map(function(item2) {
if (item1[1] === item2[1]) {
item1[0] = item1[0] + item2[0]; //Increase number of stock
}
});
});

// Get item's name for new Inventory
arr2.map(function(item) {
arrNeInvName.push(item[1]);
});

// Get item's name for Current Inventory
arr1.map(function(item) {
arrCurInvName.push(item[1]);
});

// Add new inventory items to current inventory.
arrNeInvName.map(function(item) {
if (arrCurInvName.indexOf(item) === -1) {
index = arrNeInvName.indexOf(item);
arr1.push(arr2[index]);
}
});

// Sort the array alphabetically using the second element of the array as base.
arr1.sort(function(currItem, nextItem) {

//Ternary function to avoid using if else
return currItem[1] > nextItem[1] ? 1 : -1;
});

return arr1;
}

// test here
// Example inventory lists
var curInv = [
[21, "Bowling Ball"],
[2, "Dirty Sock"],
[1, "Hair Pin"],
[5, "Microphone"]
];

var newInv = [
[2, "Hair Pin"],
[3, "Half-Eaten Apple"],
[67, "Bowling Ball"],
[7, "Toothpaste"]
];

updateInventory(curInv, newInv);
```
```function updateInventory(arr1, arr2) {
// All inventory must be accounted for or you're fired!

// convert current inventory (arr1) to an one-dimensional array
const inventory = Array.prototype.concat.apply([], arr1);

// loop through new delivery (arr2)
for (let i = 0; i < arr2.length; i++) {

// extract item properties for easy reference
const item = arr2[i][1];
const quantity = arr2[i][0];

// check if item already exists in inventory
const position = inventory.indexOf(item);

// exsisting item: update quantity
if (position !== -1) {
const row = Math.floor(position / 2);
arr1[row][0] += quantity;
continue;
}

// alien item: add to inventory
arr1.push([quantity, item]);

}

// sort inventory in alphabetical order
arr1.sort((previous, next) => (previous[1] > [next[1]]) ? 1 : -1);

return arr1;

}

// test here
// Example inventory lists
var curInv = [
[21, "Bowling Ball"],
[2, "Dirty Sock"],
[1, "Hair Pin"],
[5, "Microphone"]
];

var newInv = [
[2, "Hair Pin"],
[3, "Half-Eaten Apple"],
[67, "Bowling Ball"],
[7, "Toothpaste"]
];

updateInventory(curInv, newInv);
```

Rearrange all the characters in a string, and then generate a new string. There are no consecutive repeated characters in the returned new string. Continuous repetition is judged by a single character.

For example, aab should return 2 because it has six permutations: aab, aab, aba, aba, baa, baa, but there are only two characters without continuous repetition (character a is the repeated character in this example): aba, aba

```function permAlone(str) {

// Create a regex to match repeated consecutive characters.
var regex = /(.)\1+/g;

// Split the string into an array of characters.
var arr = str.split('');
var permutations = [];
var tmp;

// Return 0 if str contains same character.
if (str.match(regex) !== null && str.match(regex)[0] === str) return 0;

// Function to swap variables' content.
function swap(index1, index2) {
tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}

// Generate arrays of permutations using the algorithm.
function generate(int) {
if (int === 1) {
// Make sure to join the characters as we create  the permutation arrays
permutations.push(arr.join(''));
} else {
for (var i = 0; i != int; ++i) {
generate(int - 1);
swap(int % 2 ? 0 : i, int - 1);
}
}
}

generate(arr.length);

// Filter the array of repeated permutations.
var filtered = permutations.filter(function(string) {
return !string.match(regex);
});

// Return how many have no repetitions.
return filtered.length;
}

// Test here.
permAlone('aab');
```

regex contains the regular expression to match repeated consecutive characters.
The string str is split into an array of characters, arr.
0 is returned if str contains same characters.
The function swap() is used for the purpose of swapping the contents of two variable's contents.
The next block of code uses Heap's algorithm to generate arrays of permutations in permutations.
The filtered variable filters permutations to include only non-repeated permutations.
filtered.length returns the number of total permutations of the provided string that don't have repeated consecutive letters.

Quick sort

Now let's start talking about quick sorting. Quick sort is an efficient recursive divide and conquer method to sort arrays. In this method, we need to select a pivot value in the original array, and then divide the array into two sub arrays whose values are greater than or less than the pivot value. Then we will recursively call the results of the quick sort algorithm on the two sub arrays to use them together until there is an empty array or an array of single elements, and then return the results. The expanded result of recursive call will return the sorted array.

Quick sort is a very effective sort method, with an average time complexity of O(nlog(n)), and it is also relatively easy to implement. These features make quick sort a popular and useful sort method.

Description: create a function and name it quickSort. The input parameter is an array, and all array elements are integer types. Then return the whole array in the order from minimum to maximum. Although it is important to select a pivot value, any pivot can meet the requirements. In case, I generally choose the first or last element as the number axis value.

Keywords: Javascript Algorithm Interview

Added by monloi on Fri, 17 Dec 2021 00:02:45 +0200