Οι κορυφαίες δομές δεδομένων που πρέπει να γνωρίζετε για την επόμενη συνέντευξη κωδικοποίησης

Ο Niklaus Wirth, Ελβετός επιστήμονας υπολογιστών, έγραψε ένα βιβλίο το 1976 με τίτλο Αλγόριθμοι + Δομές Δεδομένων = Προγράμματα.

40+ χρόνια αργότερα, αυτή η εξίσωση ισχύει ακόμα. Γι 'αυτό οι υποψήφιοι μηχανικής λογισμικού πρέπει να αποδείξουν την κατανόηση των δομών δεδομένων μαζί με τις εφαρμογές τους.

Σχεδόν όλα τα προβλήματα απαιτούν από τον υποψήφιο να επιδείξει μια βαθιά κατανόηση των δομών δεδομένων. Δεν έχει σημασία αν μόλις αποφοιτήσατε (από πανεπιστήμιο ή κωδικοποίηση bootcamp) ή έχετε δεκαετίες εμπειρίας.

Μερικές φορές οι ερωτήσεις συνέντευξης αναφέρουν ρητά μια δομή δεδομένων, για παράδειγμα, "δεδομένου ενός δυαδικού δέντρου". Άλλες φορές είναι σιωπηρή, όπως «θέλουμε να παρακολουθούμε τον αριθμό των βιβλίων που σχετίζονται με κάθε συγγραφέα».

Η εκμάθηση δομών δεδομένων είναι απαραίτητη ακόμα κι αν προσπαθείτε να βελτιώσετε την τρέχουσα εργασία σας. Ας ξεκινήσουμε με την κατανόηση των βασικών.

Τι είναι μια δομή δεδομένων;

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

Γιατί χρειαζόμαστε δομές δεδομένων;

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

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

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

Δομές δεδομένων που χρησιμοποιούνται συνήθως

Ας απαριθμήσουμε πρώτα τις πιο συχνά χρησιμοποιούμενες δομές δεδομένων και μετά θα τις καλύψουμε μία προς μία:

  1. Πίνακες
  2. Στοίβες
  3. Ουρές
  4. Συνδεδεμένες λίστες
  5. Δέντρα
  6. Γραφικές παραστάσεις
  7. Προσπαθεί (είναι ουσιαστικά δέντρα, αλλά είναι ακόμα καλό να τα καλέσετε ξεχωριστά).
  8. Πίνακες κατακερματισμού

Πίνακες

Ένας πίνακας είναι η απλούστερη και ευρύτερα χρησιμοποιούμενη δομή δεδομένων. Άλλες δομές δεδομένων όπως στοίβες και ουρές προέρχονται από πίνακες.

Ακολουθεί μια εικόνα ενός απλού πίνακα μεγέθους 4, που περιέχει στοιχεία (1, 2, 3 και 4).

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

Τα ακόλουθα είναι τα δύο είδη συστοιχιών:

  • Μονοδιάστατες συστοιχίες (όπως φαίνεται παραπάνω)
  • Πολυδιάστατες συστοιχίες (συστοιχίες εντός συστοιχιών)

Βασικές λειτουργίες σε συστοιχίες

  • Εισαγωγή - Εισάγει ένα στοιχείο σε ένα δεδομένο ευρετήριο
  • Λήψη - Επιστρέφει το στοιχείο σε ένα δεδομένο ευρετήριο
  • Διαγραφή - Διαγράφει ένα στοιχείο σε ένα δεδομένο ευρετήριο
  • Μέγεθος - Λαμβάνει τον συνολικό αριθμό στοιχείων σε έναν πίνακα

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Array

  • Βρείτε το δεύτερο ελάχιστο στοιχείο ενός πίνακα
  • Πρώτοι μη επαναλαμβανόμενοι ακέραιοι αριθμοί
  • Συγχώνευση δύο ταξινομημένων πινάκων
  • Αναδιάταξη θετικών και αρνητικών τιμών σε έναν πίνακα

Στοίβες

