Coding Interview Prep · Pelajaran

Trik Selisih Nomor Baris

Kurangi ROW_NUMBER dari suatu deret untuk mengelompokkan nilai berurutan menjadi islands.

Trik Selisih Nomor Baris adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 2 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.

Kunci Pulau yang Paling Elegan

Trik selisih nomor baris adalah teknik yang paling ingin dilihat pewawancara untuk pulau yang terdiri dari bilangan bulat atau tanggal berurutan. Teknik ini menghasilkan kunci grup melalui satu pengurangan, tanpa LAG dan tanpa jumlah berjalan.

Gagasan utamanya: kurangi ROW_NUMBER dari nilai itu sendiri. Untuk setiap rangkaian nilai berurutan, baik nilainya maupun nomor barisnya bertambah tepat 1 pada setiap langkah, sehingga selisihnya tetap di seluruh rangkaian. Nilai tetap itu adalah kunci pulau Anda.

Mengapa Selisihnya Tetap

Perhatikan dua baris yang bersebelahan dalam rangkaian berurutan. Saat berpindah dari satu baris ke baris berikutnya, nilainya bertambah 1 dan nomor barisnya juga bertambah 1. Kurangkan keduanya, maka kenaikan +1 saling meniadakan, sehingga value - row_number tidak berubah.

Namun begitu ada celah, nilainya melonjak lebih dari 1 sementara nomor barisnya tetap hanya bertambah 1. Selisihnya bergeser menjadi konstanta baru. Pergeseran itulah yang memisahkan satu pulau dari pulau berikutnya.

Melihatnya pada Data Kita

Ingat kembali hari masuk 1, 2, 3, 7, 8, 10. Mari susun nomor baris dan selisihnya berdampingan:

hari 1, nomor baris 1, selisih 0
hari 2, nomor baris 2, selisih 0
hari 3, nomor baris 3, selisih 0
hari 7, nomor baris 4, selisih 3
hari 8, nomor baris 5, selisih 3
hari 10, nomor baris 6, selisih 4

Selisih (0,0,0,3,3,4) membagi baris dengan sempurna menjadi tiga pulau. Selisih yang sama berarti pulau yang sama.

SELECT
  day_no,
  ROW_NUMBER() OVER (ORDER BY day_no) AS rn,
  day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
FROM logins
ORDER BY day_no;

Meringkas Menjadi Pulau

Dengan selisih sebagai kunci grup, kueri akhir adalah peringkasan standar. Bungkus selisih dalam CTE dan lakukan GROUP BY terhadapnya:

Ini mengembalikan tiga pulau yang sama seperti sebelumnya, tetapi SQL-nya lebih singkat dan jelas daripada versi LAG plus jumlah berjalan. Untuk rangkaian bilangan bulat atau rangkaian dengan langkah seragam, inilah jawaban yang sebaiknya dipilih terlebih dahulu.

WITH keyed AS (
  SELECT
    day_no,
    day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
  FROM logins
)
SELECT
  MIN(day_no) AS start_day,
  MAX(day_no) AS end_day,
  COUNT(*)    AS length
FROM keyed
GROUP BY grp
ORDER BY start_day;

Jebakan: Nilai Harus Bertambah Satu

Trik selisih sederhana mengasumsikan urutan bertambah tepat 1 pada setiap langkah. Hal itu berlaku untuk bilangan bulat berurutan dan hari-hari kalender yang berurutan, tetapi tidak berlaku jika nilai bertambah dengan jumlah tetap lain atau jika terdapat duplikat.

Nilai genap 2,4,6,8 akan terlihat seperti celah jika menggunakan pengurangan nilai dengan nomor baris.
Nilai duplikat mengacaukan keselarasan karena nomor baris terus bertambah, sedangkan nilainya tidak.

Memahami keterbatasan ini dan cara memperbaikinya membedakan trik hafalan dari pemahaman yang sebenarnya.

Memperbaiki Urutan dengan Langkah Tetap

Jika nilai bertambah dengan konstanta yang diketahui, k, bukan 1, lakukan normalisasi terlebih dahulu: bagi nilai dengan k (atau gunakan value / k untuk bilangan bulat) agar setiap langkah kembali menjadi 1, lalu kurangi dengan nomor baris.

Misalnya, untuk bilangan genap yang bertambah 2, gunakan day_no / 2 - ROW_NUMBER(). Nilai yang telah dinormalisasi kini bertambah 1 pada setiap item berurutan, sehingga sifat selisih konstan kembali berlaku.

SELECT
  val,
  (val / 2) - ROW_NUMBER() OVER (ORDER BY val) AS grp
FROM even_series
ORDER BY val;

Menerapkannya pada Tanggal

Tanggal adalah bentuk yang paling umum dalam penggunaan nyata. Tanggal kalender tidak dapat langsung dikurangkan dari nomor baris, jadi ubah tanggal menjadi jumlah hari terlebih dahulu. Di Postgres, kurangi tanggal acuan tetap untuk mendapatkan bilangan bulat yang menyatakan jumlah hari, lalu terapkan trik yang sama.

Karena hari-hari kalender yang berurutan memiliki selisih 1, selisih antara jumlah hari dan nomor baris kembali konstan dalam satu pulau.

