دليل أسئلة مقابلة Python: كيفية ترميز قائمة مرتبطة

لقد فهمت دائمًا المفهوم الأساسي للقوائم المرتبطة ، لكنني لم أقم بتطبيقه مطلقًا.

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

ولهذا السبب أكتب هذا الدليل!

هدفي هو مساعدة لك الحصول على وظيفة مهندس برمجيات.

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

ما هي القائمة المرتبطة؟

القائمة المرتبطة هي بنية بيانات تتكون من العديد من هياكل البيانات المصغرة تسمى "العقد". ترتبط العقد معًا لتشكيل قائمة.

كل عقدة تحتوي على سمتين

  1. قيمته. يمكن أن يكون هذا أي شيء: أعداد صحيحة ، أحرف ، سلاسل ، أشياء ، وما إلى ذلك.
  2. مؤشر إلى العقدة التالية في التسلسل.

بعض التعاريف

"العقدة الرئيسية": العقدة الرئيسية هي ببساطة العقدة الأولى في القائمة المرتبطة. كما نرى من المثال أعلاه ، فإن العقدة التي تحتوي على "5" هي العقدة الأولى ، وبالتالي الرأس.

"عقدة الذيل": عقدة الذيل هي العقدة الأخيرة في التسلسل. نظرًا لأنها العقدة الأخيرة ، فإنها تشير إلى خالية ، لأنه لا توجد عقدة تالية في التسلسل. في المثال أعلاه ، ستكون العقدة التي تحتوي على '3' هي عقدة الذيل.

مرتبط فردي مقابل ربط مضاعف

عندما يتعلق الأمر بالقوائم المرتبطة ، هناك نوعان رئيسيان.

تلك المرتبطة "بشكل فردي" وتلك المرتبطة "بشكل مزدوج".

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

يعني الارتباط المضاعف أن كل عقدة يمكن أن تشير إلى عقدتين أخريين ، والعقدة الموجودة أمامها والعقدة الموجودة خلفها. كما نرى من المثال أدناه ، نظرًا لعدم وجود عقدة تسبق عقدة الرأس (وهي 5) ، يشير أحد مؤشراتها إلى قيمة خالية.

حسنًا ، أفهم كل ذلك. لكن كيف يعمل الكود؟

يمكن أن يكون ترميز القوائم المرتبطة مشكلة من 4 أسطر أو مشكلة من 400 سطر. يعتمد ذلك على الطريقة التي تريد التعامل معها.

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

وبالتالي ، كل ما نحتاجه حقًا لإنشاء هذه البنية هو كائن عقدة.

class linkedListNode: def __init__(self, value, nextNode=None): self.value = value self.nextNode = nextNode

هنا يمكننا أن نرى أننا قمنا ببساطة بإنشاء فئة لها قيمة وسمة nextNode.

لإنشاء عقدة ، نقوم ببساطة بتمرير قيمة.

node1 = linkedListNode("3") # "3"node2 = linkedListNode("7") # "7"node3 = linkedListNode("10") # "10"

هنا ، قمنا بإنشاء 3 عقد فردية.

الخطوة التالية هي ببساطة توصيلهم معًا.

node1.nextNode = node2 node2.nextNode = node3 

السطر الأول أعلاه يجعل العقدة 1 تشير إلى العقدة 2:

"3" ← "7"

السطر الثاني أعلاه يجعل العقدة 2 تشير إلى العقدة 3:

"7" ← "10"

معًا ، يتبقى لدينا قائمة مرتبطة تبدو كالتالي:

"3" → ”7" → ”10" → لاغية

ملاحظة: يشير الرقم "10" إلى قيمة خالية ، لأنه لم يتم تعيين العقدة التالية للعقدة 3 ، والعقدة الافتراضية nextNode هي Null.

كما ذكرت سابقًا ، هناك الكثير من الطرق المختلفة للقيام بذلك. هذا فقط أبسط.

إذا كنت تحاول إنشاء فئة LinkedList كاملة ، فإن هذا الفيديو يتعمق في كيفية القيام بذلك.

عبور قائمة مرتبطة

إذا كنت تجري مقابلة برمجية ، وطُرح عليك سؤال قائمة مرتبطة ، فلن تحصل على جميع العقد.

كل ما ستحصل عليه هو عقدة الرأس.

من عقدة الرأس هذه ، يجب عليك الحصول على بقية القائمة.

أولاً ، دعنا نفهم كيفية الحصول على القيمة والعقدة التالية من عقدة في Python.

لنفترض أن لدينا عقدة تسمى ببساطة "عقدة".

الحصول على قيمة العقدة:

node.value

الحصول على العقدة التالية من العقدة:

