Coding Interview Prep · درس

العثور على الفجوات في تسلسل

اكتشاف القيم المفقودة وبداية كل فجوة ونهايتها

العثور على الفجوات في تسلسل درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

الآن ابحث عن الفجوات

حتى الآن جمّعنا الصفوف في جزر. أما سؤال المقابلة المعاكس فهو: ما القيم المفقودة؟ وقد يصوغه القائمون بالمقابلات بعبارات مثل «اعثر على الفجوات في متتالية المعرّفات هذه»، أو «ما أرقام الفواتير التي تم تخطيها؟»، أو «في أي أيام لم يُسجَّل أي نشاط؟».

الفجوات هي المساحات الفارغة بين الجزر. والفكرة الأساسية هي أنك لا تحتاج عادةً إلى سرد كل قيمة مفقودة؛ بل تحتاج إلى الإبلاغ عن بداية ونهاية كل نطاق فجوة، وهو تمثيل أكثر اختصارًا وما يتوقعه القائمون بالمقابلات.

مجموعة بيانات الفجوات النموذجية

أعد استخدام القيم الموجودة 1, 2, 3, 7, 8, 10 من جدول seq(n). الفجوات المطلوب الإبلاغ عنها هي:

من 4 إلى 6 (بعد الجزيرة الأولى وقبل 7)
من 9 إلى 9 (بين 8 و10)

لاحظ أننا نصف الفجوة على شكل نطاق: gap_start = آخر قيمة موجودة + 1، وgap_end = القيمة الموجودة التالية - 1. هذا التمثيل المختصر هو هدف الأسلوب الأساسي التالي.

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

أسلوب LEAD للعثور على الفجوات

أوضح كاشف للفجوات يقارن كل صف بالصف التالي باستخدام LEAD. فإذا كانت القيمة التالية أكبر من القيمة الحالية بأكثر من 1، فهناك فجوة بينهما.

لكل صف من هذه الصفوف، تبدأ الفجوة عند n + 1 وتنتهي عند next_n - 1. اطلع أولًا على ناتج LEAD الخام:

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

الإبلاغ عن نطاقات الفجوات

ضع ناتج LEAD داخل CTE، واحتفظ بالصفوف التي تتجاوز فيها القفزة إلى القيمة التالية 1 فقط. تمثل هذه الصفوف الفجوات:

يعيد هذا فجوتَي 4-6 و9-9 بالضبط. كما تعطي الصيغة next_n - n - 1 عدد القيم المفقودة في كل فجوة، وهو سؤال متابعة شائع.

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

صيغة LAG المتماثلة

يمكنك اكتشاف الفجوات نفسها بالنظر إلى الخلف باستخدام LAG بدلًا من ذلك. توجد فجوة قبل الصف الحالي عندما تكون القيمة السابقة أقل منه بأكثر من 1.

الطريقتان متكافئتان تمامًا؛ فاختر الصيغة التي تبدو أكثر طبيعية في سياق السؤال. ويفضّل بعض القائمين بالمقابلات LEAD لأن الفجوة توصف بالنسبة إلى الصف الذي يسبقها، وهو ما يطابق طريقة تعبير الناس.

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

سرد كل قيمة مفقودة

أحيانًا يريد القائم بالمقابلة بالفعل القائمة الكاملة للأرقام المفقودة، لا النطاقات فقط. الأسلوب الموثوق هو إنشاء المتتالية المتوقعة الكاملة وتنفيذ anti-join عليها مقابل القيم الموجودة. في Postgres، تنشئ generate_series النطاق الكامل:

كل عدد صحيح ضمن النطاق المتوقع وغير موجود في seq هو قيمة مفقودة. ويتعامل هذا أيضًا مع الفجوات عند الطرفين تمامًا إذا كنت تعرف الحدين الأدنى والأقصى المقصودين.

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

إنشاء المتتاليات عبر لهجات SQL

لا يحتوي كل محرك على generate_series. تعرّف على البدائل:

Postgres: generate_series(1, 100).
SQL Server: ‏CTE تكراري أو جدول أرقام/عدّ.
MySQL 8: ‏CTE تكراري يعدّ تصاعديًا حتى القيمة القصوى.

