ملخص Trie للمقابلات البرمجية
مقدمة
Tries هي Trees خاصة تجعل البحث عن الـStrings وتخزينها أكثر كفاءة. ولـTries تطبيقات عملية كثيرة، مثل إجراء عمليات البحث وتقديم الإكمال التلقائي. ومن المفيد معرفة هذه التطبيقات الشائعة كي تتمكن بسهولة من تحديد متى يمكن حل مسألة بكفاءة باستخدام Trie.
كن على دراية بتنفيذ صنف Trie من الصفر مع توابعه add وremove وsearch.
مصادر التعلم
- قراءات
- Trying to Understand Tries، basecs
- Implement Trie (Prefix Tree)، LeetCode
- إضافية (فقط إذا كان لديك وقت)
الـtime complexity
حيث m هو طول الـString المستخدمة في العملية.
| العملية | Big-O |
|---|---|
| البحث | O(m) |
| الإدراج | O(m) |
| الحذف | O(m) |
الحالات الحدّية
- البحث عن String في Trie فارغة
- إدراج Strings فارغة في Trie
تقنيات
في بعض الأحيان، تؤدي المعالجة المسبقة لقاموس كلمات (معطى في قائمة) وتحويله إلى Trie إلى تحسين كفاءة البحث عن كلمة طولها k بين n كلمة. فيصبح البحث بزمن O(k) بدلاً من O(n).
أسئلة أساسية
هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.
أسئلة تدريب موصى بها
هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.
المصدر والرخصة
هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.