Ερωτήσεις συνέντευξης DSA

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

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

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

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

• Two pointers. Ταξινομημένη είσοδος, αθροίσματα ζευγών, in-place διαμερισμός, έλεγχοι παλίνδρομου.
• Sliding window. Ο μεγαλύτερος ή μικρότερος συνεχόμενος υποπίνακας υπό έναν περιορισμό.
• Μέτρηση με hash map. Αναγράμματα, διπλότυπα, συγκρίσεις συχνότητας, πρώτο μοναδικό στοιχείο.
• Δυαδική αναζήτηση. Ταξινομημένοι πίνακες, και αναζήτηση στον χώρο απαντήσεων όταν ο πίνακας δεν είναι ταξινομημένος.
• Αναζήτηση κατά πλάτος και κατά βάθος. Δέντρα, πλέγματα, συνδεδεμένα στοιχεία, συντομότερο μη σταθμισμένο μονοπάτι.
• Σωρός και ουρά προτεραιότητας. Προβλήματα top-k, συγχώνευση ταξινομημένων ροών, τρέχουσες διάμεσοι.
• Διαστήματα. Συγχώνευση, εισαγωγή και εντοπισμός επικάλυψης μετά από ταξινόμηση κατά αρχή.
• Δυναμικός προγραμματισμός. Επικαλυπτόμενα υποπροβλήματα: ανέβασμα σκάλας, ρέστα νομισμάτων, απόσταση επεξεργασίας, υπακολουθίες.
• Backtracking. Μεταθέσεις, συνδυασμοί, υποσύνολα, γρίφοι με περιορισμούς.
• Αλγόριθμοι γράφων. Τοπολογική ταξινόμηση, union find, συντομότερο σταθμισμένο μονοπάτι.

Αντιπροσωπευτικές εκφωνήσεις, διατυπωμένες όπως τις διατυπώνουν οι συνεντευκτές:

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

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

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

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

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