Kiam mi studis la agadon de algoritmoj, mi trovis ĉi tion . Ĝi ne nur donas ideon pri kiel intervjuoj estas faritaj ĉe grandaj teknologiaj korporacioj, sed ankaŭ permesas kompreni kiel algoritmaj problemoj estas solvitaj kiel eble plej efike.
Ĉi tiu artikolo estas speco de akompano al la video. En ĝi mi donas komentojn pri ĉiuj montritaj solvoj, krom mia propra versio de la solvo en JavaScript. La nuancoj de ĉiu algoritmo ankaŭ estas diskutitaj.
Ni memorigas vin: por ĉiuj legantoj de "Habr" - rabato de 10 000 rubloj kiam oni enskribas en iu ajn Skillbox-kurso per la reklamkodo "Habr".
Skillbox rekomendas: Praktika kurso .
Formulado de la problemo
Ni ricevas ordigitan tabelon kaj specifan valoron. Oni tiam petas krei funkcion kiu resendas vera aŭ malvera depende ĉu la sumo de iuj du nombroj en la tabelo povas egali antaŭfiksitan valoron.
Alivorte, ĉu estas du entjeroj en la tabelo, x kaj y, kiuj kiam kunigitaj egalas la specifitan valoron?
Ekzemplo A
Se ni ricevas tabelon [1, 2, 4, 9] kaj la valoro estas 8, la funkcio revenos malvera ĉar neniuj du nombroj en la tabelo povas sumi ĝis 8.
Ekzemplo B
Sed se ĝi estas tabelo [1, 2, 4, 4] kaj la valoro estas 8, la funkcio devus reveni vera ĉar 4 + 4 = 8.
Solvo 1: Bruta forto
Tempokomplekseco: O(N²).
Spaca komplekseco: O(1).
La plej evidenta signifo estas uzi paron da nestitaj maŝoj.
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;
};Ĉi tiu solvo ne estas efika ĉar ĝi kontrolas ĉiun eblan sumon de du elementoj en la tabelo kaj ankaŭ komparas ĉiun paron da indeksoj dufoje. (Ekzemple, kiam i = 1 kaj j = 2 estas fakte sama kiel kompari kun i = 2 kaj j = 1, sed en ĉi tiu solvo ni provas ambaŭ opciojn).
Ĉar nia solvo uzas paron de nestitaj por cikloj, ĝi estas kvadrata kun O(N²) tempokomplekseco.
Solvo 2: Binara Serĉo
Tempokomplekseco: O(Nlog(N)).
Spackomplekseco: O (1).
Ĉar la tabeloj estas ordigitaj, ni povas serĉi solvon uzante binaran serĉon. Ĉi tiu estas la plej efika algoritmo por ordigitaj tabeloj. Binara serĉo mem havas rultempon de O(log(N)). Tamen, vi ankoraŭ bezonas uzi for-buklon por kontroli ĉiun elementon kontraŭ ĉiuj aliaj valoroj.
Jen kiel solvo povus aspekti. Por klarigi aferojn, ni uzas apartan funkcion por kontroli binaran serĉon. Kaj ankaŭ la funkcio removeIndex(), kiu resendas la version de la tabelo minus la donita indekso.
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;
};La algoritmo komenciĝas de indekso [0]. Ĝi tiam kreas version de la tabelo ekskludante la unuan indekson kaj uzas binaran serĉon por vidi ĉu iu el la ceteraj valoroj povas esti aldonita al la tabelo por produkti la deziratan sumon. Ĉi tiu ago estas farita unufoje por ĉiu elemento en la tabelo.
La for-buklo mem havos linearan tempkompleksecon de O(N), sed ene de la for-buklo ni elfaras binaran serĉon, kiu donas totalan tempkompleksecon de O(Nlog(N)). Ĉi tiu solvo estas pli bona ol la antaŭa, sed ankoraŭ estas loko por plibonigo.
Solvo 3: Lineara tempo
Tempokomplekseco: O(N).
Spaca komplekseco: O(1).
Nun ni solvos la problemon, memorante, ke la tabelo estas ordigita. La solvo estas preni du nombrojn: unu ĉe la komenco kaj unu ĉe la fino. Se la rezulto diferencas de la postulata, tiam ŝanĝu la komencajn kaj finpunktojn.
Fine ni aŭ renkontos la deziratan valoron kaj revenos vera, aŭ la komencaj kaj finpunktoj konverĝos kaj revenos malvera.
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;
};
Nun ĉio estas en ordo, la solvo ŝajnas esti optimuma. Sed kiu povas garantii ke la tabelo estis mendita?
Kio do?
Unuavide, ni povus simple ordigi la tabelon unue kaj poste uzi la supran solvon. Sed kiel tio influos la ekzekuttempon?
La plej bona algoritmo estas rapidsortado kun tempokomplekseco O (Nlog (N)). Se ni uzas ĝin en nia optimuma solvo, ĝi ŝanĝos sian rendimenton de O(N) al O(Nlog(N)). Ĉu eblas trovi linearan solvon kun neordigita tabelo?
4 Solvo
Tempokomplekseco: O(N).
Spackomplekseco: O(N).
Jes, ekzistas linia solvo; por fari tion, ni devas krei novan tabelon enhavantan la liston de kongruoj, kiujn ni serĉas. La kompromiso ĉi tie estas pli da memoruzo: ĝi estas la nura solvo en la papero kun spackomplekseco pli granda ol O(1).
Se la unua valoro de donita tabelo estas 1 kaj la serĉvaloro estas 8, ni povas aldoni la valoron 7 al la tabelo "serĉaj valoroj".
Tiam, dum ni prilaboras ĉiun elementon de la tabelo, ni povas kontroli la tabelon de "serĉaj valoroj" kaj vidi ĉu unu el ili estas egala al nia valoro. Se jes, revenu vera.
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;
};La bazo de la solvo estas por buklo, kiu, kiel ni vidis supre, havas linearan tempokompleksecon de O(N).
La dua ripeta parto de nia funkcio estas Array.prototype.include(), JavaScript-metodo kiu resendos vera aŭ malvera depende ĉu la tabelo enhavas la donitan valoron.
Por eltrovi la tempkompleksecon de Array.prototype.includes(), ni povas rigardi la polyfill provizitan de MDN (kaj skribita en JavaScript) aŭ uzi metodon en la fontkodo de JavaScript-motoro kiel 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;
}
});
}Ĉi tie la ripeta parto de Array.prototype.include() estas la while-buklo en paŝo 7, kiu (preskaŭ) trairas la tutan longon de la donita tabelo. Ĉi tio signifas, ke ĝia tempokomplekseco ankaŭ estas linia. Nu, ĉar ĝi ĉiam estas unu paŝo malantaŭ nia ĉefa tabelo, la tempokomplekseco estas O (N + (N - 1)). Uzante Big O-Notacion, ni simpligas ĝin al O(N) - ĉar ĝi estas N kiu havas la plej grandan efikon kiam pliigas la eniggrandecon.
Koncerne spacan kompleksecon, necesas plia tabelo, kies longo spegulas la originan tabelon (minuso unu, jes, sed tio povas esti ignorita), rezultigante O(N) spacan kompleksecon. Nu, pliigita memoruzo certigas maksimuman efikecon de la algoritmo.
Mi esperas, ke vi trovos la artikolon utila kiel suplemento al via videointervjuo. Ĝi montras ke simpla problemo povas esti solvita en pluraj malsamaj manieroj kun malsamaj kvantoj de rimedoj uzataj (tempo, memoro).
Skillbox rekomendas:
- Aplikata interreta kurso .
- Interreta kurso .
- Praktika jarkurso .
fonto: www.habr.com