Wawancara SQL: Temukan Rentetan Login Beruntun Terpanjang Setiap Pengguna

Permintaan dan Konteks yang Berlaku

Anda diberikan sebuah tabel event PostgreSQL:

CREATE TABLE user_logins (
  user_id bigint NOT NULL,
  login_at timestamptz NOT NULL
);

Untuk setiap pengguna, kembalikan setiap rentetan terpanjang dari tanggal kalender America/New_York berurutan di mana pengguna tersebut login setidaknya satu kali. Kolom keluarannya adalah user_id, streak_start, streak_end, dan streak_days. Beberapa event pada tanggal lokal yang sama dihitung sebagai satu hari aktif. Setiap tanggal lokal yang hilang memutus rentetan. Jika seorang pengguna memiliki dua rentetan terpanjang dengan panjang yang sama, kembalikan keduanya. Pengguna tanpa event tidak muncul.

Ini adalah masalah wawancara data dan SQL, bukan permintaan untuk menghitung periode 24 jam yang berlalu. Hari lokal di sekitar transisi daylight saving time (DST) mungkin berisi 23 atau 25 jam dan tetap merupakan satu tanggal kalender. Oleh karena itu, pertanyaan ini menetapkan zona waktu pelaporan sebelum mengonversi timestamp ke tanggal. Jawaban utama ditujukan untuk PostgreSQL; dialek lain memerlukan aritmatika tanggal yang berbeda.

Tugas intinya adalah masalah gaps-and-islands: mentransformasikan tanggal-tanggal terurut sehingga setiap tanggal dalam satu rentetan berurutan berbagi kunci stabil yang sama, mengagregasi setiap kunci menjadi sebuah island, lalu mempertahankan semua island yang memiliki panjang maksimum yang sama per pengguna.

Hal yang Dievaluasi oleh Pewawancara

Sinyal pertama adalah apakah kandidat menentukan grain data sebelum menulis fungsi window. Grain sumber adalah satu event login, tetapi grain bisnis adalah satu baris per pengguna dan tanggal kalender lokal. Melewatkan konversi tersebut membuat event duplikat pada hari yang sama menggelembungkan ROW_NUMBER(), hitungan, dan batas rentetan.

Sinyal kedua adalah apakah kandidat dapat menurunkan island key. Setelah tanggal-tanggal unik diurutkan, baik tanggal maupun ROW_NUMBER() bertambah satu di dalam rentetan berurutan. Oleh karena itu, mengurangkan offset nomor baris dari setiap tanggal menghasilkan nilai yang sama di sepanjang rentetan tersebut. Pada sebuah celah (gap), tanggal melompat lebih dari satu sementara nomor baris bertambah tepat satu, sehingga kuncinya berubah.

Sinyal ketiga adalah disiplin kontrak. "Rentetan terpanjang" bersifat ambigu ketika dua rentetan memiliki panjang yang sama. Kueri yang menggunakan ROW_NUMBER() untuk memilih satu hasil secara diam-diam membuang hasil seri yang valid. Instruksi ini mewajibkan setiap nilai maksimum yang seri, sehingga jawabannya membandingkan setiap panjang island dengan panjang island maksimum untuk pengguna tersebut.

Sinyal keempat adalah kebenaran zona waktu. Melakukan casting login_at secara langsung ke date menggunakan zona waktu sesi database, yang mungkin berbeda antar-lingkungan. Jawaban ini mengonversi setiap timestamptz ke zona bisnis bernama terlebih dahulu dan baru kemudian mengambil tanggalnya. Offset UTC tetap tidak cukup untuk zona yang offset-nya berubah mengikuti aturan daylight saving time.

Sinyal terakhir adalah verifikasi dan penilaian skala. Kueri yang benar harus diuji pada setiap CTE, dengan event duplikat, rentetan satu hari, gap, hasil seri, kasus tengah malam lokal, dan batas daylight saving time. Pada tabel event besar yang sering dikueri, kandidat harus menyadari bahwa mereduksi event mentah menjadi satu baris tersimpan per user-day bisa lebih berharga daripada melakukan optimasi mikro pada kueri window akhir.

Pertanyaan yang Perlu Diklarifikasi Sebelum Menjawab

