Οδηγός ερωτήσεων συνέντευξης Google: Διαγραφή επαναλαμβανόμενων χαρακτήρων με το Python

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

Είχα την ευχαρίστηση να παίρνω συνέντευξη από πολλές κορυφαίες εταιρείες ως φοιτητής και να βρω δουλειά στη Silicon Valley ως Μηχανικός Λογισμικού.

Ο στόχος μου είναι να σας βοηθήσω να πάρετε εκείνη την ονειρική δουλειά που πάντα θέλατε!

Θα εξετάσουμε μια κλασική ερώτηση που θα μπορούσε να εμφανιστεί στην επόμενη συνέντευξη Google.

Προειδοποίηση: αν είστε βετεράνος κωδικοποίησης, ίσως γνωρίζετε ήδη πώς να λύσετε αυτήν την ερώτηση!

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

ΕΡΩΤΗΣΗ: Δίνεται μια συμβολοσειρά ως είσοδος, διαγράψτε τυχόν επαναλαμβανόμενο χαρακτήρα και επιστρέψτε τη νέα συμβολοσειρά.

Εάν προτιμάτε ένα βίντεο για να εξηγήσω την ερώτηση, έφτιαξα ένα εδώ.

Όπως μπορούμε να δούμε από το παραπάνω παράδειγμα, η έξοδος είναι "abc" επειδή διαγράφουμε το δεύτερο "a", "b" και "c".

Πρώτα πράγματα πρώτα, ας ρυθμίσουμε τη λειτουργία μας στο Python 2.7.

def deleteReoccurringCharacters(string):

Για να αντιμετωπίσουμε αυτήν την ερώτηση, θα χρησιμοποιήσουμε μια συγκεκριμένη δομή δεδομένων που ονομάζεται HashSet.

Μπορείτε να σκεφτείτε ότι ένα σύνολο είναι παρόμοιο με έναν πίνακα, με δύο κύριες εξαιρέσεις.

  1. Είναι εντελώς άτακτο
  2. Δεν μπορεί να περιέχει διπλότυπα

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

Ας ρυθμίσουμε και τα δύο αυτά πράγματα.

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = ''

Τώρα που έχουμε δημιουργήσει τις δομές δεδομένων που χρειαζόμαστε, ας μιλήσουμε για τον αλγόριθμό μας.

Λόγω του τρόπου λειτουργίας ενός σετ στη μνήμη, έχει μια πολυπλοκότητα χρόνου αναζήτησης 0 (1).

Αυτό σημαίνει ότι μπορούμε να το χρησιμοποιήσουμε για να ελέγξουμε αν έχουμε ήδη επισκεφτεί έναν χαρακτήρα ή όχι!

Ο αλγόριθμός μας

Περάστε όλους τους χαρακτήρες στην αρχική συμβολοσειρά και κάντε τα εξής:

Βήμα 1: Ελέγξτε αν ο χαρακτήρας είναι ήδη στο σετ μας

Ας δούμε πώς θα μοιάζει στον κώδικα ???

for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char

Δεν χρειάζεται να ανησυχούμε για μια «άλλη» υπόθεση, γιατί δεν κάνουμε τίποτα με τον ίδιο τον επαναλαμβανόμενο χαρακτήρα.

Τώρα το μόνο που μένει να κάνουμε είναι να επιστρέψουμε το outputString.

Δείτε πώς φαίνεται ο τελικός κώδικας:

def deleteReoccurringCharacters(string): seenCharacters = set() outputString = '' for char in string: if char not in seenCharacters: seenCharacters.add(char) outputString += char return outputString

Και εκεί το έχετε!

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

Ας κάνουμε μια μικρή ανάλυση.

Χρόνος πολυπλοκότητας

Η επανάληψη σε ολόκληρη τη συμβολοσειρά εισόδου έχει χρονική πολυπλοκότητα του O (n), καθώς υπάρχουν χαρακτήρες n στην ίδια τη συμβολοσειρά.

Για καθέναν από αυτούς τους χαρακτήρες, πρέπει να ελέγξουμε εάν έχουμε δει ή όχι το… Ωστόσο, δεδομένου ότι ένα HashSet έχει χρόνο αναζήτησης O (1), η πολυπλοκότητα του χρόνου μας δεν επηρεάζεται.

Αφήνοντας μας με την πολυπλοκότητα του τελικού χρόνου του O (n).

Διαστημική πολυπλοκότητα

Το χειρότερο σενάριο, έχουμε μια συμβολοσειρά με όλους τους μοναδικούς χαρακτήρες. Για παράδειγμα, "abcdef".

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

Ωστόσο, περιοριζόμαστε επίσης στο μέγεθος του αγγλικού αλφαβήτου.

Αυτή είναι μια καλή ευκαιρία να ρωτήσουμε τον ερευνητή μας τι είδους χαρακτήρες θεωρούνται μοναδικοί στη συμβολοσειρά (κεφαλαία / πεζά / αριθμοί / σύμβολα).

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

Αφήνοντας μας με τη χειρότερη περίπτωση περίπλοκη διαστημική πολυπλοκότητα του O (1).

Τώρα ξέρετε πώς να λύσετε μια ερώτηση συνέντευξης Google!

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

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

Έχω επίσης δημοσιεύσει τον τελικό κώδικα στο Github εδώ.

Ευχαριστούμε που παρακολουθήσατε και καλή τύχη!

.α # 33