Detaillierte Erläuterung häufiger Algorithmusfragen in JavaScript-Interviews

JavaScript-Spezifikation

Erklären Sie die Variablenförderung in JavaScript

Die sogenannte Förderung bedeutet, wie der Name schon sagt, dass JavaScript alle Deklarationen nach oben befördert des aktuellen Umfangs. Dies bedeutet, dass wir eine Variable verwenden können, bevor sie deklariert wird. JavaScript führt die Deklaration zwar nach oben, führt jedoch nicht den eigentlichen Initialisierungsprozess durch.

Erklären Sie die Rolle von use strict;

use strict;Wie der Name schon sagt, wird JavaScript im sogenannten strikten Modus ausgeführt. Einer seiner Hauptvorteile besteht darin, dass es Entwickler zwingen kann um die Verwendung nicht deklarierter Variablen zu vermeiden. Bei älteren Versionen von Browsern oder Ausführungs-Engines wird diese Anweisung automatisch ignoriert.

// Example of strict mode
"use strict";

catchThemAll();
function catchThemAll() {
  x = 3.14; // Error will be thrown
  return x * x;
}

Erklären Sie, was Event Bubbling ist und wie man es vermeidet.

Event Bubbling bedeutet, dass ein Ereignis nicht nur das aktuelle Element auslöst, sondern auch an das übergeordnete Element übergeben wird verschachtelte Reihenfolge. Intuitiv ausgedrückt wird ein Klickereignis für ein untergeordnetes Element auch vom Klickereignishandler des übergeordneten Elements erfasst. Um Event Bubbling zu vermeiden, können Sie event.stopPropagation() oder event.cancelBubble für IE 9 und niedriger verwenden. Was ist der Unterschied zwischen

== und ===

===? Der Hauptunterschied besteht darin, dass === Typen und Werte vergleicht zur gleichen Zeit, anstatt nur Werte zu vergleichen.

// Example of comparators
0 == false; // true
0 === false; // false

2 == '2'; // true
2 === '2'; // false

Erklären Sie den Unterschied zwischen null und undefiniert

In JavaScript ist null ein Wert, der zugewiesen werden kann, und eine auf null gesetzte Variable bedeutet, dass sie keinen Wert hat. Undefiniert bedeutet, dass eine Variable zwar deklariert, aber noch kein Wert zugewiesen wurde.

Erklären Sie den Unterschied zwischen prototypischer Vererbung und klassischer Vererbung. Bei der Klassenvererbung gibt es verschiedene Sprachen, die die Mehrfachvererbung unterstützen der Schnittstelle, endgültig und abstrakt. Die Prototypenvererbung ist flexibler, der Prototyp selbst kann veränderbar sein und Objekte können von mehreren Prototypen erben.

Array

Finden Sie die drei Zahlen mit dem größten Produkt im Ganzzahl-Array

Angenommen ein ungeordnetes Array mit ganzen Zahlen, werden Sie aufgefordert, die drei Zahlen mit dem größten Produkt zu finden .

Fehlende Zahlen in einem kontinuierlichen Array finden

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
};

Bei einem ungeordneten Array, das n – 1 von n aufeinanderfolgenden Zahlen enthält, sind die oberen und unteren Grenzen bekannt und dies ist erforderlich Die Komplexität von

besteht darin, die fehlenden Zahlen zu finden.

O(n)

Array-Deduplizierung

// 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)
}

Bei einem ungeordneten Array ist es erforderlich, doppelte Zahlen im Array zu entfernen und ein neues Array ohne Duplizierung zurückzugeben.

Berechnung der maximalen Differenz der Elemente im 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;
}

Ermitteln Sie bei einem gegebenen ungeordneten Array die maximale Differenz zwischen zwei beliebigen Elementen. Beachten Sie, dass hier die Differenzberechnung erforderlich ist Das kleinere Element muss kleiner sein als der Index des größeren Elements. Beispiel:

Der berechnete Wert dieses Arrays ist 11( 15 – 4 ) statt 14(15 – 1), da der Index von 15 kleiner als 1 ist.

[7, 8, 4, 9, 9, 15, 3, 1, 10]

Das Produkt der Elemente im Array

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;
}

Bei einem ungeordneten Array ist es erforderlich, eine neue Array-Ausgabe zurückzugeben, wobei Ausgabe[i] das Element im ursprünglichen Array ist, außer Für den Index i muss das Elementprodukt von mit O(n)-Komplexität implementiert werden:

Array-Schnittpunkt

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;
}

Bei zwei Arrays ist es erforderlich, den Schnittpunkt von zu finden Beachten Sie, dass die Elemente im Schnittpunkt eindeutig sein sollten.

String

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)
}

Reverse String

Bei einer gegebenen Zeichenfolge ist es erforderlich, die darin enthaltenen Wörter umzukehren und sie dann auszugeben, z. B. „Willkommen in diesem Javascript-Handbuch.“ !“ sollte als „emocleW ot siht tpircsavaJ !ediuG“ ausgegeben werden.

Gemischte Zeichenfolgen mit denselben Buchstaben

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);
}

Bestimmen Sie anhand zweier Zeichenfolgen, ob die Buchstaben vertauscht sind. Die Reihenfolge ist beispielsweise umgekehrt:

Mary fragt die Zeichenfolge Army

, um zu bestimmen, ob eine Zeichenfolge eine Palindromzeichenfolge ist. Beispielsweise sind

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;
}

und

beide Palindromzeichenfolgen:

racecarStapel und Warteschlangerace car

Verwenden Sie zwei Stapel, um das Ein- und Ausreihen in die Warteschlange zu implementieren

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("");
}

Bestimmen Sie, ob die geschweiften Klammern geschlossen sind

Erstellen Sie eine Funktion, um zu bestimmen, ob die Klammern im angegebenen Ausdruck werden geschlossen:

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();
}

Rekursiv

Binärkonvertierung

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] === &#39;{&#39;) {
      stack.push(checkString[i]);
    } else if (checkString[i] === &#39;}&#39;) {
      // 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;
}

Konvertieren Sie die eingegebene Zahl in eine Binärzahl durch eine rekursive Funktion. Zeichenfolge:

Binäre Suche

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 '';
  }
}

Zahl

Bestimmen Sie, ob es sich um einen Exponentialwert von 2 handelt

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);
  }
}

Das Obige ist das JavaScript-Interview. Detaillierte Erläuterungen zu gängigen Algorithmen Probleme in . Weitere verwandte Inhalte finden Sie auf der chinesischen PHP-Website (www.php.cn)!

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);
}