حسنا ها انت ذا. مرتاح. أرهق. لقد توصلت أخيرًا إلى طريقة لحل مسألة الترميز الصعبة التي يسألك القائم بإجراء المقابلة عليها. ربما كنت قد كتبت حتى على السبورة البيضاء ، سطرا سطرا. وقمت بوقت جيد! أنت فقط 20 دقيقة في الاجتماع. فلدي انطباعك في المقابلة.
حق؟
"هذا سوف ينجح ، ولكن أي أفكار حول كيفية القيام بذلك بشكل أكثر كفاءة؟"
يغرق قلبك. كنت تعتقد أنك فعلت مع جزء تصميم خوارزمية صعبة! تحاول التفكير في طرق أكثر لحل المشكلة ، لكن كل ما يمكنك التفكير فيه هو الطريقة الوحيدة التي توصلت إليها بالفعل.
هذا يحدث للجميع تقريبا. وهذا ليس لأنهم أغبياء. ذلك لأن معظم الناس ليس لديهم طريقة لتحسين كفاءة الخوارزميات الخاصة بهم.
ولكن الحقيقة هي أن هناك الكثير. في المرة القادمة التي تتعثر فيها ، حاول تطبيق هذه الطرق الثلاثة الشائعة.
1. استخدام خريطة التجزئة
هذا صحيح. تتمتع خرائط التجزئة / المصفوفات / القواميس الترابطية (التي تحمل أسماء كثيرة ، اعتمادًا على لغة البرمجة التي تستخدمها) بقدرة سحرية على تقليل وقت تشغيل الخوارزميات.
على سبيل المثال ، افترض أن السؤال كان للعثور على الرقم الأكثر تكرارًا في مجموعة من الأرقام.
قد تكون فكرتك الأولى هي القفز إلى بعض الحلقات. لمعرفة كل رقم من أرقامنا ، حدد عددها ومعرفة ما إذا كان العدد أكبر. كيف نحصل على عدد لكل رقم؟ حلقة من خلال مجموعة ، العد كم مرة يحدث! لذلك نحن نتحدث عن حلقتين متداخلتين. في الكود الكاذب:
def get_mode (nums): max_count = 0 mode = null for potential_mode in nums: count = 0 for number in our_array: count + = 1 if count> = max_count: mode = potential_mode max_count = count return mode
في الوقت الحالي ، ندخل في صفيفنا بالكامل مرة واحدة لكل عنصر في الصفيف - لكن يمكننا أن نفعل ما هو أفضل. في تدوين كبير O ، هذا هو إجمالي وقت O (n 2 ).
إذا قمنا بتخزين تعداداتنا في خريطة التجزئة (تعيين الأرقام إلى تعداداتها) ، فيمكننا حل المشكلة في وقت واحد فقط خلال المصفوفة (O (n)!):
def get_mode (nums): max_count = 0 mode = null counts = HashMap جديدة ، وتبدأ كل قيمة عند 0 بالنسبة للقيمة المحتملة في nums: counts + = 1 إذا كانت التهم الموجهة> max_count: mode = potential_mode max_count = counts return mode
أسرع بكثير!
2. استخدام التلاعب بت
هذا سوف يميزك حقًا عن العبوة. لا ينطبق ذلك على كل مشكلة ، ولكن إذا احتفظت بهذا في جيبك الخلفي وقمت بإسقاطه في الوقت المناسب ، فستبدو مثل نجم.
إليك مثال: افترض أن لدينا مجموعة من الأرقام ، حيث يظهر كل رقم مرتين ، باستثناء رقم واحد يحدث مرة واحدة فقط. نكتب وظيفة للعثور على الرقم الوحيد غير المتكرر.
قد تكون غريزتك الأولى هي استخدام خريطة التجزئة ، لأننا تحدثنا عنها للتو. هذا غريزة جيدة لديهم! وستعمل لهذا واحد. يمكننا إعداد خريطة "تهم" متشابهة جدًا ، واستخدامها لمعرفة العدد الذي سينتهي بعدد 1.
ولكن هناك طريقة أفضل. إذا كنت معتادًا على معالجة الشيء ، فقد تكون على دراية بـ XOR. شيء واحد مميز حول XOR هو أنه إذا قمت بتدوين رقم XOR بنفسه ، فإن البتات "تلغي" إلى 0. لهذه المشكلة ، إذا قمنا بتطبيق XOR على كل رقم في المصفوفة معًا ، فسنترك برقم واحد لم يحدث. لا تلغي:
def find_unrepeated (nums): unrepeated = 0 للرقم بالأرقام: unrepeated = unrepeated XOR num return unrepeated
3. الذهاب من أسفل إلى أعلى
اكتب دالة تقوم بإخراج رقم فيبوناتشي "nth" ، مع إعطاء رقم n. هذا كلاسيكي ، ويعد نفسه جيدًا جدًا للتكرار:
def fib (n): إذا كانت n 0 أو 1: return 1 return fib (n-1) + fib (n-2)
لكن الإجابة العودية البسيطة ليست هي الوحيدة! فكر جيدًا فيما تفعله هذه الوظيفة. لنفترض أن n هي 5. للحصول على الإجابة ، فإنها تستدعي بشكل متكرر fib (4) و fib (3). الآن ، ماذا تفعل هذه الدعوة إلى fib (4)؟ يطلق عليه fib (3) و fib (2). لكننا قلنا للتو لدينا بالفعل دعوة إلى fib (3)! هذه الوظيفة العودية لطيف يفعل الكثير من تكرار العمل. وتبين أن التكلفة الإجمالية للوقت هي O (2 n ). هذا سيء - أسوأ بكثير من O (n 2 ).
بدلاً من الانتقال من n بشكل متكرر إلى 1 ، دعنا نذهب "من أسفل إلى أعلى" من 1 إلى n. هذا يتيح لنا تخطي العودية:
def fib (n): السابق = 0 previous_previous = 1 لـ i في النطاق 1 إلى n: الحالي = السابق + السابق_p السابقة previous_previous = السابق السابق = الحالي المرتجع الحالي
الرمز أطول ، لكنه أكثر فاعلية! وصولا الى O (ن) الوقت. على سبيل المكافأة المضافة مع خوارزميات العودية التمرير ، ونحن توفير مساحة. تتراكم جميع تلك المكالمات المتكررة في مكدس المكالمات ، والذي يجلس في الذاكرة ويستند إلى تكلفة مساحتنا. كان لدينا وظيفة متكررة تكلفة مساحة O (ن) ، ولكن هذه واحدة تكرارية تأخذ مساحة O (1).
في المرة القادمة يطلب منك القائم بإجراء المقابلة تحسين كفاءة حلك ، حاول استعراض هذه الاستراتيجيات ومعرفة ما إذا كانت تساعد. من خلال الممارسة الكافية ، من المحتمل أن تجد نفسك تقفز مباشرة إلى الحل الأمثل ، وتتخطى الحل الأكثر سذاجة. وهذا شيء عظيم. هذا لا يعني فقط أنك تصبح محاورًا أفضل - فهذا يعني أنك تصبح مهندسًا أفضل.
