Geekly articles weekly

Memecahkan tugas dari wawancara Google tentang JavaScript: 4 cara berbeda



Ketika saya mempelajari kinerja algoritme, saya menemukan video ini dari wawancara tiruan Google . Ini tidak hanya memberikan gambaran tentang bagaimana wawancara diadakan di perusahaan teknologi besar, tetapi juga memungkinkan Anda untuk memahami bagaimana masalah algoritmik diselesaikan, dan paling efisien.

Artikel ini adalah semacam iringan video. Di dalamnya, saya memberikan komentar pada semua solusi yang ditampilkan, ditambah versi saya sendiri dari solusi dalam JavaScript. Nuansa dari masing-masing algoritma juga dibahas.

Kami mengingatkan Anda: untuk semua pembaca "Habr" - diskon 10.000 rubel saat mendaftar untuk kursus Skillbox apa pun menggunakan kode promo "Habr".

Skillbox merekomendasikan: Kursus praktis "Pengembang Mobile PRO" .

Pernyataan masalah


Kami diberi array yang dipesan dan nilai tertentu. Kemudian mereka meminta untuk membuat fungsi yang mengembalikan benar atau salah, tergantung pada apakah jumlah dari dua angka dari array dapat sama dengan nilai yang diberikan.

Dengan kata lain, apakah ada dua bilangan bulat x dan y dalam array yang, ketika ditambahkan, sama dengan nilai yang ditentukan?

Contoh A

Jika kita diberi array [1, 2, 4, 9] dan nilai 8, fungsi akan mengembalikan false, karena tidak ada dua angka dari array yang bisa memberikan total 8.

Contoh B

Tetapi jika itu adalah array [1, 2, 4, 4] dan nilainya adalah 8, fungsi tersebut harus mengembalikan true, karena 4 + 4 = 8.

Solusi 1. Bruteforce

Kesulitan temporal: O (NĀ²).
Kompleksitas spasial: O (1).

Arti yang paling jelas adalah menggunakan sepasang loop bersarang.

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

Solusi ini tidak dapat disebut efektif, karena memeriksa setiap jumlah yang mungkin dari dua elemen dalam array, dan juga membandingkan setiap pasangan indeks dua kali. (Misalnya, ketika i = 1 dan j = 2 - ini sebenarnya sama dengan membandingkan dengan i = 2 dan j = 1, tetapi dalam solusi ini kami mencoba kedua opsi).

Karena solusi kami menggunakan sepasang bersarang untuk loop, itu kuadratik dengan kompleksitas waktu O (NĀ²).


Solusi 2. Pencarian biner (biner)

Kesulitan temporal: O (Nlog (N)).
Kompleksitas spasial: O (1) .

Karena array dipesan, kita dapat mencari solusi menggunakan pencarian biner. Ini adalah algoritma yang paling efisien untuk array yang dipesan. Pencarian biner itu sendiri memiliki runtime O (log (N)). Namun, Anda masih perlu menggunakan loop for untuk memeriksa setiap elemen terhadap semua nilai lainnya.

Berikut ini solusinya. Untuk memperjelas semuanya, kami menggunakan fungsi terpisah untuk mengontrol pencarian biner. Serta fungsi removeIndex (), yang mengembalikan versi array dikurangi indeks yang ditentukan.

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

Algoritme dimulai dari indeks [0]. Kemudian ia menciptakan versi array, tidak termasuk indeks pertama, dan menggunakan pencarian biner untuk memeriksa apakah ada nilai yang tersisa yang dapat ditambahkan ke array untuk mendapatkan jumlah yang diinginkan. Tindakan ini dilakukan sekali untuk setiap elemen dalam array.

For loop itu sendiri akan memiliki kompleksitas waktu linear O (N), tetapi di dalam for loop kami melakukan pencarian biner, yang memberikan kompleksitas waktu total O (Nlog (N)). Solusi ini lebih baik dari yang sebelumnya, tetapi masih ada sesuatu untuk diperbaiki.


