Home > Article > Web Front-end > Detailed explanation of common algorithm questions in JavaScript interviews
The so-called promotion, as the name suggests, means that JavaScript will promote all declarations to the top of the current scope. This means that we can use a variable before it is declared, but although JavaScript will raise the declaration to the top, it will not perform the actual initialization process.
use strict;
##use strict;As the name suggests, JavaScript will be executed in the so-called strict mode. One of the main The advantage is that it forces developers to avoid using undeclared variables. For older versions of browsers or execution engines, this instruction will be automatically ignored.
// Example of strict mode "use strict"; catchThemAll(); function catchThemAll() { x = 3.14; // Error will be thrown return x * x; }Explain what Event Bubbling is and how to avoid itEvent Bubbling means that an event will not only trigger the current element, but will also be passed to the parent element in nested order. Intuitively speaking, a click event on a child element will also be captured by the click event handler of the parent element. To avoid Event Bubbling, you can use
event.stopPropagation() or below IE 9, use
event.cancelBubble. What is the difference between
=== is the so-called strict comparison. The key difference is
===Will compare types and values at the same time, instead of only comparing values.
// Example of comparators 0 == false; // true 0 === false; // false 2 == '2'; // true 2 === '2'; // falseExplain the difference between null and undefinedIn JavaScript, null is a value that can be assigned, and a variable set to null means that it has no value. Undefined means that although a variable has been declared, no value has been assigned yet. Explain the difference between Prototypal Inheritance and Classical InheritanceIn class inheritance, the class is immutable. Different languages have different support for multiple inheritance. Some languages also support it. The concepts of interface, final and abstract. Prototypal inheritance is more flexible, the prototype itself can be mutable, and objects may inherit from multiple prototypes. ArrayFind the three numbers with the largest product in the integer arrayGiven an unordered array containing integers, you are required to 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 };Find missing numbers in a continuous arrayGiven an unordered array, which contains n – 1 of n consecutive numbers, the upper and lower boundaries are known, and it is required to
O(n) complexity to find the missing number.
// 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]; } // 以高斯求和公式计算理论上的数组和 // 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) }Array deduplicationGiven an unordered array, it is required to remove duplicate numbers in 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; }Calculation of the maximum difference of elements in the arrayGiven an unordered array, find the maximum difference between any two elements. Note that the minimum difference calculation is required here. The index of the element must be smaller than the index of the larger element. For example
[7, 8, 4, 9, 9, 15, 3, 1, 10]The calculated value of this array is 11(15 – 4) instead of 14(15 – 1), because 15 The subscript 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); function findLargestDifference(array) { // 如果数组仅有一个元素,则直接返回 -1 if (array.length <= 1) return -1; // current_min 指向当前的最小值 var current_min = array[0]; var current_max_difference = 0; // 遍历整个数组以求取当前最大差值,如果发现某个最大差值,则将新的值覆盖 current_max_difference // 同时也会追踪当前数组中的最小值,从而保证 `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; }The product of elements in the arrayGiven an unordered array, it is required to return a new array output, where output[i] is the elements in the original array except the element with subscript i. The product is required to be implemented with 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; }Array intersectionGiven two arrays, it is required to find the intersection of the two arrays. Note that the elements in the intersection should be only.
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) }StringInvert the stringGiven a string, it is required to reverse the words in it and then output it, such as "Welcome to this Javascript Guide!" should be The output is "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); }Out-of-order strings with the same lettersGiven two strings, determine whether the strings are composed of reversed letters, such as
Mary and
Army is the same letter but 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; }will ask the string to determine whether a string is a palindrome string, such as
racecar and
race car are all 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(""); }Stack and QueueUse two stacks to implement enqueueing and dequeuing
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(); }
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; }RecursiveBinary conversionThrough a recursive function Convert the input number into a binary string:
decimalToBinary(3); // 11 decimalToBinary(8); // 1000 decimalToBinary(1000); // 1111101000 function decimalToBinary(digit) { if(digit >= 1) { // If digit is not pisible 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 ''; } }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); } }NumberDetermine whether it is an exponential value of 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); }