JavaScript로 Google 인터뷰에서 문제 해결: 4가지 방법

알고리즘의 성능을 연구하던 중 이런 것을 발견했습니다. 구글 모의면접 영상입니다.. 대형 기술 기업에서 면접이 어떻게 진행되는지에 대한 아이디어를 제공할 뿐만 아니라, 알고리즘 문제를 최대한 효율적으로 해결하는 방법을 이해할 수 있게 해줍니다.

이 글은 영상에 대한 일종의 반주입니다. 여기에는 표시된 모든 솔루션에 대한 설명과 JavaScript로 작성된 솔루션의 자체 버전이 제공됩니다. 각 알고리즘의 미묘한 차이도 논의됩니다.

알림: "Habr"의 모든 독자를 위한 - "Habr" 프로모션 코드를 사용하여 Skillbox 과정에 등록할 때 10 루블 할인.

Skillbox는 다음을 권장합니다. 실기 코스 "모바일 개발자 PRO".

문제 성명

순서가 지정된 배열과 특정 값이 제공됩니다. 그런 다음 배열에 있는 두 숫자의 합이 주어진 값과 같을 수 있는지 여부에 따라 true 또는 false를 반환하는 함수를 생성하라는 요청을 받습니다.

즉, 배열에 함께 더하면 지정된 값과 같은 두 개의 정수 x와 y가 있습니까?

예시 A

배열 [1, 2, 4, 9]가 주어지고 값이 8인 경우 배열에 있는 두 숫자의 합이 8이 될 수 없기 때문에 함수는 false를 반환합니다.

예시 B

그러나 배열 [1, 2, 4, 4]이고 값이 8인 경우 4 + 4 = 8이므로 함수는 true를 반환해야 합니다.

해결 방법 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²) 시간 복잡도를 갖는 XNUMX차입니다.

솔루션 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;
};

솔루션의 기본은 위에서 본 것처럼 O(N)의 선형 시간 복잡도를 갖는 for 루프입니다.

함수의 두 번째 반복 부분은 배열에 지정된 값이 포함되어 있는지 여부에 따라 true 또는 false를 반환하는 JavaScript 메서드인 Array.prototype.include()입니다.

Array.prototype.includes()의 시간 복잡도를 파악하기 위해 MDN에서 제공하고 JavaScript로 작성된 폴리필을 보거나 Google V8(C++)과 같은 JavaScript 엔진의 소스 코드에 있는 메서드를 사용할 수 있습니다.

// 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이기 때문입니다.

공간 복잡성과 관련하여 길이가 원래 배열을 반영하는 추가 배열이 필요하므로(XNUMX 빼기, 예, 그러나 무시할 수 있음) O(N) 공간 복잡성이 발생합니다. 음, 메모리 사용량이 늘어나면 알고리즘의 효율성이 극대화됩니다.

이 기사가 비디오 인터뷰의 보충자료로 유용하길 바랍니다. 이는 간단한 문제가 다양한 양의 리소스(시간, 메모리)를 사용하여 여러 가지 방법으로 해결될 수 있음을 보여줍니다.

Skillbox는 다음을 권장합니다.

• 온라인 강좌 적용 "파이썬 데이터 분석가".
• 온라인 코스 "직업 프론트엔드 개발자".
• 실기 코스 "0에서 PRO로의 PHP 개발자".

출처 : habr.com