• Apa yang mendefinisikan suatu hari? Zona waktu bisnis bernama, UTC, atau zona waktu masing-masing pengguna akan mengubah konversi

tanggal dan mungkin jawabannya. Permintaan ini menggunakan America/New_York untuk setiap pengguna.

• Apakah beberapa login dalam satu hari dihitung lebih dari sekali? Di sini tidak, jadi deduplikasi harus dilakukan

sebelum penomoran. Jika metriknya adalah event berurutan, grain dan aturan pengelompokan akan berubah.

• Apakah satu tanggal yang hilang selalu memutus rentetan? Ya. Pertanyaan sessionization dengan ambang batas

30 menit memerlukan perbandingan baris sebelumnya alih-alih kedekatan kalender yang ketat.

• Bagaimana hasil seri harus dikembalikan? Kontrak ini mengembalikan setiap island terpanjang yang seri. Memilih rentetan

paling baru akan memerlukan pemecah seri (tie-breaker) yang berbeda dan eksplisit.

• Apakah rentang waktunya dibatasi? Filter tanggal dapat mengurangi beban kerja, tetapi juga memotong rentetan yang dimulai

sebelum rentang tersebut. Pemanggil harus menyatakan apakah hasilnya "di dalam rentang" atau rentetan lengkap yang melintasi batasnya.

• Bisakah user_id atau login_at bernilai null? Skema menyatakan tidak. Jika null diizinkan, penanganannya

harus ditentukan sebelum pengurutan atau pengelompokan.

• Apakah ini kueri satu kali atau metrik produk yang berulang? Jawaban ad hoc dapat memindai dan mengurutkan baris

harian. Dasbor yang sering diperbarui dapat menjustifikasi tabel user-day yang dikelola secara inkremental.

Kerangka Jawaban 30 Detik

“Pertama-tama saya akan mengonversi setiap timestamptz ke dalam zona waktu bisnis yang disepakati dan melakukan deduplikasi menjadi satu baris per pengguna dan tanggal lokal. Di dalam setiap pengguna, saya mengurutkan tanggal-tanggal tersebut dan menetapkan ROW_NUMBER(). Untuk tanggal berurutan yang ketat, login_day - row_number × one day tetap konstan di dalam sebuah rentetan dan berubah setelah adanya celah (gap), jadi saya mengelompokkan berdasarkan derived key tersebut untuk mendapatkan batas dan panjang setiap rentetan. Kemudian saya membandingkan setiap panjang dengan maksimum pengguna tersebut, yang mempertahankan hasil seri. Saya akan menguji event duplikat di hari yang sama, rentetan satu hari, gap, nilai maksimum yang sama, kasus tengah malam lokal dan daylight saving time, serta memeriksa execution plan pada data yang representatif.”

Pembahasan Mendalam Langkah demi Langkah

Mulailah dengan menormalkan aliran event ke grain bisnis. Untuk timestamptz, AT TIME ZONE dengan zona bernama menghasilkan timestamp jam dinding di zona tersebut. Melakukan casting hasil tersebut ke date menghasilkan tanggal kalender bisnis. SELECT DISTINCT kemudian menjamin tepat satu baris per user-day.

Kueri lengkapnya adalah:

WITH login_days AS (
  SELECT DISTINCT
    user_id,
    (login_at AT TIME ZONE 'America/New_York')::date AS login_day
  FROM user_logins
),
numbered AS (
  SELECT
    user_id,
    login_day,
    ROW_NUMBER() OVER (
      PARTITION BY user_id
      ORDER BY login_day
    ) AS rn
  FROM login_days
),
grouped AS (
  SELECT
    user_id,
    login_day,
    login_day - (rn * INTERVAL '1 day') AS island_key
  FROM numbered
),
streaks AS (
  SELECT
    user_id,
    MIN(login_day) AS streak_start,
    MAX(login_day) AS streak_end,
    COUNT(*) AS streak_days
  FROM grouped
  GROUP BY user_id, island_key
),
scored AS (
  SELECT
    user_id,
    streak_start,
    streak_end,
    streak_days,
    MAX(streak_days) OVER (PARTITION BY user_id) AS max_streak_days
  FROM streaks
)
SELECT
  user_id,
  streak_start,
  streak_end,
  streak_days
