de Anthony Sistilli

Ghid de întrebări pentru interviu Python: cum să codați o listă legată

Ghid de intrebari pentru interviu Python cum sa codati o
Fotografie de Mike Alonzo pe Unsplash

Am înțeles întotdeauna conceptul de bază al listelor legate, dar nu l-am pus niciodată în practică.

Abia după primul meu interviu Amazon, cu ani în urmă, mi-am dat seama că nu aveam idee despre cum s-a tradus în cod conceptul Listelor Linked.

Ghid de intrebari pentru interviu Python cum sa codati o
* Fața mea în timpul primului meu interviu Amazon *

Și de aceea scriu acest ghid!

Scopul meu este să ajut tu obține un loc de muncă ca inginer software.

Vreau să acopăr o mulțime de întrebări de interviu pentru listele legate, iar acest articol este primul pas în acest proces. Deci, să ne scufundăm.

Ce este o listă legată?

O Listă legată este o structură de date care constă din multe structuri de mini-date numite „Noduri”. Nodurile se leagă împreună pentru a forma o listă.

1611555487 947 Ghid de intrebari pentru interviu Python cum sa codati o
O întreagă listă legată, formată din 3 noduri legate împreună.

Fiecare nod conține 2 atribute

  1. Valoarea sa. Acesta poate fi orice: numere întregi, caractere, șiruri, obiecte și așa mai departe.
  2. Un indicator către următorul nod din secvență.

Unele definiții

„Nodul capului”: Nodul principal este pur și simplu primul nod din lista legată. După cum putem vedea din exemplul de mai sus, nodul care conține „5” este primul nod și, prin urmare, capul.

„Nodul cozii”: Nodul coadă este ultimul nod din secvență. Deoarece este ultimul nod, indică spre nul, deoarece nu există niciun nod următor în secvență. În exemplul de mai sus, nodul care conține „3” ar fi nodul coadă.

Singly Linked vs Doublly Linked

Când vine vorba de liste legate, există două tipuri principale.

Cei care sunt legați „individual” și cei care sunt „dublu” legați.

Singur legate înseamnă că fiecare nod indică doar cel mult un alt nod, nodul din fața acestuia. Acest lucru este prezentat în exemplul de mai sus.

1611555487 104 Ghid de intrebari pentru interviu Python cum sa codati o
Un exemplu de listă legată individual.

Dublu legat înseamnă că fiecare nod poate indica către alte 2 noduri, nodul din fața acestuia și nodul din spatele acestuia. După cum putem vedea din exemplul de mai jos, deoarece nu există niciun nod care să preceadă nodul de cap (care este 5), unul dintre indicatorii săi indică nul.

1611555487 27 Ghid de intrebari pentru interviu Python cum sa codati o
Un exemplu de listă dublă legată.

Bine, înțeleg toate acestea. Dar cum funcționează codul?

Codificarea listelor legate poate fi un Problemă cu 4 linii sau 400 de linii. Depinde de modul în care vrei să îl abordezi.

La cel mai simplu nivel, așa cum am discutat, o listă legată este doar un o grămadă de noduri conectate.

Astfel, tot ce ne trebuie cu adevărat pentru a crea această structură este un obiect nod.

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

Aici putem vedea că am creat pur și simplu o clasă care are un atribut valoare și nextNode.

Pentru a crea un nod, trecem pur și simplu o valoare.

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

Aici, am creat 3 noduri individuale.

Următorul pas este pur și simplu să le conectați împreună.

node1.nextNode = node2 node2.nextNode = node3 

Prima linie de mai sus face ca nodul 1 să se îndrepte către nodul 2:

„3” → „7”

A doua linie de mai sus face ca nodul2 să fie punctul 3:

„7” → ”10″

Împreună, rămânem cu o listă legată care arată astfel:

„3” → ”7″ → ”10″ → Nul

Notă: „10” indică valoarea nulă, deoarece nu a existat un nextNode atribuit nodului3, iar următorul nod implicit este Null.

Așa cum am menționat mai devreme, există o mulțime de moduri diferite de a face acest lucru. Acesta este doar cel mai simplu.

Dacă încercați să creați o întreagă clasă LinkedList, acest video aprofundează cum să faci asta.

Trecerea unei liste legate

Dacă faceți un interviu de programare și vi se pune o întrebare de pe lista legată, nu veți primi toate nodurile.

Tot ce veți obține este nodul principal.

1611555487 239 Ghid de intrebari pentru interviu Python cum sa codati o
Tot ce se transmite aici este nodul principal.

Din acel nod principal, trebuie să obțineți restul listei.

Mai întâi să înțelegem cum să obținem valoarea și nextNode dintr-un nod din Python.

