دليل أسئلة المقابلة الشخصية من Google: احذف الأحرف المتكررة باستخدام Python

في الوقت الحاضر ، أصبحت المقابلات عبر Google شائعة. لكن في بعض الأحيان ، يمكن أن تكون المقابلات أفضل منا. خاصة إذا كان ذلك لمنصب نريده حقًا .

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

هدفي هو مساعدة لك الحصول على هذا المنصب حلم كنت أريد دائما!

سننتقل إلى سؤال كلاسيكي يمكن أن يظهر في مقابلة Google التالية.

تحذير: إذا كنت خبيرًا في البرمجة ، فمن المحتمل أنك تعرف بالفعل كيفية حل هذا السؤال!

إذا كنت تحاول الحصول على تدريب أو وظيفة بدوام كامل العام المقبل ، فستستفيد بالتأكيد من هذه المقالة. ؟؟؟

سؤال: إعطاء سلسلة كمدخلاتك ، احذف أي حرف متكرر ، وأعد السلسلة الجديدة.

إذا كنت تفضل مقطع فيديو لشرح السؤال ، فقد قمت بعمل واحد هنا.

كما نرى من المثال أعلاه ، فإن الناتج هو "abc" لأننا نحذف الثانية "a" و "b" و "c".

أول الأشياء أولاً ، لنقم بإعداد وظيفتنا في Python 2.7.

def deleteReoccurringCharacters(string):

لمعالجة هذا السؤال ، سنستخدم بنية بيانات محددة تسمى HashSet.

يمكنك التفكير في مجموعة على أنها مشابهة لمصفوفة ، مع استثناءين رئيسيين.

  1. إنه غير مرتب تمامًا
  2. لا يمكن أن تحتوي على نسخ مكررة

نظرًا لأنه غير مرتب ، سنحتاج أيضًا إلى سلسلة فارغة لتخزين الأحرف التي أضفناها إلى المجموعة بالترتيب. ستكون هذه هي السلسلة التي نعود إليها.

دعنا نضع هذين الأمرين.

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = ''

الآن بعد أن أعددنا هياكل البيانات التي نحتاجها ، فلنتحدث عن الخوارزمية الخاصة بنا.

نظرًا للطريقة التي تعمل بها المجموعة في الذاكرة ، فإن لها تعقيدًا في وقت البحث يبلغ 0 (1).

هذا يعني أنه يمكننا استخدامه للتحقق مما إذا كنا قد زرنا بالفعل شخصية أم لا!

خوارزمية لدينا

قم بالتكرار خلال جميع الأحرف في السلسلة الأولية وقم بما يلي:

الخطوة 1: تحقق مما إذا كان الحرف موجودًا في مجموعتنا بالفعل الخطوة 2: إذا لم يكن موجودًا في المجموعة ، فقم بإضافته إلى المجموعة وإلحاقه بالسلسلة

دعونا نرى كيف سيبدو ذلك في الكود ؟؟؟

for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char

لا داعي للقلق بشأن حالة "أخرى" ، لأننا لا نفعل أي شيء مع الشخصية المتكررة نفسها.

كل ما تبقى الآن هو إرجاع سلسلة الإخراج.

إليك ما تبدو عليه الشفرة النهائية:

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char return outputString

وهناك لديك!

الآن إذا كانت هذه مقابلة ، سيسألك المجند عن الوقت والمكان المعقد.

لنقم بتحليل بسيط.

تعقيد الوقت

التكرار خلال سلسلة الإدخال بأكملها له تعقيد زمني لـ O (n) ، نظرًا لوجود حرف n في السلسلة نفسها.

لكل من هذه الأحرف ، يتعين علينا التحقق مما إذا كنا قد رأينا ... ومع ذلك ، نظرًا لأن HashSet لديه وقت بحث O (1) ، فلن يتأثر تعقيد الوقت لدينا.

مما يترك لنا معقدًا زمنيًا نهائيًا لـ O (n).

تعقيد الفضاء

أسوأ سيناريو ، نحصل على سلسلة بها جميع الأحرف الفريدة. على سبيل المثال ، "abcdef".

في هذه الحالة ، سنخزن جميع العناصر n في السلسلة والمجموعة الخاصة بنا.

ومع ذلك ، فإننا مقيدون أيضًا بحجم الأبجدية الإنجليزية.

هذه فرصة جيدة لسؤال المحاور لدينا عن نوع الأحرف التي تعتبر فريدة في السلسلة (أحرف كبيرة / صغيرة / أرقام / رموز).

بافتراض أن السلسلة الأولية ستحتوي على أحرف صغيرة من الأبجدية ، نظرًا لأن الأبجدية محدودة ، لا يمكن أبدًا أن تكون المجموعة وسلسلة الإخراج لدينا أكبر من 26 حرفًا.

يترك لنا أسوأ سيناريو معقد الفضاء لـ O (1).

أنت تعرف الآن كيفية حل سؤال مقابلة Google!

من المحتمل أن يتم طرح هذا السؤال في المراحل الأولى من المقابلة نظرًا لبساطته ... مثل الاختبار عبر الإنترنت ، أو المكالمة الهاتفية الأولى.

إذا كنت متعلمًا بصريًا مثلي ، فاطلع على هذا الفيديو الذي صنعته لشرح الحل بشكل أكبر. أقوم بإنشاء فيديو تعليمي جديد كل يوم يدور حول بدء حياتك المهنية في مجال البرمجيات.

لقد قمت أيضًا بنشر الكود النهائي على Github هنا.

شكرا للمشاهدة ، ونتمنى لك التوفيق!

أ # 33