FROM scored
WHERE streak_days = max_streak_days
ORDER BY user_id, streak_start;

Pembuktian mengikuti baris harian yang terurut. Untuk satu pengguna, sebut tanggal-tanggal unik sebagai d1, d2, ... dan nomor baris sebagai 1, 2, .... Jika d(i+1) = d(i) + 1 day, maka mengurangkan offset nomor baris berikutnya akan menghilangkan hari ekstra yang sama, sehingga derived key-nya sama. Jika setidaknya satu tanggal hilang, d(i+1) bertambah dua hari atau lebih sementara nomor baris bertambah satu; derived key meningkat dan memulai grup baru. Deduplikasi membuat COUNT(*) sama dengan hari kalender, sementara MIN dan MAX adalah batas island yang tepat.

Maksimum akhir sengaja dibuat sebagai windowed MAX, bukan ROW_NUMBER() lainnya. Setiap island yang panjangnya sama dengan maksimum pengguna akan dipertahankan. Jika produk nantinya meminta hanya satu rentetan, tambahkan aturan yang dinyatakan seperti “tanggal akhir terbaru yang menang” dan gunakan pengurutan deterministik; jangan mengarang aturan tersebut di dalam kueri.

Perhatikan tanggal-tanggal yang dinormalisasi untuk dua pengguna:

user 1: Mar 07, Mar 08, Mar 09, Mar 11, Mar 12
user 2: Nov 01, Nov 02, Nov 04, Nov 05

result:
user 1 | Mar 07 | Mar 09 | 3
user 2 | Nov 01 | Nov 02 | 2
user 2 | Nov 04 | Nov 05 | 2

Pengguna 1 memiliki maksimum tiga hari. Pengguna 2 memiliki dua maksimum dua hari yang terpisah, sehingga kedua baris diperlukan. Beberapa event mentah pada tanggal mana pun yang ditampilkan tidak mengubah hasil. Di sekitar perubahan daylight saving time, pertanyaan yang relevan tetaplah apakah tanggal-tanggal lokal berurutan, bukan apakah timestamp berjarak tepat 24 jam.

Untuk N event mentah dan D baris user-day unik, deduplikasi membaca N baris dan dapat melakukan hashing atau sorting; langkah window mengurutkan hingga D baris berdasarkan pengguna dan tanggal. Batasan wawancara yang berguna adalah waktu O(N log N + D log D) dalam execution plan berbasis sort dan ruang perantara O(D), dengan catatan bahwa pengoptimal mungkin menggunakan hash, urutan yang ada, paralelisasi, atau tumpahan disk (disk spills). Execution plan, bukan Big-O semata, yang menentukan apakah kueri produksi dapat diterima.

Untuk metrik berulang pada miliaran event, buat tabel yang dikelola secara inkremental dengan unique key pada (user_id, login_day). Hal itu memindahkan konversi zona waktu dan deduplikasi hari yang sama ke tahap ingestion atau batch boundary, sehingga kueri rentetan membaca D baris harian alih-alih N event. Jika kueri ad hoc memiliki rentang waktu, terapkan batas timestamp UTC yang sargable sebelum konversi tanggal lokal, tetapi turunkan batas UTC tersebut dari tengah malam lokal zona bernama sehingga perubahan daylight saving time dihormati.

Periksa hasil perantara alih-alih memperlakukan tabel akhir sebagai bukti:

-- These checks are run against the corresponding CTE or materialized test result.
SELECT user_id, login_day, COUNT(*)
FROM login_days
GROUP BY user_id, login_day
HAVING COUNT(*) > 1;

SELECT *
FROM numbered
ORDER BY user_id, login_day;

SELECT *
FROM streaks
WHERE streak_days <> (streak_end - streak_start + 1);

Pemeriksaan pertama dan ketiga seharusnya tidak mengembalikan baris apa pun. Output bernomor membuat grain atau pengurutan yang salah menjadi terlihat. Jalankan kueri lengkap dengan awalan EXPLAIN (ANALYZE, BUFFERS) untuk mengungkap scans, sorts, estimasi baris, I/O sementara, dan apakah mereduksi event mentah lebih awal akan berpengaruh. Gunakan salinan representatif yang aman ketika mengeksekusi pernyataan produksi itu sendiri terlalu mahal.