Să presupunem că avem un nod numit pur și simplu „nod”.

Obținerea valorii nodului:

node.value

Obținerea următorului nod al nodului:

node.nextNode

Traversal

Primul lucru pe care vrem să-l facem este să creăm o variabilă numită „currentNode” care ține evidența nodului la care ne aflăm. La început vrem să atribuim acest lucru nodului nostru principal.

currentNode = head

Acum tot ce trebuie să facem este să verificăm pur și simplu dacă nodul nostru actual este sau nu Null. Dacă nu este, facem „currentNode” egal cu „nextNode” al „currentNode”.

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

Să presupunem că avem următoarea Listă legată: „3” → ”7„ → ”10”.

Capul și primul nostru „currentNode” este „3”.

Când o facem

currentNode = currentNode.nextNode

Redistribuim „currentNode” către vecinul nodului nostru actual, care în acest caz este „7”.

Acest lucru continuă până când currentNode este indicat spre None, caz în care bucla se oprește.

Și acesta este modul de bază de a parcurge o listă legată în Python.

Link către codul de pe Github.

Inserarea elementelor

Când introduceți un element într-o listă legată, îl introduceți în spate, cu excepția cazului în care se specifică altfel.

Să folosim următorul exemplu:

„3” → ”7″ → ”10″ → Nul

Să presupunem că vrem să inserăm un „4”.

Am găsi pur și simplu nodul coadă, în acest caz „10”, și ne-am seta următorul nod la nodul „4”.

„3” → ”7” → ”10” → “4” → Nul

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

Acum să spunem că am fost într-un interviu și tot ce am avut a fost nodul principal.

Pur și simplu traversăm prin LinkedList pentru a găsi coada. Odată ce avem coada, îi setăm pur și simplu următorul nod la noul nostru nod pe care îl creăm.

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

Ștergerea elementelor

Ștergerea poate deveni puțin dificilă.

Să luăm același exemplu.

„3” → ”7″ → ”10″ → Nul

Dacă am vrut să ștergem „7”, tot ce trebuie să facem este să îndreptăm „3” către „10” astfel încât „7” să nu fie niciodată menționat.

„3” → ”10” → Nul

Pentru a face acest lucru, ar trebui să parcurgem lista în timp ce nu numai să ținem evidența nodului curent, ci și să urmărim precedentNod.

De asemenea, ar trebui să ținem cont de faptul că nodul principal este nodul pe care dorim să îl ștergem.

În codul de mai jos, ștergem pur și simplu prima instanță a valorii pe care dorim să o ștergem.

Rețineți că există multe modalități de a realiza acest lucru, iar soluția de mai jos ar putea să nu fie cel mai curat cod pe care îl veți vedea în viața dvs. Cu toate acestea, în timpul unui interviu, intervievatorul probabil nu se va aștepta la codul perfect al manualului.

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.

În codul de mai sus, odată ce găsim nodul pe care dorim să-l ștergem, setăm „nextNode” al nodului anterior la „nextNode” al nodului șters pentru al tăia complet din listă.

Analiza complexității Big O Time

** NOTĂ ** Acestea sunt complexitățile de timp pentru structura nodului de mai sus, care este cel mai probabil să apară la un interviu. În cazuri practice, puteți stoca atribute într-o clasă LinkedList pentru a reduce aceste complexități.

‘n’ = cantitatea de elemente din lista conectată.

Inserarea în partea din spate a listei conectate— Trecem prin toate n elementele pentru a găsi coada și a introduce noul nostru nod. Pe)

Inserarea în partea din față a Listei conectate – Pur și simplu creăm noul nod și îi setăm următorul nod la cap. Nu este nevoie să traversezi lista. O (1)

Traversare – Trecem odată prin toate n elementele. Pe)

Ștergere – Cel mai rău scenariu, nodul pe care îl ștergem este ultimul nod, determinându-ne să traversăm întreaga listă. Pe)

Acum puteți aborda întrebările de interviu ale Listei Linked!

Acum aveți cunoștințele fundamentale de care aveți nevoie pentru a începe să abordați întrebările de interviu ale Listei Linked!

Ele pot începe ușor și devin foarte rapide.

În articolul următor, voi analiza câteva întrebări și tehnici obișnuite pe care le puteți folosi pentru a le rezolva.

Dacă sunteți un student care dorește să obțină un stagiu de vis sau un loc de muncă cu normă întreagă în următorii 2 ani, începeți să practicați acum!

Am început o comunitate (www.theforge.ca) în care conectăm studenții cu mentori și experți din industrie care îi ajută să se orienteze spre locul de muncă de vis.

Mulțumesc pentru lectură și mult succes!