WITH keyed AS (
  SELECT
    login_date,
    (login_date - DATE '2000-01-01')
      - ROW_NUMBER() OVER (ORDER BY login_date) AS grp
  FROM daily_logins
)
SELECT MIN(login_date) AS start_date,
       MAX(login_date) AS end_date,
       COUNT(*)        AS days_in_run
FROM keyed GROUP BY grp ORDER BY start_date;

Menghitung Selisih Tanggal Lintas Dialek

Langkah mengubah tanggal menjadi bilangan bulat berbeda-beda menurut mesin basis data, dan pewawancara menghargai pemahaman lintas dialek:

Postgres: kurangi literal tanggal: login_date - DATE '2000-01-01' menghasilkan bilangan bulat.
MySQL: gunakan DATEDIFF(login_date, '2000-01-01').
SQL Server: gunakan DATEDIFF(day, '2000-01-01', login_date).

Pada beberapa mesin, cara yang lebih praktis adalah mengurangkan ROW_NUMBER hari langsung dari tanggal menggunakan aritmetika interval, lalu melakukan GROUP BY berdasarkan tanggal acuan yang dihasilkan.

SELECT
  login_date,
  login_date - (ROW_NUMBER() OVER (ORDER BY login_date)
               * INTERVAL '1 day') AS grp_date
FROM daily_logins;

Menambahkan Partisi per Grup

Untuk pulau per pengguna, lakukan partisi nomor baris berdasarkan kolom grup. Yang sangat penting, kunci grup juga harus menyertakan kolom partisi tersebut, karena dua pengguna berbeda dapat secara kebetulan menghasilkan nilai selisih yang sama.

Jadi, lakukan GROUP BY pada user_id dan selisih yang dihitung. Lupa menyertakan user_id dalam GROUP BY terakhir adalah kesalahan tersembunyi yang sering dicari oleh pewawancara.

WITH keyed AS (
  SELECT user_id, day_no,
    day_no - ROW_NUMBER()
      OVER (PARTITION BY user_id ORDER BY day_no) AS grp
  FROM logins
)
SELECT user_id, MIN(day_no) AS start_day,
       MAX(day_no) AS end_day, COUNT(*) AS len
FROM keyed
GROUP BY user_id, grp
ORDER BY user_id, start_day;

Trik vs LAG: Mana yang Digunakan

Sekarang Anda memiliki dua teknik andal dalam perangkat kerja Anda. Pilihlah dengan sengaja:

Selisih nomor baris: paling singkat dan bersih untuk rangkaian nilai dengan langkah yang seragam (bilangan bulat berurutan, tanggal berurutan). Ini adalah pilihan pertama ketika keterurutan berarti "berbeda dengan konstanta".
LAG ditambah jumlah berjalan: lebih fleksibel ketika keterurutan tidak menggunakan langkah numerik tetap, misalnya "status sama dengan baris sebelumnya" atau aturan khusus yang tidak beraturan.

Sampaikan pilihan Anda dan alasannya dalam wawancara; penalarannya lebih mengesankan daripada sintaksnya.

Menangani Duplikasi secara Antisipatif

Jika suatu nilai dapat berulang dan Anda tetap menginginkan satu pulau untuk setiap rangkaian berurutan, hilangkan duplikat terlebih dahulu dengan DISTINCT atau langkah pengelompokan agar nomor baris sejajar satu per satu dengan nilai. Alternatifnya, gunakan DENSE_RANK sebagai pengganti ROW_NUMBER agar nilai yang sama memiliki peringkat yang sama.

Selalu tanyakan kepada pewawancara apakah duplikat dapat muncul; cara penanganan yang tepat bergantung pada apakah duplikat seharusnya memperpanjang rangkaian atau diabaikan di dalamnya.

WITH d AS (SELECT DISTINCT day_no FROM logins)
SELECT day_no,
  day_no - ROW_NUMBER() OVER (ORDER BY day_no) AS grp
FROM d;

Pemeriksaan Singkat

Pastikan Anda memahami alasan trik ini berhasil.

Ringkasan: Trik Selisih

Sekarang Anda memiliki kunci pulau yang paling bersih:

Rumus kunci: value - ROW_NUMBER() OVER (ORDER BY value) konstan untuk setiap rangkaian berurutan.
Ringkas dengan GROUP BY berdasarkan selisih tersebut untuk mendapatkan awal, akhir, dan panjang.
Untuk urutan dengan langkah tetap, lakukan normalisasi (bagi dengan langkahnya) terlebih dahulu.
Untuk tanggal, ubah tanggal menjadi jumlah hari berupa bilangan bulat melalui fungsi selisih sesuai dialek.
Per grup: lakukan PARTITION BY pada nomor baris dan sertakan kolom grup dalam GROUP BY terakhir.
Lindungi dari duplikat dengan DISTINCT atau DENSE_RANK.

Selanjutnya, kita mengalihkan perhatian dari pulau ke ruang kosong: mencari celah.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Trik Selisih Nomor Baris” gratis?

Ya — teks lengkap “Trik Selisih Nomor Baris” 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 “Trik Selisih Nomor Baris”?

Kurangi ROW_NUMBER dari suatu deret untuk mengelompokkan nilai berurutan menjadi islands. 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 2 dari 4.

Berapa lama pelajaran “Trik Selisih Nomor Baris” 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

Mengenali Masalah Gaps-and-Islands
Trik Selisih Nomor Baris
Menemukan Celah dalam Deret
Islands dengan Perubahan Tanggal dan Status

← Kembali ke Coding Interview Prep