Teknik shifted-date tidak bersifat universal. Jika sesi baru dimulai ketika celah (gap) melebihi 30 menit, atau sebuah island berlanjut selama nilai status tidak berubah, gunakan LAG() untuk memeriksa baris sebelumnya, tandai setiap batas, dan ambil running SUM() dari flag-flag tersebut. Aturan keputusannya sederhana: gunakan shifted key untuk urutan per-unit yang ketat; gunakan boundary flags ketika kontinuitas bergantung pada perbandingan kustom.

Contoh Jawaban Berkualitas Tinggi

“Sebelum menulis SQL, saya akan mengunci grain data dan kontrak hasil seri. Sumber data memiliki banyak event per pengguna, tetapi metrik ini menghitung satu tanggal kalender America/New_York per pengguna. Oleh karena itu, saya akan mengonversi timestamptz ke dalam zona bernama tersebut, melakukan cast ke date, dan melakukan deduplikasi sebelum fungsi window apa pun. Hal ini juga mencegah zona waktu sesi mengubah hasil secara diam-diam.

Untuk langkah gaps-and-islands, saya menetapkan ROW_NUMBER() yang diurutkan berdasarkan tanggal lokal di dalam setiap pengguna. Selama rentetan berurutan, baik tanggal maupun nomor baris bertambah satu, sehingga mengurangkan day offset dari nomor baris menghasilkan kunci yang konstan. Tanggal yang hilang membuat tanggal melompat lebih jauh daripada nomor baris dan mengubah kuncinya. Pengelompokan berdasarkan pengguna dan kunci tersebut menghasilkan tanggal mulai, selesai, dan jumlah tanggal aktif untuk setiap rentetan.

Saya akan menggunakan windowed maximum pada panjang rentetan dan mempertahankan baris yang bernilai sama dengan nilai maksimum tersebut. Hal ini mengembalikan semua rentetan terpanjang yang bernilai seri, sebagaimana diminta, alih-alih memilih salah satu secara diam-diam. Batas atas berbasis pengurutan (sort-based) kira-kira O(N log N + D log D), di mana N adalah event mentah dan D adalah user-days unik, meskipun saya akan memeriksa execution plan aktual dan disk spills.

Data uji saya akan mencakup beberapa event pada satu tanggal, pengguna dengan satu hari aktivitas, tanggal yang hilang, dua nilai maksimum yang sama, event di kedua sisi tengah malam lokal, dan transisi daylight saving time. Untuk metrik berskala besar yang berulang, saya akan mengelola tabel user-day yang unik dan menjalankan logika window di atas grain yang lebih kecil tersebut. Jika aturan kontinuitas berubah dari kedekatan kalender menjadi ambang batas jeda waktu, saya akan beralih ke LAG() ditambah boundary flags dan running sum.”

Kesalahan Umum

• Menomori event login mentah → event duplikat memajukan nomor baris dan menggelembungkan hitungan →

lakukan deduplikasi menjadi satu baris user-day sebelum menerapkan fungsi window.

• Melakukan cast timestamptz langsung ke date → jawabannya bergantung pada zona waktu sesi →

konversikan ke zona bisnis bernama terlebih dahulu.

• Menggunakan offset UTC tetap → tanggal lokal menjadi salah ketika zona bernama mengubah offset-nya →

gunakan zona IANA beserta aturan kalendernya.

• Membandingkan timestamp berjarak 24 jam → hari lokal 23 jam atau 25 jam memutus rentetan kalender yang valid

→ bandingkan tanggal lokal, karena kontraknya adalah kedekatan kalender.

• Hanya mengelompokkan berdasarkan shifted date → pengguna dengan derived key yang sama akan bergabung menjadi satu → **kelompokkan berdasarkan

user_id dan island_key.**

• Mengambil satu baris dengan ROW_NUMBER() → rentetan terpanjang yang bernilai seri akan terbuang → **bandingkan setiap island

dengan nilai maksimum per pengguna.**

• Memfilter interval pelaporan tanpa aturan batas → rentetan yang melintasi tanggal mulai akan

terpotong dan mungkin salah label → tentukan apakah hasilnya bersifat range-local atau island lengkap.

• Menggunakan LAG() tanpa menangani baris pertama → island pertama kehilangan batas awal → **perlakukan baris

