0Pricing
Coding Interview Prep · Pelajaran

Mengenali Masalah Gaps-and-Islands

Identifikasi pola dalam soal berbentuk uraian dan pahami inti pengelompokannya.

Mengenali Masalah Gaps-and-Islands adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Pola yang Diujikan Pewawancara

Ketika pewawancara senior meminta Anda menemukan rangkaian berurutan dari sesuatu, Anda sedang menghadapi masalah celah dan pulau. Nama ini berasal dari gambaran mental: baris yang termasuk dalam satu kelompok membentuk sebuah pulau, sedangkan jeda di antaranya adalah celah.

  • Sebuah pulau adalah rangkaian baris terpanjang yang berdekatan berdasarkan suatu aturan (bilangan bulat berurutan, tanggal berurutan, atau status yang sama secara berulang).
  • Sebuah celah adalah ruang yang hilang di antara dua pulau.

Mengenali jenis masalah ini secara langsung merupakan sinyal senior tersendiri. Banyak kandidat terjebak dalam rangkaian penggabungan tabel dengan dirinya sendiri; jawaban elegan hampir selalu berupa fungsi jendela.

Soal Uraian yang Menyembunyikan Pulau

Tantangannya adalah pewawancara jarang menyebut "celah dan pulau". Mereka menyamarkannya. Latih kepekaan Anda terhadap ungkapan seperti:

  • "Temukan setiap periode saat pengguna berlangganan secara terus-menerus."
  • "Berapa banyak hari berturut-turut server tetap aktif?"
  • "Rentang ID yang hilang mana yang tidak ada dalam tabel ini?"
  • "Rapatkan baris bersebelahan dengan status yang sama menjadi satu baris."

Semua ini memiliki bentuk yang sama: kelompokkan baris yang bersebelahan, lalu laporkan awal, akhir, atau ketiadaan kelompok tersebut. Setelah Anda memetakan kata-katanya ke pulau, penulisan SQL menjadi mudah.

Wawasan Inti: Membuat Kunci Grup

Inilah seluruh triknya dalam satu kalimat: jika Anda dapat memberikan kunci grup yang sama kepada setiap baris dalam pulau yang sama, GROUP BY sederhana akan meringkas setiap pulau menjadi satu baris ringkasan.

Jadi, pekerjaan sebenarnya dalam masalah celah dan pulau adalah menghitung kunci grup tersebut. Berbagai variasi menghitungnya dengan cara berbeda, tetapi semuanya memiliki tujuan ini. Setelah Anda memiliki kuncinya, langkah terakhir sepele:

SELECT
  grp,
  MIN(value) AS island_start,
  MAX(value) AS island_end,
  COUNT(*)   AS island_length
FROM rows_with_group_key
GROUP BY grp
ORDER BY island_start;

Kumpulan Data Konkret

Mari mulai dari data. Bayangkan tabel logins yang mencatat nomor hari ketika pengguna masuk:

  • Hari yang ada: 1, 2, 3, 7, 8, 10

Secara kasatmata, pulaunya adalah {1,2,3}, {7,8}, dan {10}. Celahnya adalah hari 4-6 dan hari 9. Tugas Anda dalam wawancara adalah membuat basis data mengenali ketiga pulau ini tanpa Anda menunjukkannya secara manual. Ingat terus kumpulan data kecil ini saat kita mempelajari setiap teknik.

CREATE TABLE logins (day_no INT);
INSERT INTO logins VALUES (1),(2),(3),(7),(8),(10);

Mengapa Pendekatan Naif Gagal

Insting pertama yang umum adalah membandingkan setiap baris dengan baris berikutnya menggunakan penggabungan tabel dengan dirinya sendiri, lalu menandai jeda. Cara ini berhasil untuk menemukan satu celah, tetapi dengan cepat menjadi sulit dikelola:

  • Anda perlu mendeteksi awal dan akhir setiap pulau, yang berarti dua lintasan atau dua penggabungan.
  • Baris tepi (baris paling awal dan paling akhir) memerlukan penanganan khusus.
  • Cara ini tidak dapat digeneralisasi menjadi "beri saya panjang setiap rangkaian" tanpa logika tambahan.

Pewawancara mengamati apakah Anda terjebak dalam rangkaian penggabungan tabel sendiri atau mengenali bahwa satu lintasan dengan fungsi jendela lebih rapi.

Model Mental untuk Mendeteksi Celah

Salah satu cara yang kuat untuk merumuskannya adalah: pulau baru dimulai setiap kali baris saat ini tidak bersebelahan dengan baris sebelumnya. Gunakan LAG untuk melihat satu baris ke belakang dan membandingkannya.

Jika day_no - LAG(day_no) lebih besar dari 1 (atau NULL untuk baris pertama), baris ini menandai awal pulau baru. Kita menandainya dengan penanda bernilai 1; jika tidak, nilainya 0. Perhatikan seperti apa penanda tersebut untuk data kita.

SELECT
  day_no,
  CASE
    WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1 THEN 0
    ELSE 1
  END AS is_new_island
FROM logins
ORDER BY day_no;

Mengubah Penanda Menjadi Kunci Grup

Penanda dari langkah sebelumnya adalah 1, 0, 0, 1, 0, 1 untuk hari 1,2,3,7,8,10. Perhatikan bahwa jumlah berjalan dari penanda tersebut menghasilkan angka yang tetap dalam satu pulau dan bertambah setiap kali ada pulau baru: 1,1,1,2,2,3.

