🥇用 JavaScript 解決 Google 面試問題：4 種不同的方式

當我研究演算法的性能時，我遇到了這個這是Google模擬面試的影片。。它不僅讓您了解大型科技公司的面試是如何進行的，還可以讓您了解如何盡可能有效地解決演算法問題。

這篇文章是影片的一種伴奏。在其中，我提供了對所顯示的所有解決方案的評論，以及我自己的 JavaScript 解決方案版本。也討論了每種演算法的細微差別。

提醒： 對於“Habr”的所有讀者 - 使用“Habr”促銷代碼註冊任何 Skillbox 課程可享受 10 盧布的折扣。

技能箱推薦： 實踐課程 “移動開發者專業版”.

制定問題

我們得到一個有序數組和一個特定值。然後要求建立一個函數，根據數組中任意兩個數字的總和是否等於給定值，傳回 true 或 false。

換句話說，數組中是否有兩個整數 x 和 y，相加後等於指定值？

實施例A

如果給定一個陣列 [1, 2, 4, 9] 且值為 8，則函數將傳回 false，因為陣列中沒有兩個數字的和可以等於 8。

實施例B

但如果它是一個陣列 [1, 2, 4, 4] 且值為 8，則該函數應該傳回 true，因為 4 + 4 = 8。

解決方案1：暴力破解

時間複雜度：O(N²)。
空間複雜度：O(1)。

最明顯的含義是使用一對巢狀循環。

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

該解決方案效率不高，因為它檢查數組中兩個元素的每個可能的和，並將每對索引進行兩次比較。（例如，當 i = 1 且 j = 2 時，實際上與 i = 2 且 j = 1 進行比較相同，但在此解決方案中我們嘗試了這兩個選項）。

因為我們的解決方案使用一對嵌套的 for 循環，所以它是二次的，時間複雜度為 O(N²)。

解決方案2：二分查找

時間複雜度：O(Nlog(N))。
空間複雜度：O(1).

由於數組是有序的，因此我們可以使用二分搜尋來搜尋解決方案。這是有序數組最有效的演算法。二分查找本身的運行時間為 O(log(N))。但是，您仍然需要使用 for 迴圈來根據所有其他值檢查每個元素。

解決方案可能如下所示。為了清楚起見，我們使用一個單獨的函數來控制二分搜尋。還有removeIndex() 函數，它會傳回數組減去給定索引的版本。

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
 
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2); 
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

演算法從索引[0]開始。然後，它會建立一個不包括第一個索引的陣列版本，並使用二分搜尋來查看是否可以將任何剩餘值新增至陣列中以產生所需的總和。此操作對數組中的每個元素執行一次。

for 迴圈本身的線性時間複雜度為 O(N)，但在 for 迴圈內部我們執行二分搜索，這給出了 O(Nlog(N)) 的總體時間複雜度。該解決方案比前一種方案更好，但仍有改進的空間。

解3：線性時間

時間複雜度：O(N)。
空間複雜度：O(1)。

現在我們將解決這個問題，記住數組是有序的。解決方案是取兩個數字：一個在開頭，一個在結尾。如果結果與要求的不同，則更改起點和終點。

最終我們要么遇到期望的值並返回 true，要么起點和終點收斂並返回 false。

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};

現在一切都很好，解決方案似乎是最佳的。但誰能保證數組是有順序的呢？

然後怎樣呢？

乍一看，我們可以簡單地先對數組進行排序，然後使用上面的解決方案。但這會如何影響執行時間呢？

最好的演算法是快速排序，時間複雜度為O(Nlog(N))。如果我們在最優解中使用它，它的效能將從 O(N) 變成 O(Nlog(N))。是否可以用無序數組找到線性解？

4解決方案

時間複雜度：O(N)。
空間複雜度：O(N)。

是的，有一個線性解決方案；為此，我們需要建立一個包含我們正在尋找的匹配列表的新數組。這裡的權衡是更多的記憶體使用：這是論文中空間複雜度大於 O(1) 的唯一解決方案。

如果給定數組的第一個值為 1 且搜尋值為 8，我們可以將值 7 新增到「搜尋值」陣列中。

然後，當我們處理數組的每個元素時，我們可以檢查「搜尋值」數組，看看其中一個是否等於我們的值。如果是，則傳回true。

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

這個解決方案的基礎是 for 循環，正如我們在上面看到的，它的線性時間複雜度為 O(N)。

我們函數的第二個迭代部分是 Array.prototype.include()，這是一個 JavaScript 方法，它將根據數組是否包含給定值傳回 true 或 false。

要計算 Array.prototype.includes() 的時間複雜度，我們可以查看 MDN 提供的 polyfill（以 JavaScript 編寫）或使用 JavaScript 引擎（例如 Google V8 (C++)）原始程式碼中的方法。

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
 
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
 
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
 
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
 
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
 
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
 
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
 
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
 
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
 
      // 8. Return false
      return false;
    }
  });
}

這裡 Array.prototype.include() 的迭代部分是步驟 7 中的 while 循環，它（幾乎）遍歷給定數組的整個長度。這意味著它的時間複雜度也是線性的。好吧，由於它總是落後我們的主數組一步，所以時間複雜度是 O(N + (N - 1))。使用 Big O 表示法，我們將其簡化為 O(N) - 因為在增加輸入大小時，N 的影響最大。

關於空間複雜度，需要一個額外的數組，其長度鏡像原始數組（負一，是的，但可以忽略），導致空間複雜度為 O(N)。那麼，增加記憶體使用量可以確保演算法的最大效率。

我希望您發現這篇文章作為視訊訪談的補充很有用。它表明一個簡單的問題可以透過使用不同數量的資源（時間、記憶體）以多種不同的方式來解決。

技能箱推薦：

應用在線課程《Python資料分析師》.

在線課程《職業前端開發人員》.

實踐年課程《PHP 開發者從 0 到 PRO》.

來源： www.habr.com

用 JavaScript 解決 Google 面試中的問題：4 種不同的方法

制定問題

然後怎樣呢？

添加評論取消回复

用 JavaScript 解決 Google 面試中的問題：4 種不同的方法

制定問題

然後怎樣呢？

添加評論 取消回复

添加評論取消回复