sebelumnya yang bernilai null sebagai awal grup.**

• Hanya mengutip Big-O → sort spill atau estimasi kardinalitas yang buruk tetap tidak terlihat → **periksa

hitungan perantara dan EXPLAIN (ANALYZE, BUFFERS).**

• Memindai riwayat mentah untuk setiap refresh dasbor → konversi dan deduplikasi berulang mendominasi

biaya → kelola grain user-day unik jika beban kerja menjustifikasinya.

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan Lanjutan 1: Bagaimana cara Anda hanya mengembalikan rentetan terpanjang yang paling baru?

Pertahankan konstruksi island yang sama. Setelah menghitung rentetan, beri peringkat per pengguna berdasarkan streak_days DESC, lalu streak_end DESC, dan terakhir streak_start DESC sebagai pemecah seri deterministik terakhir. Kembalikan peringkat satu. Nyatakan bahwa ini mengubah kontrak output: panjang yang sama tidak lagi semuanya bertahan.

Pertanyaan Lanjutan 2: Apa yang berubah jika sesi berakhir setelah 30 menit tidak aktif?

Pengurangan kalender tidak lagi memodelkan kontinuitas. Urutkan event berdasarkan timestamp, gunakan LAG(login_at) per pengguna, tandai baris pertama atau celah apa pun yang lebih dari 30 menit sebagai sesi baru, dan hitung running SUM dari flag tersebut dengan frame ROWS UNBOUNDED PRECEDING yang eksplisit. Agregasikan berdasarkan pengguna dan session ID yang dihasilkan.

Pertanyaan Lanjutan 3: Bagaimana Anda menangani zona waktu masing-masing pengguna?

Gabungkan (join) event ke nilai zona waktu pengguna berversi yang valid untuk waktu event tersebut, lalu konversikan sebelum mengambil tanggalnya. Pengaturan profil tunggal saat ini dapat menulis ulang hari-hari historis setelah pengguna pindah. Klarifikasi apakah produk menginginkan aktivitas historis dibekukan di bawah zona waktu saat itu atau dihitung ulang di bawah zona waktu pengguna saat ini; keduanya merupakan metrik yang berbeda.

Pertanyaan Lanjutan 4: Bagaimana Anda mengueri hanya untuk 90 hari lokal terakhir?

Tentukan apakah rentetan boleh dimulai sebelum batas jendela waktu. Untuk hasil khusus dalam rentang (window-local), turunkan dua waktu UTC yang sesuai dengan tengah malam lokal pada awal dan akhir di zona bernama, filter login_at berdasarkan batas-batas tersebut, lalu normalisasi. Untuk island yang lengkap, sertakan baris harian sebelumnya yang cukup untuk menemukan gap nyata pertama; pemotongan 90 hari secara buta tidak dapat membuktikan awal mula yang sebenarnya.

Pertanyaan Lanjutan 5: Bagaimana Anda membuat ini efisien untuk dasbor harian?

Kelola user_login_days(user_id, login_day) dengan unique key dan idempotent upserts. Perbarui tabel tersebut dari pipeline event menggunakan aturan zona waktu yang disepakati. Hitung ulang hanya pengguna yang baris hariannya berubah, atau bangun ulang secara berkala dari jendela tumpang tindih (overlap window) untuk menyerap event yang datang terlambat. Rekonsiliasikan hitungan baris harian terhadap sumber mentah sebelum memublikasikannya.

Pertanyaan Lanjutan 6: Pengujian apa yang Anda wajibkan sebelum merilis ke produksi?

Gunakan fixture berbasis tabel untuk duplikat, pengguna satu baris, gap internal, nilai maksimum seri, event tengah malam lokal, awal dan akhir daylight saving time, event yang datang terlambat, dan event yang melintasi batas pelaporan. Pastikan bahwa baris harian bersifat unik, setiap island memenuhi streak_days = streak_end - streak_start + 1, dan setiap rentetan yang dikembalikan sama dengan nilai maksimum penggunanya. Bandingkan tabel harian inkremental dengan komputasi ulang event mentah pada sampel pengguna, lalu periksa rencana kueri dan I/O sementara pada kardinalitas yang menyerupai lingkungan produksi.