Da jeg studerede algoritmers ydeevne, stødte jeg på denne . Den giver ikke kun indsigt i, hvordan jobsamtaler foregår i store teknologivirksomheder, men hjælper også med at forstå, hvordan algoritmiske opgaver løses mest effektivt.
Denne artikel er en form for ledsager til videoen. Her giver jeg kommentarer til alle de viste løsninger plus min egen version af løsningen i JavaScript. Jeg diskuterer også nuancerne af hver algoritme.
Vi minder om: til alle læsere af 'Habr' — rabat på 10.000 rubler ved tilmelding til et hvilket som helst Skillbox-kursus med rabatkoden 'Habr'.
Skillbox anbefaler: Praktisk kursus .
Problemformulering
Vi får et sorteret array og en bestemt værdi. Derefter bliver vi bedt om at oprette en funktion, der returnerer true eller false, afhængigt af om summen af to tal fra arrayet kan være lig med den angivne værdi.
Med andre ord, er der to heltal x og y i arrayet, der ved addition er lig med den angivne værdi?
Eksempel A
Hvis vi får arrayet [1, 2, 4, 9] og værdien 8, vil funktionen returnere false, fordi ingen to tal i arrayet kan give 8 i summen.
Eksempel B
Men hvis det er arrayet [1, 2, 4, 4] og værdien 8, skal funktionen returnere true, fordi 4 + 4 = 8.
Løsning 1. Brute force
Tidskompleksitet: O(N²).
Plads kompleksitet: O(1).
Den mest åbenlyse tilgang er at bruge et par indlejrede loops.
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 kan ikke kaldes effektiv, da den tjekker hver mulig sum af to elementer i arrayet og sammenligner hvert indekspar to gange. (For eksempel, når i = 1 og j = 2 — det er faktisk det samme som at sammenligne med i = 2 og j = 1, men denne løsning prøver begge muligheder).
Da vores løsning bruger et par indlejrede for-løkker, er den kvadratisk med tidskompleksitet O (N²).
Løsning 2. Binær søgning
Tidskompleksitet: O(Nlog(N)).
Plads kompleksitet: O(1).
Da arrayene er sorteret, kan vi søge efter en løsning ved hjælp af binær søgning. Dette er den mest effektive algoritme til sorterede arrays. Binær søgning i sig selv har en køretid på O (log (N)). Dog skal vi stadig bruge en for-løkke for at tjekke hvert element mod alle andre værdier.
Sådan kan løsningen se ud. For at gøre alt klart bruger vi en separat funktion til at kontrollere den binære søgning. Vi har også funktionen removeIndex(), som returnerer en version af arrayet uden det specificerede indeks.
const findSum = (arr, val) => {
for (let i = 0; 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]) {
start = pivot + 1;
};
pivot = Math.floor((start + end) / 2);
if (arr[pivot] === val) {
return true;
}
};
return false;
};Algoritmen starter ved indeks [0]. Derefter opretter den en version af arrayet, der ekskluderer det første indeks, og bruger den binære søgning til at kontrollere, om et af de resterende værdier kan tilføjes til arrayet for at opnå den ønskede sum. Denne handling udføres én gang for hvert element i arrayet.
Selve for-loopet vil have en lineær tidskompleksitet O(N), men inden i for-loopet udfører vi en binær søgning, hvilket giver en samlet tidskompleksitet på O(N log(N)). Denne løsning er bedre end den tidligere, men der er stadig plads til forbedring.
Løsning 3. Lineær tid
Tidskompleksitet: O(N).
Plads kompleksitet: O(1).
Nu vil vi løse opgaven med den viden, at arrayet er sorteret. Løsningen er at tage to tal: et i starten og et i slutningen. Hvis resultatet ikke er lig med det ønskede, så ændrer vi start- og slutpunktet.
Til slut møder vi enten den ønskede værdi og returnerer true, eller start- og slutpunkterne mødes, hvorefter vi returnerer false.
const findSum = (arr, val) => {
let start = 0;
let end = arr.length - 1;
while (start val) {
end -= 1;
} else if (sum < val) {
start += 1;
} else {
return true;
};
};
return false;
};Nu ser det godt ud, løsningen virker til at være optimal. Men hvem kan garantere, at arrayet var sorteret?
Hvad så?
Ved første øjekast kunne vi blot have sorteret arrayet først og derefter brugt ovenstående løsning. Men hvordan ville det påvirke køretiden?
Den bedste algoritme er hurtig sortering med tidskompleksitet O(N log(N)). Hvis vi bruger den i vores optimale løsning, vil den ændre sin præstation fra O(N) til O(N log(N)). Kan der findes en lineær løsning med et usorteret array?
Løsning 4
Tidskompleksitet: O(N).
Rumkompleksitet: O(N).
Ja, der lineære løsning eksisterer, for at gøre dette skal vi oprette et nyt array, der indeholder en liste over de match, vi leder efter. Kompromiset her ligger i en mere aktiv brug af hukommelse: dette er den eneste løsning i artiklen med en rumkompleksitet, der overstiger O (1).
Hvis den første værdi i dette array er 1, og den søgte værdi er 8, kan vi tilføje værdien 7 til arrayet "søgeværdier".
Derefter, ved at bearbejde hvert element i arrayet, kan vi kontrollere arrayet "søgeværdier" og se, om en af dem er lig med vores værdi. Hvis ja, returnerer vi 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;
};Basis for løsningen er en for-løkke, der, som vi har set tidligere, har en linear tidskompleksitet O (N).
Den anden iterative del af vores funktion er Array.prototype.include (), en JavaScript-metode, der vil returnere true eller false afhængigt af, om arrayet indeholder den angivne værdi.
For at finde ud af tidskompleksiteten af Array.prototype.includes (), kan vi se på den polyfill, der tilbydes af MDN (og skrevet i JavaScript), eller vi kan bruge metoden i kildekoden til JavaScript-motoren, 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 () en while-løkke på trin 7, der (næsten) krydser hele længden af det givne array. Dette betyder, at dens tidskompleksitet også er lineær. Og da den altid er et skridt bag vores hovedarray, er tidskompleksiteten lig med O (N + (N — 1)). Ved at bruge Big O Notation forenkler vi den til O (N) — fordi det er N, der har den største indflydelse, når indgangsstørrelsen øges.
Når det kommer til rumkompleksitet, kræver det yderligere et array, hvis længde afspejler det originale array (minus én, ja, men det kan ignoreres), hvilket fører til en rumkompleksitet på O (N). Det øgede brug af hukommelse sikrer den maksimale effektivitet af algoritmen.
Jeg håber, at artiklen vil være nyttig for dig som et supplement til videointerviewet. Den viser, at en simpel opgave kan løses på flere forskellige måder med varierende mængder af ressourcer (tid, hukommelse).
Skillbox anbefaler:
- Anvendt online-kursus .
- Online kursus .
- Praktisk års kursus .
Kilde: habr.com