Jumlah berjalan itu adalah kunci grup buatan kita. Kita membungkus kueri penanda dalam CTE dan menjumlahkannya dengan fungsi jendela lain:

WITH flagged AS (
  SELECT
    day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new_island
  FROM logins
)
SELECT
  day_no,
  SUM(is_new_island) OVER (ORDER BY day_no) AS grp
FROM flagged;

Menyelesaikan Contoh Terapan

Sekarang tambahkan GROUP BY akhir di atas kunci grup. Setiap nilai grp yang berbeda merupakan satu pulau, dan kita melaporkan batas serta ukurannya:

Hasilnya tepat sama dengan tiga pulau yang kita lihat secara kasatmata: 1-3 (panjang 3), 7-8 (panjang 2), dan 10-10 (panjang 1). Resep tiga lapis ini (penanda, jumlah berjalan, pengelompokan) menjadi tulang punggung hampir setiap jawaban masalah celah dan pulau yang akan Anda tulis.

WITH flagged AS (
  SELECT day_no,
    CASE WHEN day_no - LAG(day_no) OVER (ORDER BY day_no) = 1
         THEN 0 ELSE 1 END AS is_new
  FROM logins
),
keyed AS (
  SELECT day_no,
    SUM(is_new) OVER (ORDER BY day_no) AS grp
  FROM flagged
)
SELECT grp, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed GROUP BY grp ORDER BY start_day;

Kedekatan Bergantung pada Domain

Satu-satunya bagian yang berubah di antara berbagai masalah adalah definisi berdekatan. Mengenali aturan kedekatan yang tepat merupakan separuh dari upaya mengenali masalahnya:

  • Bilangan bulat: berdekatan jika selisihnya tepat 1.
  • Hari kalender: berdekatan jika salah satu tanggal adalah hari berikutnya (date = prev + INTERVAL '1 day').
  • Periode status: berdekatan jika nilai status tidak berubah dari baris sebelumnya.

Kerangkanya sama, tetapi perbandingan di dalam CASE berbeda. Menentukan aturan kedekatan yang berlaku adalah pertanyaan klarifikasi yang sebaiknya Anda sampaikan dalam wawancara.

Pertanyaan Klarifikasi yang Perlu Diajukan

Sebelum menulis satu baris SQL, raihlah poin dengan memperjelas cakupan. Klarifikasi yang baik untuk masalah celah dan pulau:

  • "Apakah saya harus memperlakukan data per pengguna, atau secara global?" (Ini menentukan apakah Anda menambahkan PARTITION BY user_id.)
  • "Apakah dapat ada nilai duplikat pada hari yang sama, dan apakah nilai tersebut memutus atau memperpanjang rangkaian?"
  • "Apakah Anda menginginkan pulau, celah, atau keduanya?"
  • "Apakah urutannya dijamin sudah terurut, atau haruskah saya mengurutkannya sendiri?"

Menyampaikan pertanyaan-pertanyaan ini menunjukkan bahwa Anda pernah menyelesaikan jenis masalah ini dan memahami kasus batasnya.

Pulau per Grup dengan PARTITION BY

Data wawancara nyata hampir selalu dikelompokkan, misalnya aktivitas masuk per pengguna. Perbaikannya mekanis: tambahkan PARTITION BY user_id ke setiap fungsi jendela agar pulau tidak pernah melintasi pengguna.

Kerangkanya identik; Anda hanya membagi data ke dalam partisi. Inilah alasan menguasai kasus satu aliran terlebih dahulu sangat bermanfaat, karena memperluasnya ke per grup hanya memerlukan perubahan satu klausa.

SELECT
  user_id, day_no,
  CASE WHEN day_no - LAG(day_no)
         OVER (PARTITION BY user_id ORDER BY day_no) = 1
       THEN 0 ELSE 1 END AS is_new
FROM logins;

Pemeriksaan Singkat

Uji naluri Anda dalam mengenali pola.

Ringkasan: Mengenali Polanya

Anda kini dapat mengenali masalah celah dan pulau dari penyamarannya dan menyebutkan strateginya:

  • Kata pemicu: berturut-turut, terus-menerus, tanpa putus, rentetan, rentang yang hilang, rapatkan yang bersebelahan.
  • Gagasan inti: berikan setiap baris dalam rangkaian yang sama satu kunci grup yang sama, lalu gunakan GROUP BY terhadapnya.
  • Resep: tandai pulau baru dengan LAG, jumlahkan penanda secara berjalan menjadi sebuah kunci, lalu lakukan agregasi.
  • Kedekatan bergantung pada domain (bilangan bulat, tanggal, atau status yang tidak berubah).
  • Tambahkan PARTITION BY untuk analisis per grup; jelaskan cakupan sebelum menulis kode.

Selanjutnya kita mempertajam metode pembangunan kunci yang paling elegan: trik selisih nomor baris.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Mengenali Masalah Gaps-and-Islands” gratis?

Ya — teks lengkap “Mengenali Masalah Gaps-and-Islands” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Mengenali Masalah Gaps-and-Islands”?

Identifikasi pola dalam soal berbentuk uraian dan pahami inti pengelompokannya. Kamu berlatih Coding Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai Coding Interview Prep?

Tidak diperlukan pengalaman sebelumnya. Coding Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Mengenali Masalah Gaps-and-Islands” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran Coding Interview Prep ini?

Ya. Setiap pelajaran Coding Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Mengenali Masalah Gaps-and-Islands
  2. Trik Selisih Nomor Baris
  3. Menemukan Celah dalam Deret
  4. Islands dengan Perubahan Tanggal dan Status
← Kembali ke Coding Interview Prep