ملخص String للمقابلات البرمجية
مقدمة
الـString هي تسلسل من المحارف. والكثير من النصائح التي تنطبق على الـArrays تنطبق أيضاً على الـStrings. يُنصح بقراءة صفحة الـArrays قبل قراءة هذه الصفحة.
هياكل بيانات شائعة للبحث في الـStrings:
- Trie/Prefix Tree (Trie)
- Suffix Tree (Suffix Tree)
Algorithms شائعة للـStrings:
- Rabin Karp للبحث الفعال عن سلسلة فرعية باستخدام تجزئة متدرجة
- KMP للبحث الفعال عن سلسلة فرعية
الـtime complexity
الـString Array من المحارف، لذا فإن التعقيدات الزمنية لعمليات السلاسل الأساسية ستشبه إلى حد بعيد تعقيدات عمليات الـArrays.
| العملية | Big-O |
|---|---|
| الوصول | O(1) |
| البحث | O(n) |
| الإدراج | O(n) |
| الحذف | O(n) |
عمليات تتضمن String أخرى
نفترض هنا أن طول السلسلة الأخرى m.
| العملية | Big-O | ملاحظة |
|---|---|---|
| إيجاد سلسلة فرعية | O(n.m) | هذه هي الحالة الأكثر سذاجة. توجد Algorithms أكثر كفاءة للبحث في السلاسل مثل Algorithm KMP |
| تسلسل السلاسل | O(n + m) | |
| الاقتطاع (Slice) | O(m) | |
| التقسيم (برمز مميز) | O(n + m) | |
| التشذيب (إزالة المسافات البيضاء البادئة واللاحقة) | O(n) |
أمور يجب الانتباه إليها أثناء المقابلات
اسأل عن مجموعة محارف المدخلات وحساسية حالة الأحرف. فعادةً ما تكون المحارف محدودة بالأحرف اللاتينية الصغيرة، مثلاً من a إلى z.
الحالات الحدّية
- String فارغة
- String من محرف أو محرفين
- String بمحارف متكررة
- Strings بمحارف متميزة فقط
تقنيات
تقع العديد من أسئلة الـStrings ضمن إحدى هذه الفئات.
عدّ المحارف
ستحتاج غالباً إلى عدّ تكرار المحارف في String. وأكثر الطرق شيوعاً لذلك استخدام Hash Table/خريطة بلغتك المختارة. وإذا كانت لغتك تحتوي على صنف Counter مدمج كما في Python، فاسأل إن كان يمكنك استخدامه بدلاً من ذلك.
إذا احتجت إلى الاحتفاظ بعدّاد للمحارف، فمن الأخطاء الشائعة القول إن الـspace complexity المطلوب للعدّاد هو O(n). فالمساحة المطلوبة لعدّاد سلسلة من المحارف اللاتينية هي O(1) وليست O(n). وذلك لأن الحد الأعلى هو نطاق المحارف، وهو عادةً ثابت مقداره 26. فمجموعة المدخلات هي مجرد محارف لاتينية صغيرة.
String من محارف فريدة
حيلة أنيقة لعدّ محارف String من محارف فريدة هي استخدام قناع بتات من 26 بت للإشارة إلى المحارف اللاتينية الصغيرة الموجودة في السلسلة.
mask = 0
for c in word:
mask |= (1 << (ord(c) - ord('a')))ولتحديد ما إذا كانت سلسلتان تتشاركان محارف، نفّذ & على قناعي البتات. فإذا كانت النتيجة غير صفرية، أي mask_a & mask_b > 0، فإن السلسلتين تتشاركان محارف.
الجناس النامي (Anagram)
الجناس النامي هو إعادة ترتيب أحرف. وهو نتيجة إعادة ترتيب أحرف كلمة أو عبارة لإنتاج كلمة أو عبارة جديدة، مع استخدام جميع الأحرف الأصلية مرة واحدة فقط. وفي المقابلات لا نهتم عادةً إلا بالكلمات الخالية من المسافات.
لتحديد ما إذا كانت سلسلتان جناساً نامياً، هناك عدة أساليب:
- ترتيب السلسلتين ينبغي أن ينتج السلسلة الناتجة نفسها. يستغرق هذا زمناً O(n.log(n)) ومساحة O(n).
- إذا ربطنا كل محرف بعدد أولي وضربنا الأعداد المرتبطة ببعضها، فإن الجناس النامي ينبغي أن ينتج حاصل الضرب نفسه (التحليل إلى عوامل أولية). يستغرق هذا زمناً O(n) ومساحة O(1). أمثلة: Group Anagram
- عدّ تكرار المحارف يساعد على تحديد ما إذا كانت سلسلتان جناساً نامياً. ويستغرق هذا أيضاً زمناً O(n) ومساحة O(1).
النص المتناظر (Palindrome)
النص المتناظر هو كلمة أو عبارة أو عدد أو أي تسلسل آخر من المحارف يُقرأ بالاتجاه نفسه من الخلف إلى الأمام، مثل madam أو racecar.
فيما يلي طرق لتحديد ما إذا كانت String متناظرة:
- اعكس السلسلة وينبغي أن تساوي نفسها.
- ضع مؤشرين عند بداية السلسلة ونهايتها. حرّك المؤشرين نحو الداخل حتى يلتقيا. وفي كل لحظة ينبغي أن يتطابق المحرفان عند المؤشرين.
ترتيب المحارف داخل السلسلة مهم، لذا فإن Hash Tables لا تفيد عادةً.
عندما يكون السؤال عن عدّ النصوص المتناظرة، فإن حيلة شائعة هي استخدام مؤشرين يتحركان نحو الخارج مبتعدَين عن المنتصف. لاحظ أن النصوص المتناظرة قد تكون ذات طول زوجي أو فردي. ولكل موضع محوري في المنتصف، عليك فحصه مرتين — مرة يشمل المحرف ومرة دونه. تُستخدم هذه التقنية في Longest Palindromic Substring.
- بالنسبة للسلاسل الفرعية، يمكنك الإنهاء مبكراً فور عدم وجود تطابق
- وبالنسبة للتتاليات الفرعية، استخدم الـDynamic Programming لوجود مسائل فرعية متداخلة. اطّلع على هذا السؤال
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.