Att lösa ett problem från en Google-intervju i JavaScript: 4 olika sätt

När jag studerade algoritmernas prestanda stötte jag på detta det här är en video av en låtsasintervju med Google. Det ger dig inte bara en uppfattning om hur intervjuer genomförs på stora teknikföretag, utan det låter dig också förstå hur algoritmiska problem löses, och på ett så effektivt sätt som möjligt.

Den här artikeln är ett slags ackompanjemang till videon. I den ger jag kommentarer om alla lösningar som visas, plus min egen version av lösningen i JavaScript. Nyanserna i varje algoritm diskuteras också.

Påminnelse: för alla läsare av "Habr" - en rabatt på 10 000 rubel när du anmäler dig till någon Skillbox-kurs med hjälp av "Habr"-kampanjkoden.

Skillbox rekommenderar: Praktisk kurs "Mobilutvecklare PRO".

Problem uttalande

Vi får en ordnad array och ett specifikt värde. De uppmanas sedan att skapa en funktion som returnerar sant eller falskt beroende på om summan av två valfria tal i matrisen kan vara lika med ett givet värde.

Med andra ord, finns det två heltal x och y i arrayen som, när de adderas, är lika med det angivna värdet?

Exempel A

Om vi ​​får en array [1, 2, 4, 9] och värdet 8, kommer funktionen att returnera false eftersom inga två tal i arrayen kan lägga till 8.

Exempel B

Men om det är en array [1, 2, 4, 4] och värdet är 8, bör funktionen returnera sant eftersom 4 + 4 = 8.

Lösning 1: Brute force

Tidskomplexitet: O(N²).
Rymdkomplexitet: O(1).

Den mest uppenbara betydelsen är användningen av ett par kapslade slingor.

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

Denna lösning är inte effektiv eftersom den kontrollerar varje möjlig summa av två element i arrayen, och jämför också varje par av index två gånger. (Till exempel, när i = 1 och j = 2 är det faktiskt samma sak som att jämföra med i = 2 och j = 1, men i den här lösningen försöker vi båda alternativen.)

Eftersom vår lösning använder ett par kapslade för loopar, är den kvadratisk med tidskomplexiteten O(N²).

Lösning 2. Binär sökning

Tidskomplexitet: O(Nlog(N)).
Rymdkomplexitet: O(1).

Eftersom arrayerna är ordnade kan vi söka efter en lösning med hjälp av binär sökning. Detta är den mest effektiva algoritmen för sorterade arrayer. Binär sökning i sig har en körtid på O(log(N)). Du måste dock fortfarande använda en for-loop för att kontrollera varje element mot alla andra värden.

Så här kan lösningen se ut. För att göra saker tydligt använder vi en separat funktion för att styra binär sökning. Och även funktionen removeIndex(), som returnerar versionen av arrayen minus det givna indexet.

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

Algoritmen utgår från index [0]. Den skapar sedan en version av arrayen exklusive det första indexet och använder binär sökning för att se om något av de återstående värdena kan läggas till arrayen för att få den önskade summan. Denna åtgärd utförs en gång för varje element i arrayen.

Själva for-slingan kommer att ha en linjär tidskomplexitet på O(N), men inuti for-slingan gör vi en binär sökning, vilket ger en total tidskomplexitet på O(Nlog(N)). Denna lösning är bättre än den tidigare, men det finns fortfarande utrymme för förbättringar.

Lösning 3. Linjär tid

Tidskomplexitet: O(N).
Rymdkomplexitet: O(1).

Nu ska vi lösa problemet och komma ihåg att arrayen är sorterad. Lösningen är att ta två siffror: ett i början och ett i slutet. Om resultatet skiljer sig från det som krävs, ändrar vi start- och slutpunkterna.

Så småningom kommer vi antingen att möta det önskade värdet och returnera sant, eller så kommer start- och slutpunkterna att konvergera och returnera falskt.

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

Nu är allt bra, lösningen verkar vara optimal. Men vem kommer att garantera att arrayen var beställd?

Vad händer då?

Vid första anblicken kunde vi helt enkelt sortera arrayen först och sedan använda lösningen ovan. Men hur kommer detta att påverka genomförandetiden?

Den bästa algoritmen är quicksort med tidskomplexitet O(Nlog(N)). Om vi ​​använder den i vår optimala lösning kommer den att ändra dess prestanda från O(N) till O(Nlog(N)). Är det möjligt att hitta en linjär lösning med en oordnad array?

Lösning 4

Tidskomplexitet: O(N).
Utrymmeskomplexitet: O(N).

Ja, det finns en linjär lösning, den kräver att man skapar en ny array som innehåller listan över matchningar vi letar efter. Avvägningen här är mer minnesanvändning: detta är den enda lösningen i tidningen med rymdkomplexitet större än O(1).

Om det första värdet i den givna arrayen är 1 och sökvärdet är 8, kan vi lägga till värdet 7 till arrayen "search values".

Sedan, när vi bearbetar varje element i arrayen, kan vi kontrollera arrayen av "sökvärden" och se om ett av dem är lika med vårt värde. Om ja, returnera sant.

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

Kärnan i lösningen är for-loopen, som, som vi såg ovan, har linjär tidskomplexitet O(N).

Den andra iterationsdelen av vår funktion är Array.prototype.include() , en JavaScript-metod som returnerar true eller false beroende på om arrayen innehåller det givna värdet.

För att ta reda på tidskomplexiteten för Array.prototype.includes() kan vi överväga polyfillen som tillhandahålls av MDN (och skriven i JavaScript), eller använda metoden i källkoden för en JavaScript-motor som 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;
    }
  });
}

Här är iterationsdelen av Array.prototype.include() while-loopen i steg 7, som (nästan) korsar hela längden av den givna arrayen. Detta innebär att dess tidskomplexitet också är linjär. Tja, eftersom det alltid är ett steg bakom vår huvudmatris, är tidskomplexiteten O(N + (N - 1)). Med hjälp av Big O Notation förenklar vi det till O(N) - eftersom det är N som har störst inverkan när indatastorleken ökar.

När det gäller rymdkomplexitet behövs en extra matris vars längd speglar den ursprungliga matrisen (minus ett, ja, men det kan ignoreras), vilket resulterar i en rymdkomplexitet på O(N). Tja, ökad minnesanvändning säkerställer maximal effektivitet hos algoritmen.

Jag hoppas att du tycker att den här artikeln är användbar som ett tillägg till din videointervju. Den visar att ett enkelt problem kan lösas på flera olika sätt med olika mängd resurser som används (tid, minne).

Skillbox rekommenderar:

• Tillämpad onlinekurs "Python Data Analyst".
• Onlinekurs "Profession frontend-utvecklare".
• Praktisk årskurs "PHP-utvecklare från 0 till PRO".

Källa: will.com