מדריך לשאלות ראיון לפייתון: כיצד מקודדים רשימה מקושרת

תמיד הבנתי את מושג הליבה של רשימות מקושרות, אבל מעולם לא הפעלתי את זה.

רק בראיון הראשון שלי עם אמזון לפני שנים הבנתי שאין לי מושג כיצד הרעיון של רשימות מקושרות מתורגם לקוד.

ובגלל זה אני כותב את המדריך הזה!

המטרה שלי היא לעזור לך לקבל עבודה כמהנדס תוכנה.

אני רוצה לכסות הרבה שאלות על ראיונות מקושרים, ומאמר זה הוא הצעד הראשון בתהליך זה. אז בואו נצלול פנימה.

מהי רשימה מקושרת?

רשימה מקושרת היא מבנה נתונים המורכב ממבני מיני נתונים רבים המכונים 'צמתים'. הצמתים מקשרים יחד כדי ליצור רשימה.

כל צומת מכיל 2 תכונות

זה ערך. זה יכול להיות כל דבר: מספרים שלמים, תווים, מחרוזות, אובייקטים וכו '.
מצביע לצומת הבא ברצף.

כמה הגדרות

'ראש הצומת': צומת הראש הוא פשוט הצומת הראשון ברשימה המקושרת. כפי שניתן לראות מהדוגמה לעיל, הצומת המכיל '5' הוא הצומת הראשון, ולכן הראש.

'צומת הזנב': צומת הזנב היא הצומת האחרון ברצף. מכיוון שזה הצומת האחרון, הוא מצביע על null, מכיוון שאין בצומת הבא ברצף. בדוגמה לעיל, הצומת המכיל '3' יהיה צומת הזנב.

מקושר בודד מול מקושר כפליים

כשמדובר ברשימות מקושרות, ישנם שני סוגים עיקריים.

אלה המקושרים 'יחידה', ואלה שקושרים 'כפליים'.

מקושר יחיד פירושו שכל צומת מצביע רק לכל היותר על צומת אחר אחד, הצומת שמולו. זה מוצג בדוגמה שלמעלה.

מקושר כפול פירושו שכל צומת יכול להצביע על 2 צמתים אחרים, הצומת שמולו והצומת שמאחוריו. כפי שניתן לראות מהדוגמה שלהלן, מכיוון שאין צומת שקודם לצומת הראש (שהוא 5), אחת מהמצביעים שלו מצביעה על null.

אוקיי, אני מבין את כל זה. אבל איך הקוד עובד?

קידוד רשימות מקושרות יכול להיות בעיה של 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

השורה הראשונה למעלה מעלה את הצומת node1 ל node2:

"3" → "7"

השורה השנייה שלמעלה מציינת את node2 לכוון node3:

"7" → "10"

בסך הכל נשארה לנו רשימה מקושרת שנראית כך:

"3" → "7" → "10" → אפס

הערה: "10" מצביע על null, מכיוון שלא הוקצה NextNode ל- node3, וה- NextNode כברירת מחדל הוא Null.

כמו שציינתי קודם, יש הרבה דרכים שונות לעשות זאת. זה פשוט הכי פשוט.

אם אתה מנסה לעשות שיעור שלם של LinkedList, הסרטון הזה מפרט לעומק כיצד לעשות זאת.

חוצה רשימה מקושרת

אם אתה עורך ראיון תכנות ושואלים אותך שאלה של רשימה מקושרת, לא תקבל את כל הצמתים.

כל מה שתקבל הוא צומת הראש.

מאותו צומת ראש, עליכם להשיג את שאר הרשימה.

ראשית בואו להבין איך להשיג את הערך ואת nextNode מצומת בפייתון.

נניח שיש לנו צומת שפשוט נקראת 'צומת'.

קבלת הערך של הצומת:

node.value

קבלת הצומת הבא של הצומת:

node.nextNode

מעבר

הדבר הראשון שאנו רוצים לעשות הוא ליצור משתנה בשם "currentNode" העוקב אחר הצומת בו אנו נמצאים. אנו רוצים להקצות זאת בהתחלה לצומת הראש שלנו.

currentNode = head

כעת כל שעלינו לעשות הוא פשוט לבדוק האם הצומת הנוכחי שלנו הוא Null. אם זה לא, אנו הופכים את 'currentNode' שלנו לשווה ל- 'nextNode' של 'currentNode'.

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

נניח שיש לנו את הרשימה המקושרת הבאה: "3" → "7" → "10".

הראש וה- 'currentNode' הראשון שלנו הוא "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)

You can now tackle Linked List interview questions!

You now have the fundamental knowledge you need to start tackling Linked List interview questions!

They can start off easy, and get tough really quick.

In the next article, I’m going to go over a couple of common questions and techniques you can use to solve them.

If you’re a student looking to land your dream internship or full-time job within the next 2 years, start practicing now!

I’ve started a community (www.theforge.ca) where we connect students with mentors and industry experts that help them navigate their way to their dream job.

Thanks for reading, and good luck!