node.nextNode

اجتياز

أول شيء نريد القيام به هو إنشاء متغير يسمى "CurrentNode" يتتبع العقدة التي نحن فيها. نريد تعيين هذا إلى عقدة الرأس في البداية.

currentNode = head

الآن كل ما علينا فعله هو التحقق مما إذا كانت العقدة الحالية خالية أم لا. إذا لم يكن الأمر كذلك ، فإننا نجعل "currentNode" الخاصة بنا مساوية لـ "nextNode" من "currentNode".

currentNode = node1while currentNode is not None: currentNode = currentNode.nextNode

لنفترض أن لدينا القائمة المرتبطة التالية: "3" ← "7" ← "10".

رأسنا وأول "عقدة تيار" هو "3".

عندما نفعل

currentNode = currentNode.nextNode

نحن نعيد تعيين "currentNode" إلى جارة العقدة الحالية ، والتي في هذه الحالة هي "7".

يستمر هذا حتى يتم توجيه CurrentNode إلى None ، وفي هذه الحالة تتوقف الحلقة.

And that is the basic way to traverse through a Linked List in Python.

Link to the code on Github.

Inserting elements

When you insert an element into a linked list, you insert it into the back unless specified otherwise.

Let’s use the following example:

“3”→”7"→”10"→Null

Let’s say we want to insert a “4”.

We would simply find the tail node, in this case “10”, and set its nextNode to our “4” node.

“3”→”7"→”10"→“4”→Null

node4 = linkedListNode("4")node3.nextNode = node4

Now let’s say we were in an interview, and all we had was the head node.

We simply traverse through the LinkedList to find the tail. Once we have the tail, we simply set its nextNode to our new node that we create.

def insertNode(head, valuetoInsert): currentNode = head while currentNode is not None: if currentNode.nextNode is None: currentNode.nextNode = linkedListNode(valuetoInsert) return head currentNode = currentNode.nextNode

Deleting elements

Deleting can get a bit tricky.

Let’s take the same example.

“3”→”7"→”10"→Null

If we wanted to delete the “7”, all we need to do is point the “3” to the “10” so that the “7” is never referenced.

“3”→”10"→Null

To do this, we would have to traverse the list while not only keeping track of the currentNode, but also keeping track of the previousNode.

We would also have to account for the head node being the node we want to delete.

In the code below, we simply delete the first instance of the value we want to delete.

Note that there are many ways to accomplish this, and the solution below might not be the cleanest code you’ll see in your life. However, in the heat of an interview, the interviewer probably won’t expect textbook perfect code.

def deleteNode(head, valueToDelete): currentNode = head previousNode = None while currentNode is not None: if currentNode.value == valueToDelete: if previousNode is None: newHead = currentNode.nextNode currentNode.nextNode = None return newHead # Deleted the head previousNode.nextNode = currentNode.nextNode return head previousNode = currentNode currentNode = currentNode.nextNode return head # Value to delete was not found.

In the code above, once we find the node we want to delete, we set the previous node’s “nextNode” to the deleted node’s “nextNode” to completely cut it out of the list.

Big O Time Complexity Analysis

**NOTE** These are the time complexities for the node structure above, which is most likely to appear on an interview. In practical cases, you can store attributes in a LinkedList class to lower these complexities.

‘n’ = the amount of elements inside the Linked List.

Inserting to the back of the Linked List— We go through all n elements to find the tail and insert our new node. O(n)

Inserting to the front of the Linked List — We simply create the new node and set its nextNode to the head. No need to traverse the list. O(1)

Traversing — We go through all n elements once. O(n)

Deleting — Worst case scenario, the node we’re deleting is the last node, causing us to traverse through the entire list. O(n)

يمكنك الآن معالجة أسئلة مقابلة القائمة المرتبطة!

لديك الآن المعرفة الأساسية التي تحتاجها لبدء معالجة أسئلة مقابلة القائمة المرتبطة!

يمكنهم أن يبدأوا بسهولة ، وأن يصبحوا صعبين بسرعة كبيرة.

في المقالة التالية ، سوف أتطرق إلى بضعة أسئلة وتقنيات شائعة يمكنك استخدامها لحلها.

إذا كنت طالبًا تتطلع إلى الحصول على تدريب أحلامك أو وظيفة بدوام كامل خلال العامين المقبلين ، فابدأ في التدريب الآن!

لقد بدأت مجتمعًا (www.theforge.ca) حيث نربط الطلاب بالموجهين وخبراء الصناعة الذين يساعدونهم في التنقل في طريقهم إلى الوظيفة التي يحلمون بها.

شكرا للقراءة وحظا سعيدا!