الأخبار التكنولوجية والاستعراضات والنصائح!
blogs5

تشفير أسئلة المقابلة – النمط 1 – المحاولات (الأشجار البادئة)

ستساعدك المقالة التالية: تشفير أسئلة المقابلة – النمط 1 – المحاولات (الأشجار البادئة)

أحد أكثر أسئلة مقابلة الترميز شيوعًا لشركات FAANG [Facebook (FB), Amazon (AMZN), Apple (AAPL), Netflix (NFLX); and Alphabet (GOOG) (formerly known as Google).] تشمل المحاولات. لدى Trie متغيرات متعددة. لكن من المهم جدًا معرفة بنية البيانات قبل الذهاب إلى المقابلات في الموقع. دعنا ندخل في تفاصيلها.

أهم أسئلة المقابلة المتعلقة بـ trie (يجب أن تتعلم) تشمل:

تنفيذ Trie Datastructure

تصميم البحث الإكمال التلقائي

التطبيق العملي – اقتراح محرك البحث التلقائي:

ضع في اعتبارك محرك بحث يقوم بالاقتراح التلقائي. كما هو موضح في الصورة أعلاه ، في اللحظة التي نبدأ فيها في كتابة الكلمات مثل “wh” ، نرى اقتراحات جمل منبثقة بناءً على الأحرف المكتوبة على سبيل المثال: أطعمة كاملة ، واتس اب وما إلى ذلك. تبدأ كل هذه الجمل المقترحة بالحروف “wh”. “. بينما نكتب المزيد من الأحرف ، تساعدنا جميع الاقتراحات ذات الصلة في جعل البحث أسرع.
إذا كان علينا تنفيذ هذا النوع من الوظائف ، فإن نهج القوة الغاشمة لتخزين جميع الجمل وتكرارها لمطابقة بادئات الجملة مع الأحرف المكتوبة لن يساعد على نطاق واسع.
Trie هو أفضل هيكل بيانات يمكن استخدامه في هذا النوع من السيناريوهات.

ما هو Trie؟

Trie (تسمى أيضًا شجرة البادئة) هي نوع من شجرة البحث ، حيث توجد كل عقدة

  1. خريطة لجميع الأطفال بالمفتاح: الحرف التالي ، القيمة: عقدة الحرف التالي. سبب تعيين الأطفال كخريطة هو أن البحث يمكن أن يكون أسرع باستخدام حرف البداية بدلاً من القائمة.
  2. قيمة منطقية سواء كانت العقدة الحالية ورقة أم لا.
1 2 3 4فئة TrieNode {Map childMap؛ أميليف منطقية ؛ }

نموذج العينة:

ضع في اعتبارك الجمل النموذجية مثل “ماذا” ، “whatsapp” ، “كامل” ، “أطعمة كاملة” يمكن تمثيل هذه الجمل بتنسيق trie على النحو التالي:

نموذج لقائمة الكلمات: “ماذا” ، “whatsapp” ، “كامل” ، “أطعمة كاملة”

العقدة الجذرية في المثلث فارغة دائمًا. لذا فإن العقدة الزرقاء في الصورة أعلاه فارغة. ولكن يمكن أن يكون لها عدة أطفال.
كما يمكننا أن نرى من التمثيل الثلاثي ، نظرًا لأن جميع كلمات العينة تبدأ بالحرف نفسه “w” ، فإن العقدة الجذرية (باللون الأزرق) لديها طفل واحد فقط لديه Node (“w”). العقدة ‘w’ لها عقدة فرعية واحدة ‘h’ لأن كل الكلمات تبدأ بـ ‘wh’. العقدة (‘h’) لها عقدتان فرعيتان Node (‘a’) و Node (‘o’) لأن الكلمات يمكن أن تبدأ بـ ‘wha’ أو ‘who’. وبالمثل ، فإن الكلمات التي تبدأ بـ “wha” تحتوي على “t” كالحرف التالي. لذا ، فإن Node (‘t’) هي العنصر الفرعي لـ Node (‘a’) .. عندما نصل إلى Node (‘t’) ، نرى أن ‘what’ هو في الواقع جزء من عينة قائمة الكلمات. لذلك يتم وضع علامة على العقدة (‘t’) كعقدة ورقية مع amILeaf المنطقي المتغير على أنه صحيح. كما تحتوي العقدة (‘t’) على حرف تالٍ محتمل مثل ‘s’ من الكلمة (‘whatsapp’). لذلك فهي تحتوي على عقدة (عقدة) فرعية واحدة ويستمر الهيكل بأكمله حتى يتم تغطية جميع الكلمات كجزء من العقد الورقية.

بناء / إدخال العقد:
نقوم ببناء Trie عن طريق تكرار كل كلمة من كلمات الإدخال واحدة تلو الأخرى. يتم أخذ كل حرف من كلمة الإدخال ويتم تكوين العلاقات. لقائمة العينات: “ماذا” ، “whatsapp” ، “كامل” ، “أطعمة كاملة” ، يتم تكرار كل كلمة وإدراجها في trie مع الكود أدناه:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20فئة TrieNode {Map childMap؛ أميليف منطقية ؛ } / ** يُدرج كلمة في المثلث. * / إدراج الفراغ العام (TrieNode root، String word) {TrieNode node = root؛ لـ (char w: word.toCharArray ()) {if (node.map.get (w) == null) {TrieNode child = new TrieNode ()؛ node.map.put (ث ، طفل) ؛ } عقدة = node.map.get (w) ؛ // تم تغيير مرجع العقدة إلى العقدة الحالية. } node.isLeaf = صحيح ؛ }

بالنسبة للكلمة “ماذا” ، يتم إدراج “w” و “h” و “a” و “t” حرفًا بحرف. من الطفل ، تم الاستعلام عن خريطة الجذر ‘w’. إذا كان فارغًا ، يتم إنشاء TrieNode تابع جديد وإدراجه في الخريطة الجذرية. إذا كانت العقدة موجودة بالفعل ، فسيستمر الحرف التالي من خلال تعيين العقدة بالحرف الحالي. إذا لم يكن هناك المزيد من الأحرف المتبقية ، فسيتم وضع علامة على العقدة على أنها ورقة
تستمر نفس العملية لجميع الكلمات المتبقية.

تعقيد الوقت: O (m) ، حيث m هو طول الكلمة. في كل تكرار للخوارزمية ، إما أن نفحص أو ننشئ عقدة في المثلث حتى نصل إلى نهاية الكلمة.

تعقيد الفضاء: O (م). في أسوأ الحالات ، لا يشترك المفتاح الذي تم إدخاله حديثًا في بادئة مع المفاتيح التي تم إدخالها بالفعل في المثلث. يجب أن نضيف عقدًا جديدة مم ، والتي تأخذنا مساحة (م).

يبحث:

1 2 3 4 5 6 7 8 9 10 11 12 13/ ** تُرجع إذا كانت الكلمة في trie. * / البحث المنطقي العام (TrieNode root، String word) {Trie node = root؛ لـ (char ch: word.toCharArray ()) {if (node.map.get (ch) == null) {return false؛ } node = node.map.get (ch)؛ } عودة node.isLeaf؛ }

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

تعقيد الوقت: O (m): m هو طول الكلمة المراد البحث عنها. تعقيد الفضاء: O (1)

يمكن تطبيق نهج مماثل على مشكلة الاقتراح التلقائي. في البداية يتم إنشاء trie مع جميع الجمل الممكنة. بالنسبة لكلمة الإدخال المحددة ، يمكن الاستعلام عن ثلاثي لجميع الكلمات المطابقة للبادئة التي تم البحث عنها.

نحن نوصيك: