Python >> Tutoriel Python >  >> Python

Ils utilisent ces 15+ questions d'entrevue Python pour vous faire échouer… (et ce que vous pouvez faire à ce sujet)

Vous craignez votre entretien de codage ? Cet article vous montre comment réussir votre entretien de codage.

Conseils généraux pour préparer votre entretien

  • Regardez les conseils d'entretien Google.
  • Lisez les conseils du professeur Philip Guo.
  • Entraînez-vous à coder dans Google Docs. N'utilisez pas d'éditeur de surbrillance de code pour votre temps de formation.
  • Résolvez au moins 50 énigmes de code.
  • Et le plus important :Ne paniquez pas .

Regardez la publication Instagram suivante et découvrez les questions d'entretien Python populaires (balayez vers la gauche, balayez vers la droite) :

Quelles questions de programmation devez-vous préparer ?

En lisant cet article, vous découvrirez ces 15 questions d'entrevue populaires. N'hésitez pas à passer à toute question qui vous intéresse le plus.

  • Question 1 :Obtenir le nombre manquant dans une liste d'entiers compris entre 1 et 100.
  • Question 2 : Rechercher un nombre en double dans une liste d'entiers.
  • Question 3 :Vérifier si une liste contient un entier x.
  • Question 4 :Trouvez le plus grand et le plus petit nombre dans une liste non triée.
  • Question 5 :Trouver des paires d'entiers dans une liste de sorte que leur somme soit égale à l'entier x.
  • Question 6 :Supprimez tous les doublons d'une liste d'entiers.
  • Question 7 :Trier une liste avec l'algorithme Quicksort.
  • Question 8 :Trier une liste avec l'algorithme Mergesort.
  • Question 9 :Vérifiez si deux chaînes sont des anagrammes.
  • Question 10 :Calculez l'intersection de deux listes.
  • Question 11 :Inverser la chaîne à l'aide de la récursivité.
  • Question 12 :Trouver toutes les permutations d'une chaîne.
  • Question 13 :Vérifiez si une chaîne est un palindrome.
  • Question 14 :Calculez les n premiers nombres de Fibonacci.
  • Question 15 :Utilisez la liste comme pile, tableau et file d'attente.
  • Question 16 :Rechercher une liste triée dans O(log n).

Pour vous faciliter l'apprentissage de ces questions, j'ai créé cette feuille de triche pour les entretiens Python avec 14 questions d'entrevue tirées de cet article.

