Doe't ik de prestaasjes fan algoritmen studearre, kaam ik dit tsjin . It jout net allinich in idee fan hoe't ynterviews wurde útfierd by grutte technologybedriuwen, mar lit jo ek begripe hoe't algoritmyske problemen sa effisjint mooglik wurde oplost.
Dit artikel is in soarte fan begelieding foar de fideo. Dêryn jou ik opmerkings oer alle werjûn oplossingen, plus myn eigen ferzje fan de oplossing yn JavaScript. De nuânses fan elk algoritme wurde ek besprutsen.
Wy herinnerje: foar alle lêzers fan "Habr" - in koarting fan 10 roebel by it ynskriuwen fan in Skillbox-kursus mei de promoasjekoade "Habr".
Skillbox advisearret: Praktyske kursus .
Probleemintwurding
Wy krije in oardere array en in spesifike wearde. It wurdt dan frege om in funksje te meitsjen dy't wier of falsk jout, ôfhinklik fan oft de som fan elke twa nûmers yn 'e array in opjûne wearde kin lykje.
Mei oare wurden, binne d'r twa heule getallen yn 'e array, x en y, dy't as byinoar tafoege binne gelyk oan de oantsjutte wearde?
Foarbyld A
As wy in array [1, 2, 4, 9] krije en de wearde is 8, sil de funksje falsk weromkomme, om't gjin twa nûmers yn 'e array oant 8 kinne optelle.
Foarbyld B
Mar as it in array [1, 2, 4, 4] is en de wearde is 8, moat de funksje wier weromkomme om't 4 + 4 = 8.
Oplossing 1: Brute krêft
Tiidkompleksiteit: O(N²).
Romtekompleksiteit: O(1).
De meast foar de hân lizzende betsjutting is it brûken fan in pear nestele 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;
};Dizze oplossing is net effisjint, om't it alle mooglike som fan twa eleminten yn 'e array kontrolearret en ek elk pear yndeksen twa kear fergeliket. (Bygelyks, as i = 1 en j = 2 is eins itselde as fergelykjen mei i = 2 en j = 1, mar yn dizze oplossing besykje wy beide opsjes).
Om't ús oplossing in pear nêste loops brûkt, is it kwadratysk mei O(N²) tiidkompleksiteit.
Oplossing 2: Binary Search
Tiidkompleksiteit: O(Nlog(N)).
Romtekompleksiteit: O(1).
Sûnt de arrays binne oardere, kinne wy sykje nei in oplossing mei help fan binêre sykopdracht. Dit is it meast effisjinte algoritme foar bestelde arrays. Binêre sykopdracht sels hat in rinnende tiid fan O(log(N)). Jo moatte lykwols noch in for-loop brûke om elk elemint te kontrolearjen tsjin alle oare wearden.
Hjir is hoe't in oplossing der útsjen kin. Om dingen dúdlik te meitsjen, brûke wy in aparte funksje om binêre sykjen te kontrolearjen. En ek de removeIndex () -funksje, dy't de ferzje fan 'e array weromjout minus de opjûne yndeks.
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;
};It algoritme begjint fan yndeks [0]. It makket dan in ferzje fan 'e array útsein de earste yndeks en brûkt binêre sykopdracht om te sjen oft ien fan' e oerbleaune wearden kin wurde tafoege oan 'e array om de winske som te produsearjen. Dizze aksje wurdt ien kear útfierd foar elk elemint yn 'e array.
De for-lus sels sil in lineêre tiidkompleksiteit fan O(N) hawwe, mar binnen de for-loop fiere wy in binêre sykopdracht út, dy't in totale tiidkompleksiteit fan O(Nlog(N) jout). Dizze oplossing is better as de foarige, mar der is noch romte foar ferbettering.
Oplossing 3: Lineêre tiid
Tiid kompleksiteit: O(N).
Romtekompleksiteit: O(1).
No sille wy it probleem oplosse, tinkend dat de array is sorteare. De oplossing is om twa nûmers te nimmen: ien oan it begjin en ien oan 'e ein. As it resultaat ferskilt fan 'e fereaske, feroarje dan de begjin- en einpunten.
Uteinlik sille wy de winske wearde tsjinkomme en wier weromkomme, of de start- en einpunten sille gearkomme en falsk weromkomme.
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;
};
No is alles goed, de oplossing liket optimaal te wêzen. Mar wa kin garandearje dat de array is besteld?
Wat dan?
Op it earste each koene wy de array gewoan earst bestelle en dan de boppesteande oplossing brûke. Mar hoe sil dit ynfloed hawwe op de útfieringstiid?
De bêste algoritme is quicksort mei tiid kompleksiteit O (Nlog (N)). As wy it brûke yn ús optimale oplossing, sil it syn prestaasjes feroarje fan O(N) nei O(Nlog(N)). Is it mooglik om in lineêre oplossing te finen mei in unorderde array?
Oplossing 4
Tiid kompleksiteit: O(N).
Romte kompleksiteit: O (N).
Ja, d'r is in lineêre oplossing; om dit te dwaan, moatte wy in nije array meitsje mei de list mei wedstriden wêr't wy nei sykje. De ôfruil hjir is mear ûnthâldgebrûk: it is de ienige oplossing yn it papier mei romtekompleksiteit grutter dan O(1).
As de earste wearde fan in opjûne array 1 is en de sykwearde 8 is, kinne wy de wearde 7 tafoegje oan 'e array "sykwearden".
Dan, as wy elk elemint fan 'e array ferwurkje, kinne wy de array fan "sykwearden" kontrolearje en sjen oft ien fan har gelyk is oan ús wearde. As ja, werom wier.
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 fan 'e oplossing is in for-loop, dy't, lykas wy hjirboppe seagen, in lineêre tiidkompleksiteit hat fan O(N).
It twadde iterative diel fan ús funksje is Array.prototype.include(), in JavaScript-metoade dy't wier of falsk sil weromjaan ôfhinklik fan oft de array de opjûne wearde befettet.
Foar in útfine de tiid kompleksiteit fan Array.prototype.includes (), kinne wy sjen op de polyfill levere troch MDN (en skreaun yn JavaScript) of brûk in metoade yn de boarne koade fan in JavaSkript motor lykas 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;
}
});
}Hjir is it iterative diel fan Array.prototype.include () de while-loop yn stap 7 dy't (hast) de hiele lingte fan 'e opjûne array trochgiet. Dit betsjut dat syn tiidkompleksiteit ek lineêr is. No, om't it altyd ien stap efter ús haadarray is, is de tiidkompleksiteit O (N + (N - 1)). Mei help fan Big O-notaasje ferienfâldigje wy it nei O(N) - om't it N is dy't de grutste ynfloed hat by it fergrutsjen fan de ynfiergrutte.
Oangeande romtlike kompleksiteit is in ekstra array nedich wêrfan de lingte de oarspronklike array spegelet (minus ien, ja, mar dat kin negearre wurde), wat resulteart yn O(N) romtlike kompleksiteit. No, ferhege ûnthâldgebrûk soarget foar maksimale effisjinsje fan it algoritme.
Ik hoopje dat jo it artikel nuttich fine as oanfolling op jo fideo-ynterview. It lit sjen dat in ienfâldich probleem kin wurde oplost op ferskate ferskillende manieren mei ferskillende hoemannichten boarnen brûkt (tiid, ûnthâld).
Skillbox advisearret:
- Oanfrege online kursus .
- Online kursus .
- Praktyske jierkursus .
Boarne: www.habr.com