Guide des questions d'entrevue Google: supprimer les caractères récurrents avec Python

De nos jours, les interviews Google font fureur. Mais parfois, les entretiens peuvent tirer le meilleur parti de nous. Surtout si c'est pour un poste que nous voulons vraiment .

J'ai eu le plaisir d'interviewer plusieurs grandes entreprises en tant qu'étudiant et de décrocher un emploi dans la Silicon Valley en tant qu'ingénieur logiciel.

Mon objectif est de vous aider à obtenir l'emploi de vos rêves que vous avez toujours voulu!

Nous allons passer en revue une question classique qui pourrait apparaître lors de votre prochaine interview Google.

Attention: si vous êtes un vétéran du codage, vous savez probablement déjà comment résoudre cette question!

Si vous essayez d'obtenir un stage ou un emploi à temps plein l'année prochaine, vous bénéficierez certainement de cet article. ???

QUESTION: Étant donné une chaîne comme entrée, supprimez tout caractère récurrent et renvoyez la nouvelle chaîne.

Si vous préférez une vidéo pour expliquer la question, j'en ai fait une ici.

Comme nous pouvons le voir dans l'exemple ci-dessus, la sortie est «abc» car nous supprimons le second «a», «b» et «c».

Tout d'abord, configurons notre fonction dans Python 2.7.

def deleteReoccurringCharacters(string):

Pour répondre à cette question, nous allons utiliser une structure de données spécifique appelée HashSet.

Vous pouvez considérer un ensemble comme étant similaire à un tableau, à deux exceptions près.

  1. C'est complètement désordonné
  2. Il ne peut pas contenir de doublons

Comme il n'est pas ordonné, nous aurons également besoin d'une chaîne vide pour stocker les caractères que nous avons ajoutés à l'ensemble dans l'ordre. Ce sera la chaîne que nous renvoyons.

Mettons ces deux choses en place.

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

Maintenant que nous avons mis en place les structures de données dont nous avons besoin, parlons de notre algorithme.

En raison de la façon dont un ensemble fonctionne en mémoire, il a une complexité de temps de recherche de 0 (1).

Cela signifie que nous pouvons l'utiliser pour vérifier si nous avons déjà visité un personnage!

Notre algorithme

Parcourez tous les caractères de la chaîne initiale et procédez comme suit:

Étape 1: Vérifiez si le caractère est déjà dans notre ensemble Étape 2: S'il ne fait pas partie de l'ensemble, ajoutez-le à l'ensemble et ajoutez-le à la chaîne

Voyons à quoi cela ressemblerait dans le code ???

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

Nous n'avons pas à nous soucier d'un cas «autre», car nous ne faisons rien avec le caractère récurrent lui-même.

Il ne reste plus qu'à renvoyer la outputString.

Voici à quoi ressemble le code fini:

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

Et voila!

Maintenant, s'il s'agissait d'un entretien, votre recruteur vous poserait des questions sur la complexité du temps et de l'espace.

Faisons une petite analyse.

Complexité temporelle

Itérer sur toute la chaîne d'entrée a une complexité temporelle de O (n), car il y a n caractères dans la chaîne elle-même.

Pour chacun de ces caractères, nous devons vérifier si nous avons vu ou non le… Cependant, comme un HashSet a un temps de recherche de O (1), notre complexité temporelle n'est pas affectée.

Nous laissant avec une complexité temporelle finale de O (n).

Complexité spatiale

Dans le pire des cas, nous obtenons une chaîne avec tous les caractères uniques. Par exemple, «abcdef».

Dans ce cas, nous stockerions tous les n éléments dans notre chaîne et notre ensemble.

Cependant, nous sommes également limités à la taille de l'alphabet anglais.

C'est une bonne occasion de demander à notre enquêteur quel type de caractères compte comme unique dans la chaîne (majuscules / minuscules / nombres / symboles).

En supposant que la chaîne initiale contienne des lettres minuscules de l'alphabet, puisque l'alphabet est fini, notre ensemble et la chaîne de sortie ne peuvent jamais dépasser 26 caractères.

Nous laissant avec une complexité spatiale du pire des cas de O (1).

Vous savez maintenant comment résoudre une question d'entrevue Google!

Cette question est susceptible de se poser dans les premières étapes de l'entrevue en raison de sa simplicité… Comme le test en ligne ou le premier appel téléphonique.

Si vous êtes un apprenant visuel comme moi, regardez cette vidéo que j'ai réalisée pour expliquer davantage la solution. Je crée chaque jour un nouveau tutoriel vidéo tournant autour du démarrage de votre carrière dans le logiciel.

J'ai également posté le code fini sur Github ici.

Merci d'avoir regardé et bonne chance!

.a # 33