🥇JavaScript'те Google интервьюсунан көйгөйдү чечүү: 4 башка жол

Алгоритмдердин аткарылышын изилдеп жүргөндө мен буга туш болдум Бул Google жасалма интервьюсунун видеосу.. Бул ири технологиялык корпорацияларда интервьюлар кандай өткөрүлөт деген түшүнүктү гана бербестен, алгоритмдик көйгөйлөр кантип мүмкүн болушунча натыйжалуу чечилерин түшүнүүгө мүмкүндүк берет.

Бул макала видеонун бир түрү болуп саналат. Анда мен бардык көрсөтүлгөн чечимдерге комментарий берем, ошондой эле JavaScriptдеги чечимдин өзүмдүн версиям. Ар бир алгоритмдин нюанстары да талкууланат.

Биз эсиңизге салабыз: "Хабрдын" бардык окурмандары үчүн - "Habr" промо-кодун колдонуу менен каалаган Skillbox курсуна катталганда 10 000 рубль арзандатуу.

Skillbox сунуштайт: Практикалык курс "Мобилдик иштеп чыгуучу PRO".

Тапшырманын коюлушу

Бизге иреттелген массив жана белгилүү бир маани берилет. Андан кийин массивдеги каалаган эки сандын суммасы берилген мааниге барабар болушуна жараша чын же жалганды кайтарган функцияны түзүү суралат.

Башкача айтканда, массивде x жана y эки бүтүн сан бар, алар кошулганда көрсөтүлгөн мааниге барабар болобу?

Мисал А

Эгерде бизге массив [1, 2, 4, 9] берилсе жана мааниси 8 болсо, функция жалганды кайтарат, анткени массивдеги эки сан 8ге чейин кошула албайт.

Мисал Б

Бирок ал массив [1, 2, 4, 4] болсо жана мааниси 8 болсо, функция чындыкты кайтарышы керек, анткени 4 + 4 = 8.

Чечим 1: Оор күч

Убакыт татаалдыгы: O(N²).
Космостун татаалдыгы: O(1).

Эң айкын мааниси - жуп уяланган илмектерди колдонуу.

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 = 1 жана j = 2 чындыгында i = 2 жана j = 1 менен салыштырганда бирдей, бирок бул чечимде биз эки вариантты тең аракет кылабыз).

Биздин чечимибиз бир жуп уяланган for циклин колдонгондуктан, ал O(N²) убакыт татаалдыгы менен квадраттык болуп саналат.

Чечим 2: Бинардык издөө

Убакыт татаалдыгы: O(Nlog(N)).
Космостун татаалдыгы: O(1).

Массивдер иреттелгендиктен, биз бинардык издөө аркылуу чечимди издей алабыз. Бул иреттелген массивдер үчүн эң эффективдүү алгоритм. Бинардык издөөнүн өзүндө O(log(N)) иштөө убактысы бар. Бирок, сиз дагы эле ар бир элементти башка бардык баалуулуктарга каршы текшерүү үчүн for циклин колдонушуңуз керек.

Бул жерде чечим кандай болушу мүмкүн. Баарын айкын кылуу үчүн, биз экилик издөөнү башкаруу үчүн өзүнчө функцияны колдонобуз. Жана ошондой эле removeIndex() функциясы, ал массивдин версиясын минус берилген индексти кайтарат.

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;
};

Алгоритм [0] индексинен башталат. Андан кийин ал биринчи индексти кошпогондо массивдин версиясын түзөт жана керектүү сумманы өндүрүү үчүн массивге калган маанилердин кайсынысын кошууга болорун билүү үчүн бинардык издөөнү колдонот. Бул аракет массивдеги ар бир элемент үчүн бир жолу аткарылат.

for циклинин өзү O(N) сызыктуу убакыт татаалдыгына ээ болот, бирок for циклинин ичинде биз O(Nlog(N)) жалпы убакыт татаалдыгын берген бинардык издөөнү жүргүзөбүз. Бул чечим мурункусуна караганда жакшыраак, бирок дагы деле жакшыртууга мүмкүнчүлүк бар.

Чечим 3: Сызыктуу убакыт

Убакыт татаалдыгы: O(N).
Космостун татаалдыгы: O(1).

Эми массив иреттелгенин эстеп, маселени чечебиз. Чечим эки санды алуу керек: бири башында жана экинчиси аягында. Эгер натыйжа талап кылынгандан башкача болсо, анда баштапкы жана аяктоочу чекиттерди өзгөртүңүз.

