حل یک مشکل از مصاحبه گوگل در جاوا اسکریپت: 4 روش مختلف

زمانی که عملکرد الگوریتم ها را مطالعه می کردم به این موضوع برخورد کردم این ویدئویی از یک مصاحبه ساختگی گوگل است.. این نه تنها ایده ای از نحوه انجام مصاحبه ها در شرکت های بزرگ فناوری ارائه می دهد، بلکه به شما امکان می دهد تا بفهمید که چگونه مشکلات الگوریتمی تا حد امکان کارآمد حل می شوند.

این مقاله به نوعی همراهی ویدیو است. در آن من نظراتی را در مورد تمام راه حل های نشان داده شده، به علاوه نسخه خودم از راه حل در جاوا اسکریپت ارائه می کنم. تفاوت های ظریف هر الگوریتم نیز مورد بحث قرار می گیرد.

یادآوری می کنیم: برای همه خوانندگان "Habr" - تخفیف 10 روبل هنگام ثبت نام در هر دوره Skillbox با استفاده از کد تبلیغاتی "Habr".

Skillbox توصیه می کند: دوره عملی "موبایل توسعه دهنده PRO".

بیانیه مشکل

به ما یک آرایه مرتب و یک مقدار خاص داده می شود. سپس از آن خواسته می شود تا تابعی ایجاد کند که بسته به اینکه مجموع هر دو عدد در آرایه می تواند برابر با یک مقدار معین باشد، true یا false را برمی گرداند.

به عبارت دیگر، آیا دو عدد صحیح در آرایه وجود دارد، x و y که وقتی با هم جمع شوند مقدار مشخص شده برابر است؟

مثال الف

اگر یک آرایه [1، 2، 4، 9] به ما داده شود و مقدار آن 8 باشد، تابع false برمی‌گرداند زیرا هیچ دو عددی در آرایه نمی‌توانند 8 را جمع کنند.

مثال B

اما اگر یک آرایه [1، 2، 4، 4] باشد و مقدار آن 8 باشد، تابع باید true باشد زیرا 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 است، اما در این راه حل ما هر دو گزینه را امتحان می کنیم).

از آنجایی که راه حل ما از یک جفت حلقه های تو در تو استفاده می کند، درجه دوم با پیچیدگی زمانی 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).

اکنون با یادآوری اینکه آرایه مرتب شده است، مشکل را حل خواهیم کرد. راه حل این است که دو عدد را بگیرید: یکی در ابتدا و دیگری در پایان. اگر نتیجه با نتیجه مورد نیاز متفاوت است، سپس نقاط شروع و پایان را تغییر دهید.

در نهایت یا با مقدار مورد نظر مواجه می‌شویم و true را برمی‌گردانیم یا نقطه شروع و پایان همگرا و false برمی‌گردند.

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() است، یک متد جاوا اسکریپت که بسته به اینکه آرایه حاوی مقدار داده شده باشد true یا false را برمی گرداند.

برای پی بردن به پیچیدگی زمانی Array.prototype.includes()، می توانیم به polyfill ارائه شده توسط MDN (و نوشته شده در جاوا اسکریپت) نگاه کنیم یا از روشی در کد منبع یک موتور جاوا اسکریپت مانند 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;
    }
  });
}

در اینجا قسمت تکراری Array.prototype.include() حلقه while در مرحله 7 است که (تقریباً) تمام طول آرایه داده شده را طی می کند. این بدان معناست که پیچیدگی زمانی آن نیز خطی است. خوب، از آنجایی که همیشه یک قدم از آرایه اصلی ما عقب است، پیچیدگی زمانی O (N + (N - 1)) است. با استفاده از نماد Big O، آن را به O(N) ساده می کنیم - زیرا N است که بیشترین تأثیر را هنگام افزایش اندازه ورودی دارد.

با توجه به پیچیدگی فضایی، یک آرایه اضافی مورد نیاز است که طول آن منعکس کننده آرایه اصلی باشد (منهای یک، بله، اما می توان آن را نادیده گرفت)، که منجر به پیچیدگی فضایی O(N) می شود. خوب، افزایش استفاده از حافظه، حداکثر کارایی الگوریتم را تضمین می کند.

امیدوارم مقاله به عنوان مکمل مصاحبه ویدیویی شما مفید واقع شود. این نشان می دهد که یک مسئله ساده را می توان به چندین روش مختلف با مقادیر مختلف منابع مورد استفاده (زمان، حافظه) حل کرد.

Skillbox توصیه می کند:

• دوره آنلاین کاربردی "تحلیلگر داده پایتون".
• دوره آنلاین "توسعه‌دهنده حرفه‌ای ظاهری".
• دوره عملی سال "توسعه دهنده PHP از 0 تا PRO".

منبع: www.habr.com