🥇Løsning af et problem fra et Google-interview i JavaScript: 4 forskellige måder

Da jeg studerede effektiviteten af algoritmer, stødte jeg på dette Dette er en video af et Google mock interview.. Det giver ikke kun en idé om, hvordan interviews udføres hos store teknologivirksomheder, men giver dig også mulighed for at forstå, hvordan algoritmiske problemer løses så effektivt som muligt.

Denne artikel er en slags akkompagnement til videoen. I den giver jeg kommentarer til alle de viste løsninger, plus min egen version af løsningen i JavaScript. Nuancerne i hver algoritme diskuteres også.

Påmindelse: for alle læsere af "Habr" - en rabat på 10 rubler ved tilmelding til ethvert Skillbox-kursus ved hjælp af "Habr"-kampagnekoden.

Skillbox anbefaler: Praktisk kursus "Mobiludvikler PRO".

Formulering af problemet

Vi får et ordnet array og en bestemt værdi. Det bliver derefter bedt om at oprette en funktion, der returnerer sand eller falsk afhængigt af, om summen af to tal i matrixen kan svare til en given værdi.

Med andre ord, er der to heltal i matrixen, x og y, som når de lægges sammen er lig med den angivne værdi?

Eksempel A

Hvis vi får et array [1, 2, 4, 9], og værdien er 8, vil funktionen returnere falsk, fordi ingen to tal i arrayet kan summere op til 8.

Eksempel B

Men hvis det er et array [1, 2, 4, 4], og værdien er 8, skulle funktionen returnere sand, fordi 4 + 4 = 8.

Løsning 1: Brut force

Tidskompleksitet: O(N²).
Rumkompleksitet: O(1).

Den mest åbenlyse betydning er at bruge et par indlejrede løkker.

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

Denne løsning er ikke effektiv, fordi den kontrollerer enhver mulig sum af to elementer i arrayet og sammenligner også hvert par af indekser to gange. (For eksempel, når i = 1 og j = 2 er faktisk det samme som at sammenligne med i = 2 og j = 1, men i denne løsning prøver vi begge muligheder).

Fordi vores løsning bruger et par indlejrede for loops, er den kvadratisk med O(N²) tidskompleksitet.

Løsning 2: Binær søgning

Tidskompleksitet: O(Nlog(N)).
Rumkompleksitet: O(1).

Da arrays er ordnet, kan vi søge efter en løsning ved hjælp af binær søgning. Dette er den mest effektive algoritme til ordnede arrays. Binær søgning i sig selv har en køretid på O(log(N)). Du skal dog stadig bruge en for-løkke for at kontrollere hvert element mod alle andre værdier.

Sådan kan en løsning se ud. For at gøre tingene klart, bruger vi en separat funktion til at styre binær søgning. Og også removeIndex()-funktionen, som returnerer versionen af arrayet minus det givne indeks.

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 starter fra indeks [0]. Derefter opretter den en version af arrayet eksklusive det første indeks og bruger binær søgning for at se, om nogen af de resterende værdier kan tilføjes til arrayet for at producere den ønskede sum. Denne handling udføres én gang for hvert element i arrayet.

Selve for-løkken vil have en lineær tidskompleksitet på O(N), men inde i for-løkken udfører vi en binær søgning, som giver en samlet tidskompleksitet på O(Nlog(N)). Denne løsning er bedre end den forrige, men der er stadig plads til forbedringer.

Løsning 3: Lineær tid

Tidskompleksitet: O(N).
Rumkompleksitet: O(1).

Nu vil vi løse problemet og huske, at arrayet er sorteret. Løsningen er at tage to tal: et i begyndelsen og et i slutningen. Hvis resultatet afviger fra det påkrævede, skal du ændre start- og slutpunkterne.

Til sidst vil vi enten støde på den ønskede værdi og returnere sand, eller start- og slutpunkterne vil konvergere og returnere falsk.

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 er alt i orden, løsningen ser ud til at være optimal. Men hvem kan garantere, at arrayet blev bestilt?

Hvad så?

Ved første øjekast kunne vi simpelthen have bestilt arrayet først og derefter brugt løsningen ovenfor. Men hvordan vil dette påvirke udførelsestiden?

Den bedste algoritme er quicksort med tidskompleksitet O (Nlog (N)). Hvis vi bruger det i vores optimale løsning, vil det ændre sin ydeevne fra O(N) til O(Nlog(N)). Er det muligt at finde en lineær løsning med et uordnet array?

4 Solution

Tidskompleksitet: O(N).
Rumkompleksitet: O(N).

Ja, der er en lineær løsning; for at gøre dette skal vi oprette et nyt array, der indeholder listen over matches, som vi leder efter. Afvejningen her er mere hukommelsesbrug: det er den eneste løsning i papiret med rumkompleksitet større end O(1).

Hvis den første værdi af en given matrix er 1, og søgeværdien er 8, kan vi tilføje værdien 7 til "search values"-arrayet.

Når vi derefter behandler hvert element i arrayet, kan vi kontrollere arrayet af "søgeværdier" og se, om en af dem er lig med vores værdi. Hvis ja, returner sandt.

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

Grundlaget for løsningen er en for-løkke, der, som vi så ovenfor, har en lineær tidskompleksitet på O(N).

Den anden iterative del af vores funktion er Array.prototype.include(), en JavaScript-metode, der returnerer true eller false afhængigt af, om arrayet indeholder den givne værdi.

For at finde ud af tidskompleksiteten af Array.prototype.includes(), kan vi se på polyfillet leveret af MDN (og skrevet i JavaScript) eller bruge en metode i kildekoden til en JavaScript-motor så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;
    }
  });
}

Her er den iterative del af Array.prototype.include() while-løkken i trin 7, der (næsten) krydser hele længden af det givne array. Det betyder, at dens tidskompleksitet også er lineær. Nå, da det altid er et trin bag vores hovedarray, er tidskompleksiteten O (N + (N - 1)). Ved hjælp af Big O Notation forenkler vi det til O(N) - fordi det er N, der har størst indflydelse, når inputstørrelsen øges.

Med hensyn til rumlig kompleksitet er der behov for et ekstra array, hvis længde afspejler det originale array (minus en, ja, men det kan ignoreres), hvilket resulterer i O(N) rumlig kompleksitet. Nå, øget hukommelsesforbrug sikrer maksimal effektivitet af algoritmen.

Jeg håber, du finder artiklen nyttig som supplement til dit videointerview. Den viser, at et simpelt problem kan løses på flere forskellige måder med forskellige mængder ressourcer, der bruges (tid, hukommelse).

Skillbox anbefaler:

Anvendt online kursus "Python Data Analyst".

Online kursus "Profession frontend udvikler".

Praktisk årskursus "PHP-udvikler fra 0 til PRO".

Kilde: www.habr.com

Løsning af et Google-interviewproblem i JavaScript: 4 forskellige måder

Formulering af problemet

Hvad så?

Tilføj en kommentar Annuller svar