Είμαστε όλοι εξοικειωμένοι με τη διάσημη επιλογή Αναίρεσης , η οποία υπάρχει σχεδόν σε κάθε εφαρμογή. Αναρωτηθήκατε ποτέ πώς λειτουργεί; Η ιδέα: αποθηκεύετε τις προηγούμενες καταστάσεις της εργασίας σας (οι οποίες περιορίζονται σε έναν συγκεκριμένο αριθμό) στη μνήμη με μια σειρά που η τελευταία εμφανίζεται πρώτη. Αυτό δεν μπορεί να γίνει μόνο χρησιμοποιώντας πίνακες. Εκεί έρχεται το Stack βολικό.

Ένα πραγματικό παράδειγμα του Stack θα μπορούσε να είναι ένας σωρός από βιβλία τοποθετημένα σε κάθετη σειρά. Για να πάρετε το βιβλίο που βρίσκεται κάπου στη μέση, θα πρέπει να αφαιρέσετε όλα τα βιβλία που βρίσκονται πάνω του. Έτσι λειτουργεί η μέθοδος LIFO (Last In First Out).

Ακολουθεί μια εικόνα στοίβας που περιέχει τρία στοιχεία δεδομένων (1, 2 και 3), όπου το 3 βρίσκεται στην κορυφή και θα αφαιρεθεί πρώτα:

Βασικές λειτουργίες στοίβας:

  • Push - Εισάγει ένα στοιχείο στην κορυφή
  • Pop - Επιστρέφει το κορυφαίο στοιχείο μετά την αφαίρεση από τη στοίβα
  • isEmpty - Επιστρέφει true εάν η στοίβα είναι άδεια
  • Κορυφή - Επιστρέφει το κορυφαίο στοιχείο χωρίς αφαίρεση από τη στοίβα

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Stack

  • Αξιολογήστε την έκφραση μετά την επιδιόρθωση χρησιμοποιώντας μια στοίβα
  • Ταξινόμηση τιμών σε μια στοίβα
  • Ελέγξτε ισορροπημένες παρενθέσεις σε μια έκφραση

Ουρές

Παρόμοια με το Stack, το Queue είναι μια άλλη γραμμική δομή δεδομένων που αποθηκεύει το στοιχείο με διαδοχικό τρόπο. Η μόνη σημαντική διαφορά μεταξύ Stack και Queue είναι ότι αντί να χρησιμοποιεί τη μέθοδο LIFO, το Queue εφαρμόζει το FIFOμέθοδος, η οποία είναι σύντομη για την First in First Out.

Ένα τέλειο πραγματικό παράδειγμα της ουράς: μια σειρά ανθρώπων που περιμένουν σε ένα θάλαμο εισιτηρίων. Εάν έρθει ένα νέο άτομο, θα συμμετάσχουν στη γραμμή από το τέλος, όχι από την αρχή - και το άτομο που στέκεται στο μπροστινό μέρος θα είναι το πρώτο που θα πάρει το εισιτήριο και επομένως θα αποχωρήσει από τη γραμμή.

Ακολουθεί μια εικόνα της ουράς που περιέχει τέσσερα στοιχεία δεδομένων (1, 2, 3 και 4), όπου το 1 βρίσκεται στην κορυφή και θα αφαιρεθεί πρώτα:

Βασικές λειτουργίες της ουράς

  • Enqueue () - Εισάγει ένα στοιχείο στο τέλος της ουράς
  • Dequeue () - Καταργεί ένα στοιχείο από την αρχή της ουράς
  • isEmpty () - Επιστρέφει true εάν η ουρά είναι κενή
  • Κορυφή () - Επιστρέφει το πρώτο στοιχείο της ουράς

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Queue

  • Εφαρμόστε στοίβα χρησιμοποιώντας μια ουρά
  • Αντιστρέψτε τα πρώτα στοιχεία k μιας ουράς
  • Δημιουργήστε δυαδικούς αριθμούς από 1 έως n χρησιμοποιώντας μια ουρά

Συνδεδεμένη λίστα

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

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

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

Ακολουθεί μια οπτική αναπαράσταση της εσωτερικής δομής μιας συνδεδεμένης λίστας:

Ακολουθούν οι τύποι των συνδεδεμένων λιστών:

  • Singly Linked List (Μονοκατευθυντική)
  • Διπλή συνδεδεμένη λίστα (αμφίδρομη)

