პრობლემის გადაჭრა Google-ის ინტერვიუდან JavaScript-ში: 4 განსხვავებული გზა

როცა ალგორითმების შესრულებას ვსწავლობდი, ამას წავაწყდი ეს არის Google-ის იმიტირებული ინტერვიუს ვიდეო.. ის არა მხოლოდ იძლევა წარმოდგენას იმის შესახებ, თუ როგორ ტარდება ინტერვიუები დიდ ტექნოლოგიურ კორპორაციებში, არამედ საშუალებას გაძლევთ გაიგოთ, თუ როგორ წყდება ალგორითმული პრობლემები რაც შეიძლება ეფექტურად.

ეს სტატია არის ვიდეოს ერთგვარი თანხლება. მასში მე ვაძლევ კომენტარს ყველა ნაჩვენები გადაწყვეტის შესახებ, პლუს გადაწყვეტის ჩემი საკუთარი ვერსია JavaScript-ში. ასევე განიხილება თითოეული ალგორითმის ნიუანსი.

შეგახსენებთ: "Habr"-ის ყველა მკითხველისთვის - ფასდაკლება 10 რუბლიდან Skillbox-ის ნებისმიერ კურსზე ჩარიცხვისას "Habr" სარეკლამო კოდის გამოყენებით.

Skillbox გირჩევთ: პრაქტიკული კურსი "Mobile Developer 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 loop, რათა შეამოწმოთ თითოეული ელემენტი ყველა სხვა მნიშვნელობის წინააღმდეგ.

აი, როგორი შეიძლება იყოს გამოსავალი. გასაგებად რომ ვთქვათ, ჩვენ ვიყენებთ ცალკეულ ფუნქციას ბინარული ძიების გასაკონტროლებლად. და ასევე 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)-მდე). შესაძლებელია თუ არა წრფივი ამონახსნის პოვნა უწესრიგო მასივით?

Solution 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 loop, რომელსაც, როგორც ზემოთ ვნახეთ, აქვს O(N) წრფივი დროის სირთულე.

ჩვენი ფუნქციის მეორე განმეორებითი ნაწილია Array.prototype.include(), JavaScript მეთოდი, რომელიც დააბრუნებს true ან false იმისდა მიხედვით, შეიცავს თუ არა მასივი მოცემულ მნიშვნელობას.

Array.prototype.includes()-ის დროის სირთულის გასარკვევად, ჩვენ შეგვიძლია გადავხედოთ MDN-ის მიერ მოწოდებულ პოლიფილს (და დაწერილი JavaScript-ში) ან გამოვიყენოთ მეთოდი JavaScript ძრავის საწყის კოდში, როგორიცაა 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