ملخص الهندسة للمقابلات البرمجية

مقدمة

الهندسة فرع من الرياضيات يهتم بخصائص الفضاء المرتبطة بالمسافة والشكل والحجم والموضع النسبي للأشكال. والهندسة المتقدمة (مثل الهندسة ثلاثية الأبعاد) لا تُدرَّس في معظم مساقات علوم الحاسوب، لذا يمكنك توقع أن الأسئلة ستقتصر على الهندسة ثنائية الأبعاد.

في مقابلات الـAlgorithms، لا تكون الهندسة عادةً محور المسألة (فأنت لا تُقيَّم على الرياضيات في نهاية المطاف). وستحتاج عادةً إلى استخدام Algorithms أو هياكل بيانات أخرى في المسألة.

الحالات الحدّية

• القيم الصفرية. وهي ما يوقع الناس دائماً.

تقنيات

المسافة بين نقطتين

عند مقارنة المسافة بين نقطتين، يكفي استخدام dx² + dy². ولا داعي لأخذ الجذر التربيعي للقيمة. أمثلة: K Closest Points to Origin

الدوائر المتداخلة

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

المستطيلات المتداخلة

يتداخل مستطيلان إذا تحقق ما يلي:

overlap = rect_a.left < rect_b.right and \
  rect_a.right > rect_b.left and \
  rect_a.top > rect_b.bottom and \
  rect_a.bottom < rect_b.top

إليك تصوراً مرئياً لطيفاً. أمثلة: Rectangle Overlap

أسئلة نموذجية

• لديك مستوٍ عليه مستطيلات كثيرة، اكتشف كم منها يتقاطع.
• أي بنية بيانات ستستخدم للاستعلام عن أقرب k نقاط من مجموعة على مستوٍ ثنائي الأبعاد؟
• بالنظر إلى نقاط كثيرة، جد k نقاط هي الأقرب إلى نقطة الأصل.
• كيف تُضلّع مضلعاً (تقسمه إلى مثلثات)؟

أسئلة أساسية

هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.

• Rectangle Overlap

أسئلة تدريب موصى بها

هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.

• K Closest Points to Origin
• Rectangle Area

المصدر والرخصة

هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.