Βασικές λειτουργίες συνδεδεμένης λίστας:

  • InsertAtEnd - Εισάγει ένα δεδομένο στοιχείο στο τέλος της συνδεδεμένης λίστας
  • InsertAtHead - Εισάγει ένα δεδομένο στοιχείο στην αρχή / επικεφαλίδα της συνδεδεμένης λίστας
  • Διαγραφή - Διαγράφει ένα δεδομένο στοιχείο από τη συνδεδεμένη λίστα
  • DeleteAtHead - Διαγράφει το πρώτο στοιχείο της συνδεδεμένης λίστας
  • Αναζήτηση - Επιστρέφει το δεδομένο στοιχείο από μια συνδεδεμένη λίστα
  • isEmpty - Επιστρέφει true εάν η συνδεδεμένη λίστα είναι κενή

Συνήθεις ερωτήσεις συνέντευξης Συνδεδεμένης λίστας

  • Αντιστρέψτε μια συνδεδεμένη λίστα
  • Εντοπίστε βρόχο σε μια συνδεδεμένη λίστα
  • Επιστροφή Nth κόμβος από το τέλος σε μια συνδεδεμένη λίστα
  • Κατάργηση διπλότυπων από μια συνδεδεμένη λίστα

Γραφικές παραστάσεις

Ένα γράφημα είναι ένα σύνολο κόμβων που συνδέονται μεταξύ τους με τη μορφή δικτύου. Οι κόμβοι καλούνται επίσης κορυφές. Ένα ζεύγος (x, y) ονομάζεται άκρο , το οποίο δείχνει ότι η κορυφή x συνδέεται με την κορυφή y . Ένα άκρο μπορεί να περιέχει βάρος / κόστος, δείχνοντας το κόστος που απαιτείται για να διασχίσουμε από την κορυφή x έως το y .

Τύποι γραφημάτων:

  • Μη κατευθυνόμενο γράφημα
  • Κατευθυνόμενο γράφημα

Σε μια γλώσσα προγραμματισμού, τα γραφήματα μπορούν να αναπαρασταθούν χρησιμοποιώντας δύο μορφές:

  • Πίνακας προσαρμογής
  • Λίστα ικανοτήτων

Συνηθισμένοι αλγόριθμοι διέλευσης γραφημάτων:

  • Πρώτη αναζήτηση
  • Πρώτη αναζήτηση βάθους

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Graph

  • Εφαρμογή πρώτης αναζήτησης εύρους και βάθους
  • Ελέγξτε εάν ένα γράφημα είναι δέντρο ή όχι
  • Μετρήστε τον αριθμό των άκρων σε ένα γράφημα
  • Βρείτε τη συντομότερη διαδρομή μεταξύ δύο κορυφών

Δέντρα

Ένα δέντρο είναι μια ιεραρχική δομή δεδομένων που αποτελείται από κορυφές (κόμβους) και άκρα που τις συνδέουν. Τα δέντρα είναι παρόμοια με τα γραφήματα, αλλά το βασικό σημείο που διαφοροποιεί ένα δέντρο από το γράφημα είναι ότι ένας κύκλος δεν μπορεί να υπάρχει σε ένα δέντρο.

Τα δέντρα χρησιμοποιούνται εκτενώς στην Τεχνητή Νοημοσύνη και σε πολύπλοκους αλγόριθμους για την παροχή ενός αποτελεσματικού μηχανισμού αποθήκευσης για την επίλυση προβλημάτων.

Ακολουθεί μια εικόνα ενός απλού δέντρου και βασικές ορολογίες που χρησιμοποιούνται στη δομή δεδομένων δέντρων:

Τα ακόλουθα είναι τα είδη των δέντρων:

  • N-ary Tree
  • Ισορροπημένο δέντρο
  • Δυαδικό δέντρο
  • Δυαδικό δέντρο αναζήτησης
  • Δέντρο AVL
  • Κόκκινο μαύρο δέντρο
  • 2–3 Δέντρο

Από τα παραπάνω, το Binary Tree και το Binary Search Tree είναι τα πιο συχνά χρησιμοποιούμενα δέντρα.

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Tree

  • Βρείτε το ύψος ενός δυαδικού δέντρου
  • Βρείτε τη μέγιστη τιμή kth σε ένα δέντρο δυαδικής αναζήτησης
  • Βρείτε κόμβους σε απόσταση "k" από τη ρίζα
  • Βρείτε προγόνους ενός δεδομένου κόμβου σε ένα δυαδικό δέντρο

Τρι