Je vous enverrai ces feuilles de triche Python (et d'autres) sous forme de PDF téléchargeable s dans mon cours de messagerie gratuit . Ne vous inquiétez pas, je ne vous spammerai pas. Vous deviendrez simplement un meilleur codeur Python sur pilote automatique.

Rejoindre le cours Python Cheat Sheet
*LIBRE*

Question 1 :Obtenir le nombre manquant dans une liste d'entiers compris entre 1 et 100.

def get_missing_number(l):
    nxt = 1
    while nxt < len(l):
        if nxt != l[nxt-1]:
            return nxt
        nxt = nxt + 1

Il existe de nombreuses autres façons de résoudre ce problème (et d'autres plus concises). Par exemple, vous pouvez créer un ensemble de nombres de 1 à 100 et supprimer tous les éléments de la liste l. C'est une solution élégante car elle renvoie non pas un mais tous les nombres manquants dans la séquence. Voici cette solution :

set(range(l[len(l)-1])[1:]) - set(l)

Une solution alternative est la suivante :

lst = list(range(1, 101))
lst.remove(55)

total = sum(range(max(lst) + 1))
print(total - sum(lst))

Question 2 : Rechercher un nombre en double dans une liste d'entiers.

Disons que nous avons une liste de nombres entiers appelés éléments . Le but est de créer une fonction qui trouve TOUS les éléments entiers de cette liste qui sont dupliqués, c'est-à-dire qui existent au moins deux fois dans la liste. Par exemple, lors de l'application de notre fonction à la liste des éléments =[2, 2, 3, 4, 3], il retourne une nouvelle liste [2, 3] car les éléments entiers 2 et 3 sont dupliqués dans la liste éléments . En entretien, avant même de se lancer dans la « programmation sur papier », il faut toujours demander à l'intervieweur de revenir avec des exemples concrets pour montrer que vous avez bien compris la question.

Commençons donc à coder. Voilà ma première tentative:

def find_duplicates(elements):
    duplicates = set()
    seen = set() 

    for element in elements:
            if element in seen: # O(1) operation
                    duplicates.add(element)
            seen.add(element)
    return list(duplicates)


l = [2, 2, 2, 3, 4, 3, 6, 4, 3]
print(find_duplicates(l))
# [2, 3, 4]

Notez que la complexité d'exécution est assez bonne. Nous parcourons tous les éléments une fois dans la boucle principale. Le corps de la boucle principale a une durée d'exécution constante car j'ai sélectionné un ensemble pour les deux variables "doublons" et "vu". Vérifier si un élément est dans un ensemble, ainsi que l'ajout d'un élément à l'ensemble a un temps d'exécution constant (O(1)). Par conséquent, la complexité d'exécution totale est linéaire dans la taille d'entrée.

Finxter Mostafa a soumis la brillante solution suivante :

u = [1,2,2,3,4,5,4]
[u.remove(x) for x in list(set(u))]
print(list(set(u)))
# [2, 4]

Question 3 :Vérifier si une liste contient un entier x.

C'est un problème très simple. Je ne sais pas pourquoi un enquêteur poserait des questions aussi simples - c'est peut-être la première question "d'échauffement" pour que la personne interrogée se sente plus à l'aise. Pourtant, de nombreuses personnes ont déclaré que c'était l'une de leurs questions d'entrevue.

Pour vérifier si une liste Python contient un élément x en Python, cela peut être fait en itérant sur toute la liste et en vérifiant si l'élément est égal à l'élément d'itération actuel. En fait, ce serait aussi mon choix, si les éléments de la liste étaient des objets complexes qui ne sont pas hachables.

Cependant, le chemin facile est souvent le meilleur. La question d'entretien demande explicitement le confinement d'une valeur entière x. Comme les valeurs entières sont hachables, vous pouvez simplement utiliser le mot-clé Python "in" comme suit.

l = [3, 3, 4, 5, 2, 111, 5]
print(111 in l)
# True

Question 4 :Trouvez le plus grand et le plus petit nombre dans une liste non triée.

Encore une fois, cette question est une question simple qui montre votre utilisation efficace des mots-clés Python de base. N'oubliez pas :vous n'avez pas d'éditeur sophistiqué avec la mise en évidence du code source ! Ainsi, si vous ne formez pas le codage dans Google Docs, cela peut être un obstacle sérieux. Pire encore :le problème est en fait facile mais si vous ne parvenez pas à le résoudre, vous échouerez instantanément à l'entretien ! NE SOUS-ESTIMEZ JAMAIS UN PROBLÈME DE CODAGE !

Voici une solution simple pour Python :

l = [4, 3, 6, 3, 4, 888, 1, -11, 22, 3]

print(max(l))
# 888

print(min(l))
# -11

Cela ressemble à de la triche, n'est-ce pas? Mais notez que nous n'avons même pas utilisé de bibliothèque pour résoudre cette question d'entretien. Bien sûr, vous pouvez aussi faire quelque chose comme ceci :

def find_max(l):
    maxi = l[0]
    for element in l:
        if element > maxi:
            maxi = element
    return maxi


l = [4, 3, 6, 3, 4, 888, 1, -11, 22, 3]
print(max(l))
# 888

Quelle version préférez-vous ?

Question 5 :Trouver des paires d'entiers dans une liste de sorte que leur somme soit égale à l'entier x.

Ce problème est intéressant. La solution simple consiste à utiliser deux boucles for imbriquées et à vérifier pour chaque combinaison d'éléments si leur somme est égale à l'entier x. Voici ce que je veux dire :

def find_pairs(l, x):
    pairs = []
    for (i, element_1) in enumerate(l):
        for (j, element_2) in enumerate(l[i+1:]):
            if element_1 + element_2 == x:
                pairs.add((element_1, element_2))
    return pairs


l = [4, 3, 6, 3, 4, 888, 1, -11, 22, 3]
print(find_pairs(l, 9))

Échouer! Il lève une exception:"AttributeError:l'objet 'list' n'a pas d'attribut 'add'"

C'est ce que je voulais dire :il est facile de sous-estimer le niveau de difficulté des énigmes, seulement pour apprendre que vous avez encore fait une erreur d'inattention. Donc la solution corrigée est celle-ci :

def find_pairs(l, x):
    pairs = []
    for (i, element_1) in enumerate(l):
        for (j, element_2) in enumerate(l[i+1:]):
            if element_1 + element_2 == x:
                pairs.append((element_1, element_2))
    return pairs


l = [4, 3, 6, 3, 4, 888, 1, -11, 22, 3]
print(find_pairs(l, 9))

Maintenant, cela dépend si votre intervieweur acceptera cette réponse. La raison en est que vous avez beaucoup de paires dupliquées. S'il vous demandait de les supprimer, vous pourriez simplement faire un post-traitement en supprimant tous les doublons de la liste.

En fait, c'est aussi une question d'entrevue courante (voir la question suivante).

Voici une autre belle solution en une seule ligne soumise par l'un de nos lecteurs :

# Solution from user Martin 
l = [4, 3, 6, 4, 888, 1, -11, 22, 3] 
match = 9
res = set([(x, match - x) for e, x in enumerate(l) if x >= match / 2 and match - x in l[:e] + l[e+1:]])
print(res) 

Question 6 :Supprimer tous les doublons d'une liste d'entiers.

Étant donné une liste, le but est de supprimer tous les éléments qui existent plus d'une fois dans la liste. Notez que vous devez faire attention à ne pas supprimer d'éléments lors de l'itération sur une liste.

Mauvais exemple de modification d'une liste lors de l'itération (n'essayez pas cela à la maison):

lst = list(range(10))
for element in lst:
    if element >= 5:
        lst.remove(element)

print(lst)
# [0, 1, 2, 3, 4, 6, 8]

Comme vous pouvez le voir, la modification de la séquence sur laquelle vous itérez provoque un comportement non spécifié. Après avoir supprimé l'élément 5 de la liste, l'itérateur augmente l'index à 6. L'itérateur suppose qu'il s'agit de l'élément suivant dans la liste. Cependant, ce n'est pas le cas. Comme nous avons supprimé l'élément 5, l'élément 6 est maintenant à la position 5. L'itérateur ignore simplement l'élément. Par conséquent, vous obtenez cette sémantique inattendue.

Pourtant, il existe une bien meilleure façon de supprimer les doublons en Python. Vous devez savoir que les ensembles en Python n'autorisent qu'une seule instance d'un élément. Ainsi, après avoir converti la liste en un ensemble, tous les doublons seront supprimés par Python. Contrairement à l'approche naïve (vérifiant si toutes les paires d'éléments sont des doublons), cette méthode a une complexité d'exécution linéaire. La raison en est que la création d'un ensemble est linéaire en nombre d'éléments d'ensemble. Maintenant, nous devons simplement reconvertir l'ensemble en liste et voilà, les doublons sont supprimés.

lst = list(range(10)) + list(range(10))
lst = list(set(lst))
print(lst)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

# Does this also work for tuples? Yes!
lst = [(10,5), (10,5), (5,10), (3,2), (3, 4)]
lst = list(set(lst))
print(lst)
# [(3, 4), (10, 5), (5, 10), (3, 2)]

Question 7 :Trier une liste avec l'algorithme Quicksort.

C'est un problème difficile à résoudre lors d'un entretien de codage. À mon avis, la plupart des développeurs de logiciels ne sont pas capables d'écrire correctement l'algorithme Quicksort dans un document Google. Pourtant, nous le ferons, n'est-ce pas?

L'idée principale de Quicksort est de sélectionner un élément pivot, puis de placer tous les éléments supérieurs ou égaux à l'élément pivot à droite et tous les éléments inférieurs à l'élément pivot à gauche. Maintenant, vous avez divisé le gros problème du tri de la liste en deux sous-problèmes plus petits :trier les partitions droite et gauche de la liste. Ce que vous faites maintenant est de répéter cette procédure de manière récursive jusqu'à ce que vous obteniez une liste avec zéro élément. Cette liste est déjà triée, donc la récursivité se termine. Voici l'algorithme de tri rapide sous forme de one-liner Python :

def qsort(L):
    if L == []:
        return []
    return qsort([x for x in L[1:] if x<L[0]]) + L[0:1] + qsort([x for x in L[1:] if x>=L[0]])


lst = [44, 33, 22, 5, 77, 55, 999]
print(qsort(lst))
# [5, 22, 33, 44, 55, 77, 999]

Question 8 :Trier une liste avec l'algorithme Mergesort.

Il peut être assez difficile de coder l'algorithme Mergesort sous la pression émotionnelle et temporelle. Alors prenez votre temps maintenant pour bien le comprendre.

L'idée est de diviser la liste en deux sous-listes. Pour chacune des sous-listes, vous appelez maintenant le tri par fusion de manière récursive. En supposant que les deux listes sont triées, vous fusionnez maintenant les deux listes triées. Notez qu'il est très efficace de fusionner deux listes triées :cela ne prend qu'un temps linéaire dans la taille de la liste.

Voici l'algorithme résolvant ce problème.

def msort(lst):
    if len(lst)<=1:
        return lst
    
    left = msort(lst[:len(lst)//2])
    right = msort(lst[len(lst)//2:])
    return merge(left, right)


def merge(lst1, lst2):
    
    if len(lst1)==0:
        return lst2
    
    if len(lst2)==0:
        return lst1
    
    merged_list = []
    index_lst1 = 0
    index_lst2 = 0
    
    while len(merged_list) < (len(lst1) + len(lst2)):
        if lst1[index_lst1] < lst2[index_lst2]:
            merged_list.append(lst1[index_lst1])
            index_lst1 += 1
            if index_lst1 == len(lst1):
                merged_list += lst2[index_lst2:]
        else:
            merged_list.append(lst2[index_lst2])
            index_lst2 += 1
            if index_lst2 == len(lst2):
                merged_list += lst1[index_lst1:]

    return merged_list


lst = [44, 33, 22, 5, 77, 55, 999]
print(msort(lst))
# [5, 22, 33, 44, 55, 77, 999]

Question 9 :Vérifiez si deux chaînes sont des anagrammes.

Vous pouvez trouver cette question d'entrevue à tant d'endroits différents en ligne. C'est l'une des questions d'entrevue les plus populaires.

La raison en est que la plupart des étudiants qui ont suivi une formation universitaire en informatique savent exactement quoi faire ici. Il sert de filtre, de langage secret, qui révèle immédiatement si vous êtes dans ou hors de cette communauté.

En fait, ce n'est rien de plus. La vérification des anagrammes a peu ou pas d'applicabilité pratique. Mais c'est marrant, j'avoue !

Alors, que sont les anagrammes ? Deux mots sont des anagrammes s'ils sont composés exactement des mêmes caractères. Wikipédia le définit un peu plus précisément :"Une anagramme est un mot ou une phrase formé en réarrangeant les lettres d'un mot ou d'une phrase différente, en utilisant généralement toutes les lettres d'origine exactement une fois" .

Voici quelques exemples :

  • "écouter" → "silencieux"
  • "enterrement" → "vraiment amusant"
  • « elvis » → « vit »

Ok, maintenant vous savez exactement quoi faire, n'est-ce pas ? Commençons donc à coder.

def is_anagram(s1, s2):
    return sorted(s1) == sorted(s2)

s1 = "elvis"
s2 = "lives"
s3 = "not"
s4 = "hello"

print(is_anagram(s1, s2)) # True
print(is_anagram(s2, s3)) # False
print(is_anagram(s2, s4)) # False
print(is_anagram(s2, s1)) # True

Comme vous pouvez le voir, le programme résout le problème efficacement et correctement. Mais ce n'était pas ma première tentative. J'ai souffert de la vieille faiblesse des programmeurs :commencer à coder trop tôt. J'ai utilisé une approche pratique et créé une fonction récursive is_anagram(s1, s2). J'ai utilisé l'observation que s1 et s2 sont des anagrammes ssi (1) ils ont deux caractères égaux et (2) ils sont toujours des anagrammes si nous supprimons ces deux caractères (le petit problème). Bien que cette solution ait fonctionné, elle a également absorbé 10 minutes de mon temps.

En réfléchissant au problème, cela m'a frappé :pourquoi ne pas simplement trier les deux chaînes ? Deux chaînes sont des anagrammes si elles ont la même séquence de caractères triés. C'est si facile.

Je suis sûr, sans le rechercher, que trier les chaînes et comparer les représentations triées (comme cela est fait dans le code) est la solution la plus propre à ce problème.

Question 10 :Calculez l'intersection de deux listes.

Ce problème semble facile (attention !). Bien sûr, si vous avez des connaissances en bibliothèque (comme numpy), vous pouvez résoudre ce problème avec un seul appel de fonction. Par exemple, la bibliothèque de Python pour l'algèbre linéaire (numpy) a une implémentation de la fonction d'intersection. Pourtant, nous supposons que nous n'avons PAS de connaissances en bibliothèque dans l'entretien de codage (c'est un pari beaucoup plus sûr).

La fonction d'intersection prend deux listes en entrée et renvoie une nouvelle liste qui contient tous les éléments qui existent dans les deux listes.

Voici un exemple de ce que nous voulons faire :

  • intersect([1, 2, 3], [2, 3]) → [2, 3]
  • intersect([“hi”, “my”, “name”, “is”, “slim”, “shady”], [“i”, “like”, “slim”]) → [“slim”]
  • intersect([3, 3, 3], [3, 3]) → [3, 3]

Vous pouvez utiliser le code suivant pour ce faire.

def intersect(lst1, lst2):
    res = []
    lst2_copy = lst2[:]
    for el in lst1:
        if el in lst2_copy:
            res.append(el)
            lst2_copy.remove(el)
    return res


# Are the results ok?
print(intersect([1, 2, 3], [2, 3]))
# [2, 3]

print(intersect("hi my name is slim shady".split(" "),
                "i like slim".split(" ")))
# ['slim']

print(intersect([3, 3, 3], [3, 3]))
# [3, 3]

# Are the original lists untouched?
lst1 = [4, 4, 3]
lst2 = [3, 4, 2]
print(intersect(lst1, lst2))
# [4, 3]
      
print(lst1)
# [4, 4, 3]

print(lst2)
# [3, 4, 2]

Nous avons donc bien défini la sémantique, ce qui devrait suffire à réussir l'entretien. Le code est correct et il garantit que la liste d'origine n'est pas touchée.

Mais est-ce vraiment la version la plus concise ? Je ne pense pas! Ma première idée était d'utiliser à nouveau des ensembles sur lesquels nous pouvons effectuer des opérations telles que l'intersection d'ensembles. Mais lors de l'utilisation d'ensembles, nous perdons les informations sur les entrées en double dans la liste. Une solution simple dans ce sens n'est donc pas en vue.

Ensuite, je pensais à la compréhension de liste. Pouvons-nous faire quelque chose dans ce sens ? La première idée est d'utiliser la compréhension de liste comme ceci :

def intersect(lst1, lst2):
    lst2_copy = lst2[:]
    return [x for x in lst1 if lst2.remove(x)]

Cependant, voyez-vous le problème avec cette approche?

Le problème est que intersect([4, 4, 3], [4, 2]) renvoie [4, 4]. C'est une erreur évidente ! Ce n'est pas facile à voir - j'ai trouvé de nombreuses ressources en ligne qui ignorent tout simplement ce problème...

Le nombre 4 existe deux fois dans la première liste mais si vous cochez "4 dans [4, 2]", il renvoie Vrai - peu importe la fréquence de vérification. C'est pourquoi nous devons supprimer le nombre entier 4 de la deuxième liste après l'avoir trouvé la première fois.

C'est exactement ce que j'ai fait dans le code ci-dessus. Si vous avez une idée de la façon de résoudre ce problème avec la compréhension de liste, faites-le moi savoir ([email protected]) ! 🙂

Modifier :J'ai reçu une solution très intelligente utilisant la compréhension de liste avec des effets secondaires :

def intersect(lst1, lst2):
    lst2_copy = lst2[:]
    return [(x, lst2_copy.remove(x))[0] for x in lst1 if x in lst2_copy]


lst1 = [4, 4, 3]
lst2 = [3, 4, 2]
print(intersect(lst1, lst2))                               # [4, 3]
print(lst1)                                                # [4, 4, 3]
print(lst2) 

Finxter Mostafa a soumis la solution en une seule ligne suivante :

intersect = lambda x,y: set(x) - (set(x) - set(y))

Excellent travail !

Question 11 :Inverser une chaîne à l'aide de la récursivité

Passons maintenant au problème suivant :inverser une chaîne à l'aide de la récursivité.

Voici ce que nous voulons réaliser :

  • "bonjour" → "Olleh"
  • "non" → "activé"
  • "oui nous pouvons" → "nac ew sey"

Il y a une restriction sur votre solution :vous devez utiliser la récursivité. En gros, la fonction devrait s'appeler sur une instance de problème plus petite.

Wikipedia explique la récursivité de manière compréhensible :

Clairement, la stratégie suivante résoudrait le problème de manière récursive. Tout d'abord, vous prenez le premier élément d'une chaîne et vous le déplacez jusqu'à la fin. Deuxièmement, vous prenez le reste de la chaîne et répétez cette procédure de manière récursive jusqu'à ce qu'il ne reste qu'un seul caractère.

Voici le code :

def reverse(string):
    if len(string)<=1:
        return string
    else:
        return reverse(string[1:]) + string[0]


phrase1 = "hello"
phrase2 = "no"
phrase3 = "yes we can"

print(reverse(phrase1))
# olleh
print(reverse(phrase2))
# on
print(reverse(phrase3))
# nac ew sey

Le programme fait exactement ce que j'ai décrit plus tôt :déplacer le premier élément à la fin et appeler la fonction de manière récursive sur la chaîne restante.

Question 12 :Trouver toutes les permutations d'une chaîne

Il s'agit d'un problème commun à de nombreux entretiens de codage. Semblable au problème des anagrammes présenté dans la question ci-dessus, le but de cette question est double. Tout d'abord, les enquêteurs vérifient votre créativité et votre capacité à résoudre des problèmes algorithmiques. Deuxièmement, ils vérifient votre connaissance préalable de la terminologie informatique.

Qu'est-ce qu'une permutation ? Vous obtenez une permutation à partir d'une chaîne en réorganisant ses caractères. Revenons au problème des anagrammes. Deux anagrammes sont des permutations l'une de l'autre car vous pouvez construire l'une à partir de l'autre en réorganisant les caractères.

Voici toutes les permutations à partir de quelques exemples de chaînes :

  • ‘hello’ → {'olhel', 'olhle', 'hoell', 'ellho', 'lhoel', 'ollhe', 'hlleo', 'lhloe', 'hello', 'lhelo', 'hlelo', 'eohll', 'oellh', 'hlole', 'lhole', 'lehlo', 'ohlel', 'oehll', 'lleoh', 'olleh', 'lloeh', 'elhol', 'leolh', 'ehllo', 'lohle', 'eolhl', 'llheo', 'elhlo', 'ohlle', 'lohel', 'elohl', 'helol', 'loehl', 'lheol', 'holle', 'elloh', 'llhoe', 'eollh', 'olehl', 'lhleo', 'loleh', 'ohell', 'leohl', 'lelho', 'olelh', 'heoll', 'ehlol', 'loelh', 'llohe', 'lehol', 'holel', 'hleol', 'leloh', 'elolh', 'oelhl', 'hloel', 'lleho', 'eholl', 'hlloe', 'lolhe'}
  • ‘hi’ → {‘hi’, ‘ih’}
  • ‘bye’ → {‘bye’, ‘ybe’, ‘bey’, ‘yeb’, ‘eby’, ‘eyb’}

Conceptuellement, vous pouvez considérer une chaîne comme un seau de caractères. Disons que la chaîne a une longueur n. Dans ce cas, vous avez n postes à pourvoir à partir du seau de n caractères. Après avoir rempli toutes les n positions, vous obtenez une permutation à partir de la chaîne. Vous voulez trouver TOUTES ces permutations.

Ma première idée est de résoudre ce problème de manière récursive . Supposons que nous connaissions déjà toutes les permutations d'une chaîne de n caractères. Maintenant, nous voulons trouver toutes les permutations avec n+1 caractères en ajoutant un caractère x. Nous obtenons toutes ces permutations en insérant x dans chaque position d'une permutation existante. Nous répétons ceci pour toutes les permutations existantes.

Cependant, en règle générale :évitez à tout prix de trop compliquer le problème lors d'un entretien de codage ! N'essayez pas d'être chic! (Et n'utilisez pas la récursivité - c'est une conclusion logique des déclarations précédentes...)

Existe-t-il une solution itérative plus simple ? Malheureusement, je n'ai pas trouvé de solution itérative simple (il existe l'algorithme de Johnson-Trotter mais ce n'est guère une solution à présenter lors d'un entretien de codage).

Ainsi, je suis retourné pour implémenter la solution récursive décrite ci-dessus. (*grincer des dents* )

def get_permutations(word):

    # single word permutations
    if len(word)<=1:
        return set(word)

    # solve smaller problem recursively
    smaller_perms = get_permutations(word[1:])

    # find all permutation by inserting the first character
    # to each position of each smaller permutation
    perms = set()
    for small_perm in smaller_perms:
        for pos in range(0,len(small_perm)+1):
            perm = small_perm[:pos] + word[0] + small_perm[pos:]
            perms.add(perm)
    return perms

        

print(get_permutations("nan"))
print(get_permutations("hello"))
print(get_permutations("coffee"))

# {'nna', 'ann', 'nan'}
# {'olhel', 'olhle', 'hoell', 'ellho', 'lhoel', 'ollhe', 'hlleo', 'lhloe', 'hello', 'lhelo', 'hlelo', 'eohll', 'oellh', 'hlole', 'lhole', 'lehlo', 'ohlel', 'oehll', 'lleoh', 'olleh', 'lloeh', 'elhol', 'leolh', 'ehllo', 'lohle', 'eolhl', 'llheo', 'elhlo', 'ohlle', 'lohel', 'elohl', 'helol', 'loehl', 'lheol', 'holle', 'elloh', 'llhoe', 'eollh', 'olehl', 'lhleo', 'loleh', 'ohell', 'leohl', 'lelho', 'olelh', 'heoll', 'ehlol', 'loelh', 'llohe', 'lehol', 'holel', 'hleol', 'leloh', 'elolh', 'oelhl', 'hloel', 'lleho', 'eholl', 'hlloe', 'lolhe'}
# {'coeeff', 'ceoeff', 'ceofef', 'foecef', 'feecof', 'effeoc', 'eofefc', 'efcfoe', 'fecofe', 'eceoff', 'ceeffo', 'ecfeof', 'coefef', 'effoce', 'fceefo', 'feofce', 'fecefo', 'ocefef', 'ffecoe', 'ofcefe', 'fefceo', 'ffeoce', 'ffoeec', 'oefcfe', 'ofceef', 'efeofc', 'eefcof', 'ceffoe', 'eocfef', 'ceffeo', 'eoffec', 'ceoffe', 'fcoefe', 'cefofe', 'oeeffc', 'oeffec', 'fceeof', 'ecfofe', 'feefoc', 'ffcoee', 'feocef', 'ffceeo', 'fofcee', 'fecfoe', 'fefoec', 'eefcfo', 'eofcfe', 'ffceoe', 'ofcfee', 'ceefof', 'effoec', 'offcee', 'fofeec', 'eecffo', 'cofefe', 'feeofc', 'ecofef', 'effceo', 'cfeefo', 'ffeoec', 'eofcef', 'cffeeo', 'cffoee', 'efcefo', 'efoefc', 'eofecf', 'ffeceo', 'ofefec', 'foeecf', 'oefefc', 'oecffe', 'foecfe', 'eeffoc', 'ofecfe', 'oceeff', 'offece', 'efofce', 'fcoeef', 'fcofee', 'oefecf', 'fcefeo', 'cfefoe', 'cefoef', 'eoceff', 'ffoece', 'feofec', 'offeec', 'oceffe', 'eeoffc', 'cfoeef', 'fefcoe', 'ecoeff', 'oeecff', 'efofec', 'eeffco', 'eeofcf', 'ecfefo', 'feoefc', 'ecefof', 'feceof', 'oeefcf', 'ecffoe', 'efecfo', 'cefeof', 'fceofe', 'effeco', 'ecfoef', 'efeocf', 'ceeoff', 'foceef', 'focfee', 'eoeffc', 'efoecf', 'oefcef', 'oeffce', 'ffocee', 'efceof', 'fcfeeo', 'eoefcf', 'ocffee', 'oeceff', 'fcfeoe', 'fefeoc', 'efefco', 'cefefo', 'fecfeo', 'ffeeco', 'ofefce', 'cfofee', 'cfefeo', 'efcoef', 'ofeecf', 'eecoff', 'ffeeoc', 'eefofc', 'ecoffe', 'coeffe', 'eoecff', 'fceoef', 'foefec', 'cfeeof', 'cfoefe', 'efefoc', 'eeocff', 'eecfof', 'ofeefc', 'effcoe', 'efocef', 'eceffo', 'fefeco', 'cffeoe', 'feecfo', 'ecffeo', 'coffee', 'feefco', 'eefocf', 'fefoce', 'fofece', 'fcefoe', 'ocfeef', 'eoffce', 'efcofe', 'foefce', 'fecoef', 'cfeoef', 'focefe', 'ocfefe', 'eocffe', 'efocfe', 'feoecf', 'efecof', 'cofeef', 'fcfoee', 'oecfef', 'feeocf', 'ofecef', 'cfeofe', 'feocfe', 'efcfeo', 'foeefc'}

Si vous avez des questions, s'il vous plaît laissez-moi savoir! J'ai été vraiment surpris de constater qu'il n'y a pas de solution Python à ce problème. Si vous en connaissez un, partagez-le avec moi ([email protected]) !

Modifier :Finxter Janos a soumis une solution basée sur l'opérateur ternaire, la compréhension de liste, les fonctions lambda et la récursivité. Un coup de génie !

# One-Liner Solution By Janos:
text1 = 'bye'
perm = lambda text: list(set([c + txt for c in text for txt in perm(text.replace(c, '', 1))])) if len(text) > 1 else text
print(perm(text1))

Question 13 :Vérifier si une chaîne est un palindrome.

Tout d'abord. Qu'est-ce qu'un palindrome ?

Voici quelques exemples amusants :

  • "M. Hibou a mangé mon ver de métal"
  • "Est-ce que j'ai vu une voiture ou un chat ?"
  • "Allez accrocher un salami, je suis un cochon de lasagne"
  • "Les rats ne vivent sur aucune mauvaise étoile"
  • "Hannah"
  • "Anne"
  • "Bob"

Maintenant, cela ressemble à une solution courte et concise en Python !

def is_palindrome(phrase):
    return phrase == phrase[::-1]

print(is_palindrome("anna"))
print(is_palindrome("kdljfasjf"))
print(is_palindrome("rats live on no evil star"))

# True
# False
# True

Voici un conseil important :apprenez à trancher en Python par cœur pour votre entretien de codage. Vous pouvez télécharger mon livre de découpage gratuit pour vraiment vous préparer à fond pour la partie découpage de l'entretien. Inscrivez-vous simplement à ma newsletter gratuite et je vous enverrai la version dès qu'elle sera prête et relue !

Question 14 :Calculez les n premiers nombres de Fibonacci.

Et voici… encore un autre problème de jouet qui détruira instantanément vos chances de succès s'il n'est pas résolu correctement.

La série de Fibonacci a été découverte par le mathématicien italien Leonardo Fibonacci en 1202 et même plus tôt par des mathématiciens indiens. La série apparaît dans des domaines inattendus tels que l'économie, les mathématiques, l'art et la nature.

La série commence par les nombres de Fibonacci zéro et un. Ensuite, vous pouvez calculer l'élément suivant de la série comme la somme des deux derniers éléments.

Pour cela, l'algorithme doit garder une trace uniquement des deux derniers éléments de la série. Ainsi, nous maintenons deux variables a et b, étant respectivement l'avant-dernier et le dernier élément de la série.

# Fibonacci series:
a, b = 0, 1
n = 10 # how many numbers we calculate
for i in range(n):
    print(b)
    a, b = b, a+b

'''
1
1
2
3
5
8
13
21
34
55
'''

Pour plus de clarté du code, j'ai utilisé la fonctionnalité de langue des devoirs multiples dans la première et la dernière ligne.

Cette fonction fonctionne comme suit. Sur le côté gauche de l'affectation, il y a n'importe quelle séquence de variables comme une liste ou un tuple. A droite de l'affectation, vous indiquez les valeurs à affecter à ces variables. Les deux séquences à gauche et à droite doivent avoir la même longueur. Sinon, l'interpréteur Python renverra une erreur.

Notez que toutes les expressions du côté droit sont d'abord évaluées avant d'être affectées. C'est une propriété importante pour notre algorithme. Sans cette propriété, la dernière ligne serait erronée car l'expression 'a+b' considérerait la mauvaise valeur pour 'a'.

Question 15 :Utiliser une liste comme pile, tableau et file d'attente.

Ce problème semble facile. Mais je suis sûr qu'il fait ce qu'il est censé faire :séparer les programmeurs expérimentés des débutants.

Pour le résoudre, il faut connaître par cœur la syntaxe des listes. Et combien de débutants ont étudié en détail comment accéder à une liste en Python ? Je suppose que pas trop…

Prenez donc votre temps pour étudier attentivement ce problème. Votre connaissance de la structure des données de la liste est d'une grande importance pour votre carrière de programmeur réussie !

Commençons à utiliser une liste de trois manières différentes :comme pile, comme tableau et comme file d'attente.

# as a list ...
l = []
l.append(3) # l = [3]
l.append(4) # l = [3, 4]
l +=  [5, 6] # l = [3, 4, 5, 6]
l.pop(0) # l = [4, 5, 6]


# ... as a stack ...
l.append(10) # l = [4, 5, 6, 10]
l.append(11) # l = [4, 5, 6, 10, 11]
l.pop() # l = [4, 5, 6, 10]
l.pop() # l = [4, 5, 6]

# ... and as a queue
l.insert(0, 5) # l = [5, 4, 5, 6]
l.insert(0, 3) # l = [3, 5, 4, 5, 6]
l.pop() # l = [3, 5, 4, 5]
l.pop() # l = [3, 5, 4]

print(l)
# [3, 5, 4]

Si vous avez besoin de connaissances de base, consultez le didacticiel Python et ces articles sur la structure des données de la pile et la structure des données de la file d'attente.

Question 16 :Rechercher une liste triée en O(log n)

Comment rechercher une liste en runtime logarithmique? Ce problème a tellement d'applications pratiques que je peux comprendre que les enquêteurs de codage l'adorent.

L'algorithme le plus populaire qui résout ce problème est l'algorithme de recherche binaire. Voici quelques-unes des applications :


Pensez à l'impact d'une recherche efficace ! Vous utilisez ces structures de données dans chaque programme non trivial (et dans de nombreux programmes triviaux également).

Le graphique vous montre l'algorithme de recherche binaire au travail. La liste triée se compose de huit valeurs. Supposons que vous vouliez trouver la valeur 56 dans la liste.

L'algorithme trivial parcourt toute la liste du premier au dernier élément en comparant chacun à la valeur recherchée. Si votre liste contient n éléments, l'algorithme trivial aboutit à n comparaisons. Par conséquent, la complexité d'exécution de l'algorithme trivial est O(n).

(Si vous ne vous sentez pas à l'aise avec la notation Big-O, rafraîchissez vos connaissances sur les symboles Landau ici.)

Mais notre but est de parcourir la liste triée en temps logarithmique O(log n). On ne peut donc pas se permettre de toucher à chaque élément de la liste.

L'algorithme de recherche binaire dans le graphique sonde à plusieurs reprises l'élément au milieu de la liste (arrondi vers le bas). Il y a trois cas :

  1. Cet élément x est supérieur à la valeur recherchée 55. Dans ce cas, l'algorithme ignore la partie droite de la liste car tous les éléments sont également supérieurs à 55. C'est parce que la liste est déjà triée.
  2. L'élément x est plus petit que la valeur recherchée 55. C'est le cas, nous l'observons sur la figure. Ici, l'algorithme ignore la partie gauche de la liste car elle est également plus petite (encore une fois, en utilisant la propriété que la liste est déjà triée).
  3. L'élément x est égal à la valeur recherchée 55. Vous pouvez voir ce cas dans la dernière ligne de la figure. Félicitations, vous avez trouvé l'élément dans la liste !

A chaque phase de l'algorithme, l'espace de recherche est réduit de moitié ! Cela signifie qu'après un nombre logarithmique d'étapes, nous avons trouvé l'élément !
Après avoir compris l'algorithme, il est facile de trouver le code. Voici ma version de l'algorithme de recherche binaire.

def binary_search(lst, value):
    lo, hi = 0, len(lst)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if lst[mid] < value:
            lo = mid + 1
        elif value < lst[mid]:
            hi = mid - 1
        else:
            return mid
    return -1

    
l = [3, 6, 14, 16, 33, 55, 56, 89]
x = 56
print(binary_search(l,x))
# 6 (the index of the found element)

Félicitations, vous avez répondu à ces 15+ questions d'entrevue extrêmement populaires. N'oubliez pas de résoudre au moins 50 énigmes de code Python ici.

Merci d'avoir lu cet article. Si vous avez d'autres questions d'entretien (ou si vous rencontrez des difficultés avec l'une des questions ci-dessus), veuillez m'écrire un e-mail à [email protected].


Je vous recommande de vous inscrire à mon cours Python gratuit par e-mail . Vous obtiendrez 5 feuilles de triche Python super simples . En bonus , je vous enverrai 10+ e-mails Python éducatifs . Pas de spam. 100 % GRATUIT !

Oui, je veux développer mes compétences Python !

Articles connexes :

  • [Collection] 11 feuilles de triche Python que chaque codeur Python doit posséder
  • [Python OOP Cheat Sheet] Un aperçu simple de la programmation orientée objet
  • [Collection] 15 feuilles de triche époustouflantes pour le machine learning à épingler au mur de vos toilettes
  • Votre 8+ aide-mémoire Python gratuit [Cours]
  • Aide-mémoire Python pour débutant :19 mots clés que tout codeur doit connaître
  • Feuille de triche sur les fonctions et astuces Python
  • Aide-mémoire Python :14 questions d'entretien
  • Aide-mémoire sur les beaux pandas
  • 10 meilleures feuilles de triche NumPy
  • Aide-mémoire sur les méthodes de liste Python [Téléchargement PDF instantané]
  • [Aide-mémoire] Algorithmes d'apprentissage automatique à 6 piliers