يمثل CTE التكراري البديل القابل للنقل بين المحركات. فهو ينتج المتتالية المتوقعة نفسها لإجراء anti-join عليها.

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

فجوات تواريخ التقويم

للعثور على التواريخ المفقودة، أنشئ تقويمًا كاملًا بخطوة يومية ثم نفّذ anti-join. هذا هو الاستعلام القياسي لمعرفة «ما الأيام التي لم تُسجَّل فيها طلبات؟»:

ادمج ذلك مع أسلوب النطاقات بتطبيق LEAD على التواريخ الفعلية للإبلاغ عن فترات التواريخ المفقودة بدلًا من الأيام الفردية، باستخدام + INTERVAL '1 day' للحدود.

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

الفجوات الطرفية خارج نطاق البيانات

هناك فخ دقيق: لا يعثر LEAD/LAG إلا على الفجوات بين القيم الموجودة. فإذا كان رقم ما مفقودًا قبل أصغر قيمة موجودة أو بعد أكبر قيمة موجودة، فلن يتمكن أسلوب النوافذ من رؤيته لعدم وجود صف مجاور.

إذا حدد القائم بالمقابلة نطاقًا كاملًا متوقعًا (مثل المعرّفات من 1 إلى 100) وبدأت بياناتك عند 5، فيجب عليك استخدام generate-series anti-join المقيّد بالنطاق المعلن، لا الحدين الأدنى والأقصى للبيانات نفسها. استوضح دائمًا ما إذا كانت الحدود المتوقعة ثابتة.

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

اكتشاف الفجوات لكل مجموعة

للعثور على الفجوات لكل مستخدم، قسّم نتائج LEAD/LAG بحسب عمود المجموعة، حتى لا يتم الإبلاغ عن فجوة بين تدفقي مستخدمين مختلفين:

تُحسب النطاقات المفقودة لكل مستخدم بشكل مستقل. وكما هو الحال مع الجزر، يؤدي نسيان التقسيم إلى دمج المستخدمين بصمت وإنشاء فجوات وهمية تمتد عبر صفوف غير مرتبطة.

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

اختيار طريقة الفجوات المناسبة

دليل اتخاذ القرار في المقابلة:

إذا كنت تريد نطاقات مختصرة وفجوات داخلية فقط، فاستخدم LEAD/LAG، مع تصفية الحالات التي تتجاوز فيها الخطوة 1.
إذا كنت تريد كل قيمة مفقودة على حدة أو الفجوات خارج حدود البيانات، فاستخدم generate-series anti-join مقابل النطاق الكامل المعلن.

إن ذكر الخيارين وبيان وقت ملاءمة كل منهما يدل على عمق الفهم. طريقة LEAD أقل تكلفة، بينما طريقة المتتالية أشمل.

تحقق سريع

حدّد الفخ المتعلق بالحالات الطرفية.

مراجعة: العثور على الفجوات

أصبح اكتشاف الفجوات واضحًا:

أبلغ عن الفجوات على شكل نطاقات: gap_start = القيمة + 1، وgap_end = القيمة التالية - 1.
يكتشف LEAD (أو LAG المتماثل) الفجوات الداخلية بتكلفة منخفضة عند تصفية الحالات التي تتجاوز فيها الخطوة 1.
يسرد generate-series anti-join كل قيمة مفقودة، ويكتشف الفجوات الطرفية ضمن نطاق معلن.
تنشئ CTEs التكرارية المتتالية عندما لا يتوفر generate_series.
قسّم بحسب عمود المجموعة للعثور على فجوات كل مستخدم.
استوضح دائمًا الحدود المتوقعة.

وأخيرًا، سنتناول الصيغة الأكثر ثراءً: الجزر التي يحددها التاريخ وتغيّر الحالة.

الأسئلة الشائعة

هل درس «العثور على الفجوات في تسلسل» مجاني؟

نعم — نص درس «العثور على الفجوات في تسلسل» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.

ماذا ستتعلم في «العثور على الفجوات في تسلسل»؟

اكتشاف القيم المفقودة وبداية كل فجوة ونهايتها تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.

هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟

لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.

كم من الوقت يستغرق درس «العثور على الفجوات في تسلسل»؟

معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.

هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟

نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.

جميع الدروس في هذه الدورة

← العودة إلى Coding Interview Prep