Οδηγός ερωτήσεων συνέντευξης Python: πώς να κωδικοποιήσετε μια συνδεδεμένη λίστα

Πάντα κατάλαβα τη βασική ιδέα των Συνδεδεμένων Λιστών, αλλά δεν την έβαλα ποτέ στην πράξη.

Μόνο πριν από την πρώτη μου συνέντευξη στο Amazon πριν από χρόνια, όταν συνειδητοποίησα ότι δεν είχα ιδέα πώς μεταφράστηκε σε κώδικα η έννοια των Συνδεδεμένων Λιστών.

Γι 'αυτό γράφω αυτόν τον οδηγό!

Στόχος μου είναι να σε βοηθήσω να βρεις δουλειά ως Μηχανικός Λογισμικού.

Θέλω να καλύψω πολλές ερωτήσεις συνέντευξης Συνδεδεμένων Λιστών και αυτό το άρθρο είναι το πρώτο βήμα σε αυτήν τη διαδικασία. Ας βυθίσουμε λοιπόν.

Τι είναι μια συνδεδεμένη λίστα;

Μια συνδεδεμένη λίστα είναι μια δομή δεδομένων που αποτελείται από πολλές δομές μίνι δεδομένων που ονομάζονται «Κόμβοι». Οι κόμβοι συνδέονται μεταξύ τους για να σχηματίσουν μια λίστα.

Κάθε κόμβος περιέχει 2 χαρακτηριστικά

  1. Η αξία του. Αυτό μπορεί να είναι οτιδήποτε: ακέραιοι, χαρακτήρες, χορδές, αντικείμενα και ούτω καθεξής.
  2. Ένας δείκτης στον επόμενο κόμβο της ακολουθίας.

Μερικοί ορισμοί

Ο «κόμβος κεφαλής»: Ο κόμβος κεφαλής είναι απλά ο πρώτος κόμβος στη συνδεδεμένη λίστα. Όπως μπορούμε να δούμε από το παραπάνω παράδειγμα, ο κόμβος που περιέχει το «5» είναι ο πρώτος κόμβος και επομένως η κεφαλή.

Ο «Κόμβος Ουράς»: Ο κόμβος ουράς είναι ο τελευταίος κόμβος της ακολουθίας. Δεδομένου ότι είναι ο τελευταίος κόμβος, δείχνει το null, επειδή δεν υπάρχει επόμενος κόμβος στην ακολουθία. Στο παραπάνω παράδειγμα, ο κόμβος που περιέχει «3» θα ήταν ο κόμβος ουράς.

Singly Linked vs Doubly Linked

Όσον αφορά τις συνδεδεμένες λίστες, υπάρχουν δύο βασικά είδη.

Εκείνα που συνδέονται «μεμονωμένα» και εκείνα που είναι «διπλά» συνδεδεμένα.

Μεμονωμένα συνδεδεμένα σημαίνει ότι κάθε κόμβος δείχνει μόνο το πολύ έναν άλλο κόμβο, ο κόμβος μπροστά του. Αυτό φαίνεται στο παραπάνω παράδειγμα.

Διπλά συνδεδεμένος σημαίνει ότι κάθε κόμβος μπορεί να δείχνει σε 2 άλλους κόμβους, τον κόμβο μπροστά του και τον κόμβο πίσω από αυτόν. Όπως μπορούμε να δούμε από το παρακάτω παράδειγμα, δεδομένου ότι δεν υπάρχει κόμβος που να προηγείται του κόμβου κεφαλής (που είναι 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" → Null

Σημείωση: Το "10" δείχνει το null, επειδή δεν είχε εκχωρηθεί nextNode στον κόμβο 3 και το προεπιλεγμένο nextNode είναι Null

Όπως ανέφερα νωρίτερα, υπάρχουν πολλοί διαφορετικοί τρόποι για να γίνει αυτό. Αυτό είναι απλώς το πιο απλό.

Εάν προσπαθείτε να δημιουργήσετε μια ολόκληρη τάξη LinkedList, αυτό το βίντεο περιγράφει σε βάθος πώς να το κάνετε αυτό.

Διασχίζοντας μια συνδεδεμένη λίστα

Εάν κάνετε συνέντευξη προγραμματισμού και σας ζητηθεί μια ερώτηση συνδεδεμένης λίστας, δεν θα σας δοθούν όλοι οι κόμβοι.

Το μόνο που θα πάρετε είναι ο κόμβος κεφαλής.

Από αυτόν τον κόμβο κεφαλής, πρέπει να πάρετε την υπόλοιπη λίστα.

First let’s understand how to get the value and nextNode from a node in Python.

Let’s say we have a node simply named ‘node’.

Getting the value of the node:

node.value

Getting the nextNode of the node:

node.nextNode

Traversal

This first thing we want to do is create a variable called “currentNode” that keeps track of the node we’re at. We want to assign this to our head node at first.

currentNode = head

Now all we have to do is simply check whether or not our current node is Null. If it’s not, we make our ‘currentNode’ equal to the ‘nextNode’ of the ‘currentNode’.

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

Let’s say we have the following Linked List: “3”→”7"→”10".

Our head and first ‘currentNode’ is “3”.

When we do

currentNode = currentNode.nextNode

We are reassigning ‘currentNode’ to our current node’s neighbor, which in this case is “7”.

This continues until the currentNode is pointed to None, in which case the loop stops.

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)

Τώρα μπορείτε να αντιμετωπίσετε ερωτήσεις συνέντευξης συνδεδεμένης λίστας!

Τώρα έχετε τις βασικές γνώσεις που χρειάζεστε για να αρχίσετε να αντιμετωπίζετε ερωτήσεις συνέντευξης Συνδεδεμένης λίστας!

Μπορούν να ξεκινήσουν εύκολα και να γίνουν σκληροί πολύ γρήγορα.

Στο επόμενο άρθρο, θα εξετάσω μερικές κοινές ερωτήσεις και τεχνικές που μπορείτε να χρησιμοποιήσετε για να τις λύσετε.

Εάν είστε φοιτητής που θέλετε να προσκομίσετε την πρακτική σας άσκηση ή την πλήρη απασχόληση μέσα στα επόμενα 2 χρόνια, ξεκινήστε να ασκείστε τώρα!

Έχω ξεκινήσει μια κοινότητα (www.theforge.ca) όπου συνδέουμε τους μαθητές με μέντορες και εμπειρογνώμονες της βιομηχανίας που τους βοηθούν να περιηγηθούν στη δουλειά των ονείρων τους.

Ευχαριστώ για την ανάγνωση και καλή τύχη!