Pan oeddwn yn astudio perfformiad algorithmau, deuthum ar draws hyn . Mae nid yn unig yn rhoi syniad o sut y cynhelir cyfweliadau mewn corfforaethau technoleg mawr, ond mae hefyd yn caniatáu ichi ddeall sut mae problemau algorithmig yn cael eu datrys mor effeithlon â phosibl.
Mae'r erthygl hon yn fath o gyfeiliant i'r fideo. Ynddo rhoddaf sylwadau ar yr holl atebion a ddangosir, ynghyd â fy fersiwn fy hun o'r datrysiad yn JavaScript. Trafodir naws pob algorithm hefyd.
Rydym yn atgoffa: i holl ddarllenwyr "Habr" - gostyngiad o 10 rubles wrth gofrestru ar unrhyw gwrs Skillbox gan ddefnyddio'r cod hyrwyddo "Habr".
Mae Skillsbox yn argymell: Cwrs ymarferol .
Datganiad o'r broblem
Rhoddir arae drefnus i ni a gwerth penodol. Yna gofynnir i chi greu ffwythiant sy'n dychwelyd yn wir neu'n anghywir yn dibynnu a all swm unrhyw ddau rif yn yr arae fod yn hafal i werth penodol.
Mewn geiriau eraill, a oes dau gyfanrif yn yr arae, x ac y, sydd o'u hadio at ei gilydd yn hafal i'r gwerth penodedig?
Enghraifft A
Os rhoddir arae i ni [1, 2, 4, 9] a'r gwerth yw 8, bydd y ffwythiant yn dychwelyd yn ffug oherwydd ni all unrhyw ddau rif yn yr arae adio i 8.
Enghraifft B
Ond os yw'n arae [1, 2, 4, 4] a'r gwerth yn 8, dylai'r ffwythiant ddychwelyd yn wir oherwydd 4 + 4 = 8.
Ateb 1: Grym 'n Ysgrublaidd
Cymhlethdod amser: O(N²).
Cymhlethdod gofod: O(1).
Yr ystyr mwyaf amlwg yw defnyddio pâr o ddolenni nythu.
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;
};Nid yw'r datrysiad hwn yn effeithlon oherwydd ei fod yn gwirio pob swm posibl o ddwy elfen yn yr arae a hefyd yn cymharu pob pâr o fynegeion ddwywaith. (Er enghraifft, pan fo i = 1 a j = 2 mewn gwirionedd yr un peth â chymharu ag i = 2 a j = 1, ond yn yr ateb hwn rydyn ni'n rhoi cynnig ar y ddau opsiwn).
Oherwydd bod ein datrysiad yn defnyddio pâr o nythu ar gyfer dolenni, mae'n gwadratig gyda chymhlethdod amser O(N²).
Ateb 2: Chwiliad Deuaidd
Cymhlethdod amser: O(Nlog(N)).
Cymhlethdod gofod: O(1).
Gan fod yr araeau yn cael eu harchebu, gallwn chwilio am ateb gan ddefnyddio chwiliad deuaidd. Dyma'r algorithm mwyaf effeithlon ar gyfer araeau archebedig. Mae gan chwiliad deuaidd ei hun amser rhedeg o O(log(N)). Fodd bynnag, mae angen i chi ddefnyddio dolen for i wirio pob elfen yn erbyn pob gwerth arall.
Dyma sut olwg fyddai ar ateb. I wneud pethau'n glir, rydym yn defnyddio swyddogaeth ar wahân i reoli chwiliad deuaidd. A hefyd y swyddogaeth removeIndex(), sy'n dychwelyd y fersiwn o'r arae llai'r mynegai a roddwyd.
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;
};Mae'r algorithm yn dechrau o fynegai [0]. Yna mae'n creu fersiwn o'r arae heb gynnwys y mynegai cyntaf ac yn defnyddio chwiliad deuaidd i weld a oes modd ychwanegu unrhyw rai o'r gwerthoedd sy'n weddill at yr arae i gynhyrchu'r swm a ddymunir. Perfformir y weithred hon unwaith ar gyfer pob elfen yn yr arae.
Bydd gan y ddolen ar gyfer ei hun gymhlethdod amser llinol o O(N), ond y tu mewn i'r ddolen ar gyfer rydym yn cynnal chwiliad deuaidd, sy'n rhoi cymhlethdod amser cyffredinol O(Nlog(N)). Mae'r ateb hwn yn well na'r un blaenorol, ond mae lle i wella o hyd.
Ateb 3: Amser llinellol
Cymhlethdod amser: O(N).
Cymhlethdod gofod: O(1).
Nawr byddwn yn datrys y broblem, gan gofio bod yr amrywiaeth wedi'i datrys. Yr ateb yw cymryd dau rif: un ar y dechrau ac un ar y diwedd. Os yw'r canlyniad yn wahanol i'r un gofynnol, yna newidiwch y mannau cychwyn a gorffen.
Yn y pen draw byddwn naill ai'n dod ar draws y gwerth dymunol ac yn dychwelyd yn wir, neu bydd y pwyntiau cychwyn a diwedd yn cydgyfeirio ac yn dychwelyd ffug.
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;
};
Nawr bod popeth yn iawn, mae'n ymddangos bod yr ateb yn optimaidd. Ond pwy all warantu bod yr arae wedi'i archebu?
Beth felly?
Ar yr olwg gyntaf, gallem fod wedi archebu'r arae yn gyntaf ac yna defnyddio'r datrysiad uchod. Ond sut bydd hyn yn effeithio ar yr amser cyflawni?
Yr algorithm gorau yw quicksort gyda chymhlethdod amser O (Nlog (N)). Os byddwn yn ei ddefnyddio yn ein datrysiad gorau posibl, bydd yn newid ei berfformiad o O(N) i O(Nlog(N)). A yw'n bosibl dod o hyd i ddatrysiad llinol gydag arae heb ei drefnu?
Ateb 4
Cymhlethdod amser: O(N).
Cymhlethdod gofod: O(N).
Oes, mae yna ateb llinol; i wneud hyn, mae angen i ni greu arae newydd sy'n cynnwys y rhestr o gemau yr ydym yn chwilio amdanynt. Y cyfaddawd yma yw mwy o ddefnydd cof: dyma'r unig ateb yn y papur gyda chymhlethdod gofod yn fwy nag O(1).
Os mai gwerth cyntaf arae benodol yw 1 a'r gwerth chwilio yw 8, gallwn ychwanegu'r gwerth 7 at yr arae "gwerthoedd chwilio".
Yna, wrth i ni brosesu pob elfen o'r arae, gallwn wirio'r amrywiaeth o “werthoedd chwilio” a gweld a yw un ohonynt yn gyfartal â'n gwerth. Os oes, dychwelwch yn wir.
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;
};Sail yr ateb yw dolen ar gyfer, sydd, fel y gwelsom uchod, â chymhlethdod amser llinellol o O(N).
Ail ran ailadroddol ein swyddogaeth yw Array.prototype.include(), dull JavaScript a fydd yn dychwelyd yn wir neu'n anwir yn dibynnu a yw'r arae yn cynnwys y gwerth penodol.
I ddarganfod cymhlethdod amser Array.prototype.includes(), gallwn edrych ar y polyfill a ddarperir gan MDN (ac wedi'i ysgrifennu yn JavaScript) neu ddefnyddio dull yng nghod ffynhonnell injan JavaScript fel 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;
}
});
}Yma, rhan iterus Array.prototype.include() yw'r ddolen tra yng ngham 7 sydd (bron) yn croesi hyd cyfan yr arae a roddir. Mae hyn yn golygu bod ei gymhlethdod amser hefyd yn llinol. Wel, gan ei fod bob amser un cam y tu ôl i'n prif arae, y cymhlethdod amser yw O (N + (N - 1)). Gan ddefnyddio Nodiant O Mawr, rydym yn ei symleiddio i O(N) - oherwydd mai N sy'n cael yr effaith fwyaf wrth gynyddu maint y mewnbwn.
O ran cymhlethdod gofodol, mae angen arae ychwanegol y mae ei hyd yn adlewyrchu'r arae wreiddiol (llai un, ie, ond gellir ei anwybyddu), gan arwain at gymhlethdod gofodol O(N). Wel, mae defnydd cynyddol o gof yn sicrhau effeithlonrwydd mwyaf posibl yr algorithm.
Rwy'n gobeithio y bydd yr erthygl yn ddefnyddiol i chi fel atodiad i'ch cyfweliad fideo. Mae'n dangos y gellir datrys problem syml mewn sawl ffordd wahanol gan ddefnyddio symiau gwahanol o adnoddau (amser, cof).
Mae Skillsbox yn argymell:
- Cwrs ar-lein cymhwysol .
- Cwrs ar-lein .
- Cwrs blwyddyn ymarferol .
Ffynhonnell: hab.com