Interview Algorithm Questions in JavaScript () {… } is subject to the author’s Web front-end introduction and engineering practice. Many of the problems described below are not necessarily algorithmically difficult, but using JavaScript’s built-in apis does require some consideration.
JavaScript Specification
Explain variable promotion in JavaScript
Promotion, as the name implies, means that JavaScript elevates all declarations to the top of the current scope. This means that we can use a variable before it is declared, but while JavaScript elevates the declaration to the top, it doesn’t actually initialize it.
Use strict; The role of
use strict; As the name implies, JavaScript executes in so-called strict mode, and one of its main advantages is that it forces developers to avoid using undeclared variables. Older browsers or execution engines automatically ignore this command.
// Example of strict mode "use strict"; catchThemAll(); Function catchThemAll() {x = 3.14; // Error will be thrown return x * x; }Copy the code
Explain what Event Bubbling is and how to avoid it
An Event Bubbling is an Event that not only fires the current element, but is also passed to the parent element in a nested order. Intuitively, the click event for a child element is also captured by the click event handler for the parent element. Avoid Event Bubbling by using event.stopPropagation() or using Event.cancelBubble in IE 9 below.
What is the difference between == and ===
The key difference is that === compares both types and values, rather than just values.
// Example of comparators
0 == false; // true
0 === false; // false
2 == '2'; // true
2 === '2'; // false
Copy the code
Explain the difference between null and undefined
In JavaScript, NULL is a value that can be assigned, and a variable set to NULL means that it has no value. Undefined means that a variable is declared but has not been assigned.
Explain the difference between Prototypal Inheritance and Classical Inheritance
In class inheritance, classes are immutable. Support for multiple inheritance varies from language to language. Some languages also support the concepts of interface, final, and abstract. Stereotype inheritance, on the other hand, is more flexible. Stereotypes themselves can be mutable, and objects can inherit from multiple stereotypes.
An array of
Find the three numbers in an integer array with the largest product
Given an unordered array of integers, find the three numbers with the largest product.
var unsorted_array = [-10, 7, 29, 30, 5, -10, -70];
computeProduct(unsorted_array); // 21000
function sortIntegers(a, b) {
return a - b;
}
// greatest product is either (min1 * min2 * max1 || max1 * max2 * max3)
function computeProduct(unsorted) {
var sorted_array = unsorted.sort(sortIntegers),
product1 = 1,
product2 = 1,
array_n_element = sorted_array.length - 1;
// Get the product of three largest integers in sorted array
for (var x = array_n_element; x > array_n_element - 3; x--) {
product1 = product1 * sorted_array[x];
}
product2 = sorted_array[0] * sorted_array[1] * sorted_array[array_n_element];
if (product1 > product2) return product1;
return product2
};
Copy the code
Looks for missing numbers in a continuous array
Given an unordered array containing n-1 of n consecutive numbers, with known upper and lower bounds, the complexity of O(n) is required to find the missing numbers.
// The output of the function should be 8 var array_of_integers = [2, 5, 1, 4, 9, 6, 3, 7]; var upper_bound = 9; var lower_bound = 1; findMissingNumber(array_of_integers, upper_bound, lower_bound); //8 function findMissingNumber(array_of_integers, upper_bound, lower_bound) { // Iterate through array to find the sum of the numbers var sum_of_integers = 0; for (var i = 0; i < array_of_integers.length; i++) { sum_of_integers += array_of_integers[i]; } / / to gauss sum Formula in theory of array and / / Formula: [(N * (N + 1)) / 2] - [(M * (M - 1)) / 2]; // N is the upper bound and M is the lower bound upper_limit_sum = (upper_bound * (upper_bound + 1)) / 2; lower_limit_sum = (lower_bound * (lower_bound - 1)) / 2; theoretical_sum = upper_limit_sum - lower_limit_sum; // return (theoretical_sum - sum_of_integers) }Copy the code
Array to heavy
Given an unordered array, remove duplicate numbers from the array and return a new non-duplicate array.
// ES6 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8]; Array.from(new Set(array)); // [1, 2, 3, 5, 9, 8] // ES5 Implementation var array = [1, 2, 3, 5, 1, 5, 9, 1, 2, 8]; uniqueArray(array); // [1, 2, 3, 5, 9, 8] function uniqueArray(array) { var hashmap = {}; var unique = []; for(var i = 0; i < array.length; i++) { // If key returns null (unique), it is evaluated as false. if(! hashmap.hasOwnProperty([array[i]])) { hashmap[array[i]] = 1; unique.push(array[i]); } } return unique; }Copy the code
Calculates the maximum difference between elements in an array
Given an unordered array, find the maximum difference between any two elements. Note that the subscript of the smaller element in the difference calculation must be less than that of the larger element. For example, the array [7, 8, 4, 9, 9, 15, 3, 1, 10] evaluates to 11(15-4) instead of 14(15-1) because the subscript of 15 is less than 1.
var array = [7, 8, 4, 9, 9, 15, 3, 1, 10]; // [7, 8, 4, 9, 9, 15, 3, 1, 10] would return `11` based on the difference between `4` and `15` // Notice: It is not `14` from the difference between `15` and `1` because 15 comes before 1. findLargestDifference(array); If (array.length <= 1) return -1; if (array.length <= 1) return -1; Current_min = array[0]; // current_min = array[0]; var current_max_difference = 0; // If a maximum difference is found, the new value overwrites current_MAX_difference. // The minimum value in the current array is also tracked. Largest value in future '-' smallest value before it 'for (var I = 1; i < array.length; i++) { if (array[i] > current_min && (array[i] - current_min > current_max_difference)) { current_max_difference = array[i] - current_min; } else if (array[i] <= current_min) { current_min = array[i]; } } // If negative or 0, there is no largest difference if (current_max_difference <= 0) return -1; return current_max_difference; }Copy the code
Product of elements in an array
Given an unordered array, we are required to return a new array output, where output[I] is the product of elements in the original array except the elements with subscript I, and we are required to achieve O(n) complexity:
var firstArray = [2, 2, 4, 1];
var secondArray = [0, 0, 0, 2];
var thirdArray = [-2, -2, -3, 2];
productExceptSelf(firstArray); // [8, 8, 4, 16]
productExceptSelf(secondArray); // [0, 0, 0, 0]
productExceptSelf(thirdArray); // [12, 12, 8, -12]
function productExceptSelf(numArray) {
var product = 1;
var size = numArray.length;
var output = [];
// From first array: [1, 2, 4, 16]
// The last number in this case is already in the right spot (allows for us)
// to just multiply by 1 in the next step.
// This step essentially gets the product to the left of the index at index + 1
for (var x = 0; x < size; x++) {
output.push(product);
product = product * numArray[x];
}
// From the back, we multiply the current output element (which represents the product
// on the left of the index, and multiplies it by the product on the right of the element)
var product = 1;
for (var i = size - 1; i > -1; i--) {
output[i] = output[i] * product;
product = product * numArray[i];
}
return output;
}
Copy the code
An array of overlap
Given two arrays, find the intersection of the two arrays. Note that the elements in the intersection should be unique.
var firstArray = [2, 2, 4, 1]; var secondArray = [1, 2, 0, 2]; intersection(firstArray, secondArray); // [2, 1] function intersection(firstArray, secondArray) { // The logic here is to create a hashmap with the elements of the firstArray as the keys. // After that, you can use the hashmap's O(1) look up time to check if the element exists in the hash // If it does exist, add that element to the new array. var hashmap = {}; var intersectionArray = []; firstArray.forEach(function(element) { hashmap[element] = 1; }); // Since we only want to push unique elements in our case... we can implement a counter to keep track of what we already added secondArray.forEach(function(element) { if (hashmap[element] === 1) { intersectionArray.push(element); hashmap[element]++; }}); return intersectionArray; // Time complexity O(n), Space complexity O(n) }Copy the code
string
Reverse string
Given a string, ask for the words to be inverted and output, such as “Welcome to this Javascript Guide!” The output should be “emocleW ot siht tpircsavaJ! EdiuG “.
var string = "Welcome to this Javascript Guide!" ; // Output becomes ! ediuG tpircsavaJ siht ot emocleW var reverseEntireSentence = reverseBySeparator(string, ""); // Output becomes emocleW ot siht tpircsavaJ ! ediuG var reverseEachWord = reverseBySeparator(reverseEntireSentence, " "); function reverseBySeparator(string, separator) { return string.split(separator).reverse().join(separator); }Copy the code
Out-of-order alphabetic string
Given two strings, determine whether the characters are reversed, e.g. Mary and Army are the same letters in reverse order:
var firstWord = "Mary";
var secondWord = "Army";
isAnagram(firstWord, secondWord); // true
function isAnagram(first, second) {
// For case insensitivity, change both words to lowercase.
var a = first.toLowerCase();
var b = second.toLowerCase();
// Sort the strings, and join the resulting array to a string. Compare the results
a = a.split("").sort().join("");
b = b.split("").sort().join("");
return a === b;
}
Copy the code
Will ask for strings
Determine if a string is a palindrome string, for example racecar and Race Car are palindrome strings:
isPalindrome("racecar"); // true
isPalindrome("race Car"); // true
function isPalindrome(word) {
// Replace all non-letter chars with "" and change to lowercase
var lettersOnly = word.toLowerCase().replace(/\s/g, "");
// Compare the string with the reversed version of the string
return lettersOnly === lettersOnly.split("").reverse().join("");
}
Copy the code
The stack and queue
Enqueue and enqueue are implemented using two stacks
var inputStack = []; // First stack
var outputStack = []; // Second stack
// For enqueue, just push the item into the first stack
function enqueue(stackInput, item) {
return stackInput.push(item);
}
function dequeue(stackInput, stackOutput) {
// Reverse the stack such that the first element of the output stack is the
// last element of the input stack. After that, pop the top of the output to
// get the first element that was ever pushed into the input stack
if (stackOutput.length <= 0) {
while(stackInput.length > 0) {
var elementToOutput = stackInput.pop();
stackOutput.push(elementToOutput);
}
}
return stackOutput.pop();
}
Copy the code
Check whether the braces are closed
Create a function to determine whether the curly braces in a given expression are closed:
var expression = "{{}}{}{}"
var expressionFalse = "{}{{}";
isBalanced(expression); // true
isBalanced(expressionFalse); // false
isBalanced(""); // true
function isBalanced(expression) {
var checkString = expression;
var stack = [];
// If empty, parentheses are technically balanced
if (checkString.length <= 0) return true;
for (var i = 0; i < checkString.length; i++) {
if(checkString[i] === '{') {
stack.push(checkString[i]);
} else if (checkString[i] === '}') {
// Pop on an empty array is undefined
if (stack.length > 0) {
stack.pop();
} else {
return false;
}
}
}
// If the array is not empty, it is not balanced
if (stack.pop()) return false;
return true;
}
Copy the code
recursive
Binary conversion
Converts the input number to a binary string by some recursive function:
decimalToBinary(3); // 11 decimalToBinary(8); // 1000 decimalToBinary(1000); // 1111101000 function decimalToBinary(digit) { if(digit >= 1) { // If digit is not divisible by 2 then recursively return proceeding // binary of the digit minus 1, 1 is added for the leftover 1 digit if (digit % 2) { return decimalToBinary((digit - 1) / 2) + 1; } else { // Recursively return proceeding binary digits return decimalToBinary(digit / 2) + 0; } } else { // Exit condition return ''; }}Copy the code
Binary search
function recursiveBinarySearch(array, value, leftPosition, rightPosition) { // Value DNE if (leftPosition > rightPosition) return -1; var middlePivot = Math.floor((leftPosition + rightPosition) / 2); if (array[middlePivot] === value) { return middlePivot; } else if (array[middlePivot] > value) { return recursiveBinarySearch(array, value, leftPosition, middlePivot - 1); } else { return recursiveBinarySearch(array, value, middlePivot + 1, rightPosition); }}Copy the code
digital
The index value that determines whether it is 2
isPowerOfTwo(4); // true isPowerOfTwo(64); // true isPowerOfTwo(1); // true isPowerOfTwo(0); // false isPowerOfTwo(-1); // false // For the non-zero case: function isPowerOfTwo(number) { // `&` uses the bitwise n. // In the case of number = 4; the expression would be identical to: // `return (4 & 3 === 0)` // In bitwise, 4 is 100, and 3 is 011. Using &, if two values at the same // spot is 1, then result is 1, else 0. In this case, it would return 000, // and thus, 4 satisfies are expression. // In turn, if the expression is `return (5 & 4 === 0)`, it would be false // since it returns 101 & 100 = 100 (NOT === 0) return number & (number - 1) === 0; } // For zero-case: function isPowerOfTwoZeroCase(number) { return (number ! == 0) && ((number & (number - 1)) === 0); }Copy the code