Το Trie, το οποίο είναι επίσης γνωστό ως "Prefix Trees", είναι μια δομή δεδομένων που μοιάζει με δέντρο που αποδεικνύεται αρκετά αποτελεσματική για την επίλυση προβλημάτων που σχετίζονται με χορδές. Παρέχει γρήγορη ανάκτηση και χρησιμοποιείται ως επί το πλείστον για την αναζήτηση λέξεων σε ένα λεξικό, παρέχοντας αυτόματες προτάσεις σε μια μηχανή αναζήτησης, ακόμη και για δρομολόγηση IP.

Ακολουθεί μια απεικόνιση του τρόπου αποθήκευσης τριών λέξεων «κορυφή», «έτσι» και «τους» στο Trie:

Οι λέξεις αποθηκεύονται με τρόπο από πάνω προς τα κάτω, όπου οι πράσινοι κόμβοι "p", "s" και "r" δείχνουν το τέλος των "top", "έτσι" και "τους" αντίστοιχα.

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη της Trie:

  • Μετρήστε τον συνολικό αριθμό λέξεων στο Trie
  • Εκτυπώστε όλες τις λέξεις που είναι αποθηκευμένες στο Trie
  • Ταξινόμηση στοιχείων ενός πίνακα χρησιμοποιώντας το Trie
  • Σχηματίστε λέξεις από ένα λεξικό χρησιμοποιώντας το Trie
  • Δημιουργήστε ένα λεξικό T9

Πίνακας κατακερματισμού

Το κατακερματισμό είναι μια διαδικασία που χρησιμοποιείται για τον μοναδικό προσδιορισμό αντικειμένων και την αποθήκευση κάθε αντικειμένου σε κάποιο προκαθορισμένο μοναδικό ευρετήριο που ονομάζεται «κλειδί». Έτσι, το αντικείμενο αποθηκεύεται με τη μορφή ζεύγους "κλειδιού-τιμής" και η συλλογή τέτοιων αντικειμένων ονομάζεται "λεξικό". Μπορείτε να αναζητήσετε κάθε αντικείμενο χρησιμοποιώντας αυτό το κλειδί. Υπάρχουν διαφορετικές δομές δεδομένων που βασίζονται στο κατακερματισμό, αλλά η πιο συχνά χρησιμοποιούμενη δομή δεδομένων είναι ο πίνακας κατακερματισμού .

Οι πίνακες Hash γενικά εφαρμόζονται χρησιμοποιώντας πίνακες.

Η απόδοση της δομής δεδομένων κατακερματισμού εξαρτάται από αυτούς τους τρεις παράγοντες:

  • Λειτουργία κατακερματισμού
  • Μέγεθος του πίνακα Hash
  • Μέθοδος χειρισμού σύγκρουσης

Ακολουθεί μια εικόνα για το πώς χαρτογραφείται το hash σε έναν πίνακα. Το ευρετήριο αυτού του πίνακα υπολογίζεται μέσω μιας συνάρτησης Hash.

Συνήθεις ερωτήσεις σχετικά με τη συνέντευξη Hashing

  • Βρείτε συμμετρικά ζεύγη σε έναν πίνακα
  • Εντοπίστε την πλήρη διαδρομή ενός ταξιδιού
  • Βρείτε αν ένας πίνακας είναι ένα υποσύνολο άλλου πίνακα
  • Ελέγξτε εάν οι δεδομένες συστοιχίες είναι αποσυνδεδεμένες

Τα παραπάνω είναι οι κορυφαίες οκτώ δομές δεδομένων που πρέπει σίγουρα να γνωρίζετε πριν μπείτε σε μια συνέντευξη κωδικοποίησης.

Εάν ψάχνετε πόρους σε δομές δεδομένων για κωδικοποίηση συνεντεύξεων, δείτε τα διαδραστικά μαθήματα που βασίζονται σε προκλήσεις: Δομές δεδομένων για συνεντεύξεις κωδικοποίησης (Python, Java ή JavaScript).

Για πιο προχωρημένες ερωτήσεις, ανατρέξτε στο Coderust 3.0: Ταχύτερη προετοιμασία συνέντευξης κωδικοποίησης με διαδραστικές προκλήσεις και οπτικοποιήσεις.

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

Καλή τύχη και καλή μάθηση! :)