Pythoni intervjuu küsimuste juhend: kuidas lingitud loendit kodeerida

Sain alati lingitud loendite põhikontseptsioonist aru, kuid ei rakendanud seda kunagi.

Alles minu esimene Amazoni intervjuu aastaid tagasi mõistsin, et mul pole aimugi, kuidas lingitud loendite mõiste koodiks tõlgitakse.

Ja sellepärast kirjutangi selle juhendi!

Minu eesmärk on aidata teil tarkvarainseneriks saada.

Tahan kajastada paljusid lingitud loendite intervjuuküsimusi ja see artikkel on selle protsessi esimene samm. Nii et sukeldume sisse.

Mis on lingitud loend?

Lingitud loend on andmestruktuur, mis koosneb paljudest miniandmete struktuuridest, mida nimetatakse sõlmedeks. Noodid linkivad kokku, et moodustada loend.

Iga sõlm sisaldab 2 atribuuti

  1. Selle väärtus. See võib olla ükskõik milline: täisarvud, märgid, stringid, objektid ja nii edasi.
  2. Osuti järjestuse järgmisele sõlmele.

Mõned definitsioonid

„Peasõlm”: Peasõlm on lihtsalt lingitud loendi esimene sõlm. Nagu näeme ülaltoodud näitest, on esimene sõlm ja seega pea ka sõlm, mis sisaldab tähte '5'.

„Saba sõlm“: saba sõlm on järjestuse viimane sõlm. Kuna see on viimane sõlm, osutab see nullile, kuna järjestuses pole järgmist sõlme. Ülaltoodud näites oleks „3” sisaldav sõlm sabasõlm.

Üksikult lingitud vs kahekordselt lingitud

Lingitud loendite osas on kaks peamist tüüpi.

Need, mis on seotud „üksikult” ja need, mis on seotud „topelt”.

Üksikult ühendatud tähendab, et iga sõlm osutab ainult kuni 1 teisele sõlmele, selle ees olevale sõlmele. Seda on näidatud ülaltoodud näites.

Kahekordne linkimine tähendab, et iga sõlm võib osutada veel kahele sõlmele, selle ees olevale ja selle taga olevale sõlmele. Nagu näeme allpool toodud näitest, kuna peasõlmele (milleks on 5) ei ole ühtegi sõlme, osutab üks selle osutitest nullile.

Okei, ma saan kõigest sellest aru. Aga kuidas kood töötab?

Lingitud loendite kodeerimine võib olla nelja- või 400-realine probleem. See sõltub sellest, kuidas soovite sellele läheneda.

Lihtsamal tasandil, nagu me arutasime, on lingitud loend vaid ühendatud sõlmede hunnik.

Seega on selle struktuuri loomiseks kõik, mida me tegelikult vajame, on sõlmeobjekt.

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

Siin näeme, et oleme lihtsalt loonud klassi, millel on väärtus ja nextNode atribuut.

Sõlme loomiseks edastame lihtsalt väärtuse.

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

Siin oleme loonud 3 üksikut sõlme.

Järgmine samm on lihtsalt nende ühendamine.

node1.nextNode = node2 node2.nextNode = node3 

Esimene ülaltoodud rida paneb sõlme 1 osutama sõlme2:

„3“ → „7“

Teine ülaltoodud rida paneb sõlme2 osutama sõlme3:

„7“ → „10“

Kokkuvõttes on meile jäetud lingitud loend, mis näeb välja selline:

“3” → ”7” → ”10” → tühi

Märkus: „10” osutab nullile, kuna sõlmele3 ei olnud määratud nextNode ja vaikimisi nextNode on Null.

Nagu ma varem mainisin, on selleks palju erinevaid võimalusi. See on lihtsalt kõige lihtsam.

Kui proovite luua tervet LinkedListi klassi, siis on selles videos põhjalik ülevaade, kuidas seda teha.

Lingitud loendi läbimine

Kui teete programmeerimisintervjuud ja teilt küsitakse lingitud loendi küsimust, ei anta teile kõiki sõlme.

Kõik, mida saate, on peasõlm.

Sellest peasõlmest peate hankima ülejäänud loendi.

Kõigepealt mõistame, kuidas saada väärtus ja nextNode Pythoni sõlmest.

Oletame, et meil on sõlm, mille nimi on lihtsalt 'sõlm'.

Sõlme väärtuse hankimine:

node.value

Sõlme järgmiseNode hankimine:

node.nextNode

Läbimine

Esimene asi, mida me tahame teha, on luua muutuja nimega “currentNode”, mis jälgib sõlme, kus viibime. Me tahame selle esialgu omistada oma peasõlmele.

currentNode = head

Nüüd peame lihtsalt kontrollima, kas meie praegune sõlm on Null või mitte. Kui see pole nii, muudame meie 'currentNode' võrdseks 'currentNode' 'nextNode' -ga.

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

Oletame, et meil on järgmine lingitud loend: “3” → ”7” → ”10”.

Meie pea ja esimene 'currentNode' on „3”.

Kui me seda teeme

currentNode = currentNode.nextNode

Määrame 'currentNode' oma praeguse sõlme naabrile, mis antud juhul on „7”.

See jätkub seni, kuni praeguneNode osutatakse Puudub -le, sel juhul silmus peatub.

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)

Nüüd saate lahendada lingitud loendi intervjuu küsimused!

Teil on nüüd olemas põhiteadmised, mis on vajalikud Linked Listi intervjuu küsimustega tegelemiseks!

Nad võivad alustada lihtsalt ja kiiresti karmiks saada.

Järgmises artiklis käsitlen paari levinumat küsimust ja tehnikat, mida saate nende lahendamiseks kasutada.

Kui olete üliõpilane, kes soovib järgmise 2 aasta jooksul oma unistuste praktikale või täiskohaga tööle minna, alustage harjutamist kohe!

Ma olen loonud kogukonna (www.theforge.ca), kus me ühendame õpilasi mentorite ja valdkonna ekspertidega, mis aitavad neil oma unistuste juurde orienteeruda.

Täname lugemast ja palju edu!