Toen ik me bezig hield met het bestuderen van de prestaties van algoritmes, kwam ik deze video tegen Het geeft niet alleen een idee van hoe de interviews bij grote technologiebedrijven verlopen, maar ook inzicht in hoe algoritmische problemen effectief kunnen worden opgelost.
Dit artikel is een soort begeleider bij de video. Ik geef commentaar op alle getoonde oplossingen plus mijn eigen versie van de oplossing in JavaScript. Ook worden de nuances van elk algoritme besproken.
Ter herinnering: voor alle lezers van «Habr» — een korting van 10.000 roebel bij inschrijving voor elke cursus van Skillbox met de promocode «Habr».
Skillbox raadt aan: Praktische cursus .
Taakstelling
We krijgen een gesorteerde array en een bepaalde waarde. Vervolgens wordt gevraagd om een functie te creëren die true of false retourneert, afhankelijk van of de som van twee getallen uit de array gelijk kan zijn aan de gegeven waarde.
Met andere woorden, zijn er in de array twee gehele getallen x en y die samen de opgegeven waarde geven?
Voorbeeld A
Als we de array [1, 2, 4, 9] en de waarde 8 hebben gegeven, zal de functie false retourneren, omdat geen twee getallen uit de array samen 8 kunnen vormen.
Voorbeeld B
Maar als het de array [1, 2, 4, 4] en de waarde 8 is, moet de functie true retourneren, omdat 4 + 4 = 8.
Oplossing 1. Brute Force
Tijdcomplexiteit: O(N²).
Ruimtecomplexiteit: O(1).
De meest voor de hand liggende aanpak is het gebruik van een paar geneste lussen.
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;
};Deze oplossing kan niet efficiënt worden genoemd, omdat deze elke mogelijke som van twee elementen in de array controleert en ook elke indexpaar twee keer vergelijkt. (Bijvoorbeeld, wanneer i = 1 en j = 2 – dit is feitelijk hetzelfde als vergelijken met i = 2 en j = 1, maar in deze oplossing proberen we beide varianten).
Aangezien onze oplossing een paar geneste for-lussen gebruikt, is het kwadratisch met een tijdcomplexiteit van O(N²).
Oplossing 2. Binaire Zoektocht
Tijdcomplexiteit: O(N log(N)).
Ruimtecomplexiteit: O(1).
Aangezien de arrays gesorteerd zijn, kunnen we zoeken naar een oplossing met behulp van binaire zoektechniek. Dit is het meest efficiënte algoritme voor gesorteerde arrays. De binaire zoektechniek zelf heeft een uitvoeringstijd van O(log(N)). Echter, er is nog steeds een for-lus nodig om elk element tegen alle andere waarden te controleren.
Zo kan een oplossing eruit zien. Om alles duidelijk te maken, gebruiken we een aparte functie voor het beheer van de binaire zoekopdracht. Daarnaast is er de functie removeIndex(), die een versie van de array retourneert, minus de opgegeven index.
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;
};Het algoritme begint met index [0]. Vervolgens maakt het een versie van de array, waarbij de eerste index wordt uitgesloten, en gebruikt het binaire zoekopdracht om te controleren of een van de overgebleven waarden aan de array kan worden toegevoegd om de gewenste som te bereiken. Deze actie wordt eenmaal voor elk element in de array uitgevoerd.
De for-lus op zichzelf heeft een lineaire tijdscomplexiteit van O(N), maar binnen de for-lus voeren we een binaire zoekopdracht uit, wat leidt tot een totale tijdscomplexiteit van O(Nlog(N)). Deze oplossing is beter dan de vorige, maar er is nog ruimte voor verbetering.
Oplossing 3. Lineaire tijd
Tijdscomplexiteit: O(N).
Ruimtecomplexiteit: O(1).
We gaan nu het probleem oplossen, met in gedachten dat de array gesorteerd is. De oplossing bestaat uit het nemen van twee getallen: één aan het begin en één aan het einde. Als het resultaat niet overeenkomt met wat nodig is, verwisselen we het begin- en eindpunt.
Uiteindelijk zullen we ofwel de gewenste waarde tegenkomen en true retourneren, of de begin- en eindpunten zullen samensmelten en false retourneren.
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 is alles in orde, de oplossing lijkt optimaal. Maar wie geeft de garantie dat de array gesorteerd was?
Wat nu?
Op het eerste gezicht zouden we de array eerst gewoon kunnen sorteren en dan de bovenstaande oplossing kunnen gebruiken. Maar hoe beïnvloedt dit de uitvoeringstijd?
Het beste algoritme is quicksort met een tijdscomplexiteit van O(Nlog(N)). Als we dit gebruiken in onze optimale oplossing, verandert de prestaties van O(N) naar O(Nlog(N)). Is het mogelijk om een lineaire oplossing te vinden met een niet-gesorteerde array?
Oplossing 4
Tijdscomplexiteit: O(N).
Ruimtecomplexiteit: O(N).
Ja, er bestaat een lineaire oplossing. Hiervoor moet je een nieuwe array creëren die de lijst van overeenkomsten bevat die we zoeken. Het compromis hier is dat je meer geheugen gebruikt: dit is de enige oplossing in het artikel met een ruimtelijke complexiteit die hoger is dan O(1).
Als de eerste waarde van deze array gelijk is aan 1 en de gezochte waarde gelijk is aan 8, kunnen we de waarde 7 aan de array 'zoekwaarden' toevoegen.
Vervolgens kunnen we, terwijl we elk element van de array verwerken, de array 'zoekwaarden' controleren en kijken of een van hen gelijk is aan onze waarde. Als dat zo is, geven we true terug.
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;
};De basis van de oplossing is de for-lus, die, zoals we eerder hebben gezien, een lineaire tijdcomplexiteit O(N) heeft.
Het tweede iteratieve deel van onze functie is Array.prototype.include(), een JavaScript-methode die true of false retourneert, afhankelijk van of de array de opgegeven waarde bevat.
Om de tijdcomplexiteit van Array.prototype.includes() te bepalen, kunnen we de polyfill bekijken die door MDN wordt verstrekt (geschreven in JavaScript) of gebruikmaken van de methode in de brontekst van de JavaScript-engine, zoals 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;
}
});
}Hier is het iteratieve deel van Array.prototype.include() een while-lus op stap 7, die (bijna) de gehele lengte van de gegeven array doorloopt. Dit betekent dat de tijdcomplexiteit ook lineair is. Aangezien deze altijd één stap achter ons hoofdarray ligt, is de tijdcomplexiteit O(N + (N - 1)). Door gebruik te maken van de Big O-notatie, vereenvoudigen we dit tot O(N) — omdat N de grootste invloed heeft bij het vergroten van de invoergrootte.
Wat betreft de ruimtelijke complexiteit, heb je een extra array nodig waarvan de lengte overeenkomt met de oorspronkelijke array (min één, ja, maar dat kan worden genegeerd), wat leidt tot een ruimtelijke complexiteit van O(N). Het verhoogde geheugengebruik zorgt voor maximale efficiëntie van het algoritme.
Ik hoop dat het artikel nuttig voor je is als aanvulling op de video-interview. Het laat zien dat een eenvoudige taak op verschillende manieren kan worden opgelost met verschillende hoeveelheden gebruikte middelen (tijd, geheugen).
Skillbox raadt aan:
- Toegepaste online cursus .
- Online cursus .
- Praktische jaaropleiding .
Bron: habr.com