Solusi 3. Waktu linier

Kesulitan temporal: O (N).
Kompleksitas spasial: O (1).

Sekarang kita akan menyelesaikan masalah, mengingat array diurutkan. Solusinya adalah dengan mengambil dua angka: satu di awal dan satu di akhir. Jika hasilnya berbeda dari yang diperlukan, maka kami mengubah titik awal dan akhir.

Pada akhirnya, kami memenuhi nilai yang diinginkan dan mengembalikan true, atau titik awal dan akhir bertemu dan mengembalikan 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; };


Sekarang semuanya baik-baik saja, solusinya tampaknya menjadi optimal. Tetapi siapa yang akan menjamin bahwa array telah dipesan?

Lalu apa?


Sekilas, kita bisa mengurutkan array terlebih dahulu, dan kemudian menggunakan solusi di atas. Tetapi bagaimana ini akan mempengaruhi runtime?

Algoritma terbaik adalah penyortiran cepat dengan kompleksitas waktu O (Nlog (N)). Jika kami menggunakannya dalam solusi optimal kami, itu akan mengubah kinerjanya dari O (N) ke O (Nlog (N)). Apakah mungkin untuk menemukan solusi linier dengan array yang tidak terurut?

Keputusan 4

Kesulitan temporal: O (N).
Kompleksitas spasial: O (N).

Ya, ada solusi linier, untuk ini Anda perlu membuat array baru yang berisi daftar kecocokan yang kami cari. Imbalannya di sini adalah penggunaan memori yang lebih aktif: ini adalah satu-satunya solusi dalam artikel dengan kompleksitas spasial melebihi O (1).

Jika nilai pertama array ini adalah 1 dan nilai pencarian adalah 8, kita dapat menambahkan nilai 7 ke array "nilai pencarian".

Kemudian, memproses setiap elemen array, kita dapat memeriksa array "nilai pencarian" dan melihat apakah salah satu dari mereka sama dengan nilai kita. Jika ya, kembalikan benar.

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

Dasar dari solusinya adalah for loop, yang, seperti yang kita lihat di atas, memiliki kompleksitas waktu linear O (N).

Bagian iterasi kedua dari fungsi kami adalah Array.prototype.include (), metode JavaScript yang akan mengembalikan benar atau salah tergantung pada apakah array berisi nilai yang diberikan.

Untuk mengetahui kompleksitas waktu Array.prototype.includes (), kita dapat melihat polyfill yang disediakan oleh MDN (dan ditulis dalam JavaScript), atau menggunakan metode dalam kode sumber mesin JavaScript seperti Google V8 (C ++).

 // https://tc39.imtqy.com/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; } }); }

Di sini, bagian berulang dari Array.prototype.include () adalah loop while di langkah 7, yang (hampir) melintasi seluruh panjang array yang diberikan. Ini berarti bahwa kompleksitas temporal juga linier. Nah, karena selalu selangkah di belakang array utama kami, kompleksitas waktu adalah O (N + (N - 1)). Menggunakan Notasi O Besar, kami menyederhanakannya menjadi O (N) - karena N yang memiliki pengaruh terbesar dengan meningkatnya ukuran input.

Adapun kompleksitas spasial, array tambahan diperlukan, panjang yang mencerminkan array asli (minus satu, ya, tetapi ini dapat diabaikan), yang mengarah pada kompleksitas spasial O (N). Nah, peningkatan penggunaan memori memastikan efisiensi algoritma maksimum.


Saya harap artikel ini bermanfaat bagi Anda sebagai lampiran wawancara video. Ini menunjukkan bahwa masalah sederhana dapat diselesaikan dengan beberapa cara berbeda dengan jumlah sumber daya yang digunakan berbeda (waktu, memori).

Skillbox merekomendasikan:

Source: https://habr.com/ru/post/id443886/

More articles:


All Articles