Nilipokuwa nikisoma utendaji wa algorithms, nilikutana na hii . Haitoi tu wazo la jinsi mahojiano yanafanywa katika mashirika makubwa ya teknolojia, lakini pia hukuruhusu kuelewa jinsi shida za algorithmic zinatatuliwa kwa ufanisi iwezekanavyo.
Nakala hii ni aina ya kuambatana na video. Ndani yake mimi hutoa maoni juu ya suluhisho zote zilizoonyeshwa, pamoja na toleo langu mwenyewe la suluhisho katika JavaScript. Nuances ya kila algorithm pia inajadiliwa.
Tunakukumbusha: kwa wasomaji wote wa "Habr" - punguzo la rubles 10 wakati wa kujiandikisha katika kozi yoyote ya Skillbox kwa kutumia msimbo wa uendelezaji wa "Habr".
Skillbox inapendekeza: Kozi ya vitendo .
Taarifa ya tatizo
Tunapewa safu iliyoagizwa na thamani maalum. Kisha inaombwa kuunda chaguo la kukokotoa ambalo hurejesha kweli au si kweli kulingana na ikiwa jumla ya nambari zozote mbili kwenye mkusanyiko zinaweza kuwa sawa na thamani fulani.
Kwa maneno mengine, kuna nambari mbili kamili katika safu, x na y, ambazo zinapojumuishwa pamoja zinalingana na dhamana iliyobainishwa?
Mfano A
Ikiwa tutapewa safu [1, 2, 4, 9] na thamani ni 8, chaguo la kukokotoa litarudi kuwa sivyo kwa sababu hakuna nambari mbili katika safu zinazoweza kuongeza hadi 8.
Mfano B
Lakini ikiwa ni safu [1, 2, 4, 4] na thamani ni 8, chaguo la kukokotoa linapaswa kurudi kweli kwa sababu 4 + 4 = 8.
Suluhisho la 1: Nguvu isiyo na nguvu
Utata wa wakati: O(NΒ²).
Utata wa nafasi: O(1).
Maana ya wazi zaidi ni kutumia jozi ya vitanzi vilivyowekwa.
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;
};Suluhisho hili halifanyi kazi kwa sababu hukagua kila jumla inayowezekana ya vitu viwili kwenye safu na pia inalinganisha kila jozi ya fahirisi mara mbili. (Kwa mfano, wakati i = 1 na j = 2 kwa kweli ni sawa na kulinganisha na i = 2 na j = 1, lakini katika suluhisho hili tunajaribu chaguo zote mbili).
Kwa sababu suluhisho letu hutumia jozi ya viota kwa vitanzi, ni ya quadratic na utata wa wakati wa O(NΒ²).
Suluhisho la 2: Utafutaji wa Binary
Utata wa wakati: O(Nlog(N)).
Utata wa nafasi: O(1).
Kwa kuwa safu zimepangwa, tunaweza kutafuta suluhisho kwa kutumia utaftaji wa binary. Hii ndiyo algoriti yenye ufanisi zaidi kwa safu zilizopangwa. Utafutaji wa binary wenyewe una wakati wa O(logi(N)). Walakini, bado unahitaji kutumia kitanzi kuangalia kila kipengele dhidi ya maadili mengine yote.
Hii ndio suluhisho linaweza kuonekana kama. Ili kuweka mambo wazi, tunatumia kipengele tofauti kudhibiti utafutaji wa binary. Na pia removeIndex() kazi, ambayo inarudisha toleo la safu kutoa faharisi iliyotolewa.
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;
};Algorithm inaanza kutoka index [0]. Kisha hutengeneza toleo la mkusanyiko bila kujumuisha faharasa ya kwanza na hutumia utafutaji wa binary ili kuona kama thamani zozote zilizosalia zinaweza kuongezwa kwenye mkusanyiko ili kutoa jumla inayohitajika. Kitendo hiki kinafanywa mara moja kwa kila kipengele katika safu.
Kitanzi chenyewe kitakuwa na ugumu wa wakati wa O(N), lakini ndani ya kitanzi tunafanya utaftaji wa binary, ambao unatoa ugumu wa jumla wa wakati wa O(Nlog(N)). Suluhisho hili ni bora kuliko la awali, lakini bado kuna nafasi ya kuboresha.
Suluhisho la 3: Muda wa mstari
Utata wa wakati: O(N).
Utata wa nafasi: O(1).
Sasa tutatatua tatizo, tukikumbuka kwamba safu imepangwa. Suluhisho ni kuchukua nambari mbili: moja mwanzoni na moja mwishoni. Ikiwa matokeo yanatofautiana na yanayotakiwa, basi ubadilishe pointi za kuanzia na za mwisho.
Hatimaye tutakumbana na thamani inayotakikana na kurudisha ukweli, au pointi za kuanzia na za mwisho zitaungana na kurudi sivyo.
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;
};
Sasa kila kitu kiko sawa, suluhisho linaonekana kuwa bora. Lakini ni nani anayeweza kuhakikisha kwamba safu iliamriwa?
Nini sasa?
Kwa mtazamo wa kwanza, tungeweza kuagiza tu safu kwanza na kisha kutumia suluhisho hapo juu. Lakini hii itaathirije wakati wa utekelezaji?
Algorithm bora ni ya upangaji haraka na ugumu wa wakati O (Nlog (N)). Ikiwa tutaitumia katika suluhisho letu bora zaidi, itabadilisha utendakazi wake kutoka O(N) hadi O(Nlog(N)). Inawezekana kupata suluhisho la mstari na safu isiyopangwa?
Suluhisho la 4
Utata wa wakati: O(N).
Utata wa nafasi: O(N).
Ndio, kuna suluhisho la mstari; ili kufanya hivi, tunahitaji kuunda safu mpya iliyo na orodha ya mechi ambazo tunatafuta. Biashara hapa ni utumiaji wa kumbukumbu zaidi: ndio suluhisho pekee kwenye karatasi iliyo na ugumu wa nafasi kubwa kuliko O (1).
Ikiwa thamani ya kwanza ya safu fulani ni 1 na thamani ya utafutaji ni 8, tunaweza kuongeza thamani ya 7 kwenye safu ya "thamani za utafutaji".
Kisha, tunapochakata kila kipengele cha safu, tunaweza kuangalia safu ya "thamani za utafutaji" na kuona ikiwa mojawapo ni sawa na thamani yetu. Ikiwa ndio, rudisha ukweli.
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;
};Msingi wa suluhisho ni kitanzi, ambacho, kama tulivyoona hapo juu, kina ugumu wa wakati wa O (N).
Sehemu ya pili ya marudio ya chaguo zetu za kukokotoa ni Array.prototype.include(), mbinu ya JavaScript ambayo itarejesha kuwa kweli au si kweli kulingana na kama safu ina thamani iliyotolewa.
Ili kubaini utata wa wakati wa Array.prototype.includes(), tunaweza kuangalia ujazo wa aina nyingi unaotolewa na MDN (na kuandikwa katika JavaScript) au kutumia mbinu katika msimbo wa chanzo wa injini ya JavaScript kama vile 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;
}
});
}Hapa sehemu inayojirudia ya Array.prototype.include() ni kitanzi cha wakati katika hatua ya 7 ambacho (karibu) hupitia urefu wote wa safu iliyotolewa. Hii inamaanisha kuwa ugumu wake wa wakati pia ni wa mstari. Naam, kwa kuwa daima ni hatua moja nyuma ya safu yetu kuu, utata wa wakati ni O (N + (N - 1)). Kwa kutumia Big O Notation, tunairahisisha hadi O(N) - kwa sababu ni N ambayo ina athari kubwa wakati wa kuongeza ukubwa wa ingizo.
Kuhusu uchangamano wa anga, safu ya ziada inahitajika ambayo urefu wake unaakisi safu asili (ondoa moja, ndio, lakini hiyo inaweza kupuuzwa), na kusababisha ugumu wa anga wa O(N). Kweli, kuongezeka kwa utumiaji wa kumbukumbu huhakikisha ufanisi wa juu wa algorithm.
Natumai utapata nakala hiyo kuwa muhimu kama nyongeza ya mahojiano yako ya video. Inaonyesha kwamba tatizo rahisi linaweza kutatuliwa kwa njia kadhaa tofauti na kiasi tofauti cha rasilimali zinazotumiwa (wakati, kumbukumbu).
Skillbox inapendekeza:
- Kozi iliyotumika mtandaoni .
- Kozi ya mkondoni .
- Kozi ya mwaka wa vitendo .
Chanzo: mapenzi.com