Акыр-аягы, биз же каалаган мааниге туш болобуз жана чындыкты кайтарабыз, же башталгыч жана аяккы чекиттер биригип, жалганга кайтып келишет.

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;
};

Азыр баары жакшы, чечим оптималдуу окшойт. Бирок массив заказ кылынганына ким кепилдик бере алат?

Анда эмне?

Бир караганда, биз алгач массивге буйрук берип, андан кийин жогорудагы чечимди колдонсок болмок. Бирок бул аткаруу убактысына кандай таасир этет?

Эң жакшы алгоритм убакыттын татаалдыгы O (Nlog (N)) менен тез сорттоо. Эгерде биз аны оптималдуу чечимибизде колдонсок, ал өзүнүн көрсөткүчүн O(N)ден O(Nlog(N))ге өзгөртөт. Тартипсиз массив менен сызыктуу чечимди табуу мүмкүнбү?

Чечим 4

Убакыт татаалдыгы: O(N).
Космос татаалдыгы: O(N).

Ооба, сызыктуу чечим бар; бул үчүн биз издеп жаткан дал келүүлөрдүн тизмесин камтыган жаңы массив түзүшүбүз керек. Бул жерде алмашуу эстутумду көбүрөөк колдонуу: бул кагаздагы мейкиндик татаалдыгы O(1)ден жогору болгон жалгыз чечим.

Эгерде берилген массивдин биринчи мааниси 1 болсо жана издөө мааниси 8 болсо, биз "издөө баалуулуктары" массивине 7 маанисин кошо алабыз.

Андан кийин, массивдин ар бир элементин иштетип жатканда, биз "издөө маанилеринин" массивин текшерип, алардын бири биздин мааниге барабар экендигин көрө алабыз. Ооба болсо, чындыкты кайтарыңыз.

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;
};

Чечүүнүн негизин for цикли түзөт, ал жогоруда көргөндөй O(N) сызыктуу убакыт татаалдыгына ээ.

Функциябыздын экинчи итеративдик бөлүгү - Array.prototype.include(), массив берилген маанини камтыганына жараша чын же жалганды кайтара турган JavaScript ыкмасы.

Array.prototype.includes() убактысынын татаалдыгын аныктоо үчүн, биз MDN тарабынан берилген политолтураны карап көрсөк болот (жана JavaScript менен жазылган) же Google V8 (C++) сыяктуу JavaScript кыймылдаткычынын баштапкы кодундагы ыкманы колдонсок болот.

// 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;
    }
  });
}

Бул жерде Array.prototype.include() итеративдик бөлүгү 7-кадамдагы while цикли болуп саналат, ал (дээрлик) берилген массивдин бүт узундугун кесип өтөт. Бул анын убакыт татаалдыгы да сызыктуу экенин билдирет. Ооба, ал ар дайым биздин негизги массивден бир кадам артта тургандыктан, убакыттын татаалдыгы O (N + (N - 1)) болуп саналат. Big O белгилөөсүн колдонуп, биз аны O(N) кылып жөнөкөйлөтөбүз - анткени киргизүү өлчөмүн көбөйтүүдө эң чоң таасир этүүчү N.

Мейкиндик татаалдыгына келсек, узундугу баштапкы массивди чагылдырган кошумча массив керектелет (минус бир, ооба, бирок аны этибарга албай коюуга болот), натыйжада O(N) мейкиндик татаалдыгы пайда болот. Ооба, эстутумдун көбөйүшү алгоритмдин максималдуу натыйжалуулугун камсыз кылат.

Бул макала сизге видео маегиңизге кошумча катары пайдалуу болот деп ишенем. Бул жөнөкөй маселени ар кандай көлөмдөгү ресурстар (убакыт, эс тутум) менен бир нече ар кандай жолдор менен чечсе болорун көрсөтөт.

Skillbox сунуштайт:

Колдонмо онлайн курс "Python маалымат аналитиги".

Онлайн курс "Профессионалдуу иштеп чыгуучу".

Практикалык жылдык курс "PHP иштеп чыгуучусу 0дөн PRO".

Source: www.habr.com

JavaScript менен Google интервьюсунан көйгөйдү чечүү: 4 башка жол

Тапшырманын коюлушу

Анда эмне?

Комментарий кошуу жокко жооп