Решаване на проблем от интервю в Google в JavaScript: 4 различни начина

Когато изучавах производителността на алгоритмите, попаднах на това Това е видео на фиктивно интервю в Google.. Той не само дава представа как се провеждат интервютата в големите технологични корпорации, но също така ви позволява да разберете как алгоритмичните проблеми се решават възможно най-ефективно.

Тази статия е вид съпровод към видеото. В него предоставям коментари за всички показани решения, плюс моя собствена версия на решението в JavaScript. Обсъждат се и нюансите на всеки алгоритъм.

Напомняме ви: за всички читатели на "Habr" - отстъпка от 10 000 рубли при записване във всеки курс Skillbox, използвайки промоционалния код на "Habr".

Skillbox препоръчва: Практически курс „Мобилен разработчик PRO“.

Проблем изявление

Даден ни е подреден масив и конкретна стойност. След това се иска да се създаде функция, която връща true или false в зависимост от това дали сумата от произволни две числа в масива може да е равна на дадена стойност.

С други думи, има ли две цели числа в масива, x и y, които, когато се съберат заедно, са равни на указаната стойност?

Пример А

Ако ни е даден масив [1, 2, 4, 9] и стойността е 8, функцията ще върне false, защото никакви две числа в масива не могат да дадат сбор до 8.

Пример Б

Но ако това е масив [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(), можем да разгледаме polyfill, предоставен от MDN (и написан на 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() е цикълът while в стъпка 7, който (почти) преминава през цялата дължина на дадения масив. Това означава, че неговата времева сложност също е линейна. Е, тъй като винаги е една стъпка зад основния ни масив, времевата сложност е O (N + (N - 1)). Използвайки Big O нотация, ние го опростяваме до O(N) - защото N има най-голямо въздействие при увеличаване на входния размер.

По отношение на пространствената сложност е необходим допълнителен масив, чиято дължина отразява оригиналния масив (минус едно, да, но това може да се игнорира), което води до O(N) пространствена сложност. Е, повишеното използване на паметта гарантира максимална ефективност на алгоритъма.

Надявам се да намерите статията за полезна като допълнение към вашето видео интервю. Той показва, че един прост проблем може да бъде решен по няколко различни начина с различни количества използвани ресурси (време, памет).

Skillbox препоръчва:

• Приложен онлайн курс „Анализатор на данни на Python“.
• Онлайн курс „Професия фронтенд разработчик“.
• Практически годишен курс „PHP разработчик от 0 до PRO“.

Източник: www.habr.com