Dans la plupart des processus de recrutement pour un poste de Développeur Python ou Data Scientist, les candidats sont confrontés selon leur niveau à un test technique. C’est très souvent un passage obligé et cela permet aux entreprises de vérifier les compétences et le niveau des candidats.
Ce test technique peut servir parfois de présélection avant tout échange avec un recruteur et il est très important de bien le préparer. Certains sites comme CodinGame, Skill Value proposent ces tests sous forme de QCM et/ou d’algorithmes à résoudre.
Dans cet article, nous présentons 25 algorithmes à résoudre, allant de la manipulation de chaînes de caractères à celle des collections de données, pour réussir les tests techniques. 🤠
1. Entier inversé
Nous souhaitons inverser un entier (positif ou négatif), c’est-à-dire notre fonction prend en entrée un entier -6523 par exemple et retourne en sortie l’entier inversé -3256.
def reverse_int(integer):
sign = integer // abs(integer) # signe de l'entier (+ ou -)
return int(str(abs(integer))[::-1])*sign
# Afficher les résultats de notre fonction pour 2020 et -9430
print(reverse_int(2020))
print(reverse_int(-9430))
[Output]
202
-349
Il est très utile de savoir manipuler les types basiques et faire du cast. Nous rappelons juste qu’il est possible de convertir un entier en chaîne de caractères et vice-versa grâce aux fonctions str() et int() respectivement. De plus, 2 choses à retenir pour aboutir au résultat :
- La fonction native
abs()de Python qui permet notamment de calculer la valeur absolue d’un nombre. - Inverser une chaîne de caractères, considérée comme une liste, avec
[::-1].
2. Triplet Pythagoricien dans une liste de nombres
Et oui, le théorème de Pythagore que nous avons vu au collège, on le retrouve dans notre article.
Ici, le jeu consiste à retrouver dans une liste d’entiers, tous les triplets pythagoriciens possibles qui y sont. Pour rappel, un triplet pythagoricien respecte le théorème suivant : a2 + b2 = c2.
Prenons l’exemple suivant : nous avons la liste [0, 3, 6, 1, 2, 4, 5]. Notre fonction renvoie la liste des triplets possibles : [(3, 4, 5)] car 9 + 16 = 25.
from math import sqrt # Importer la fonction de racine carrée
def is_Pythagorean_triplet(list_):
# Vérifier que notre liste est de longueur appropriée avant tout traitement
if len(list_) < 3:
triplet = "Il faudrait réessayer avec une liste d'entiers positifs de longueur minimum 3."
# Notre liste est de longueur minimum 3
else:
n = len(list_) # Longueur de notre liste
triplet = [] # Liste de tuples à retourner
m = 0 # Index du premier élément de la liste
# Parcourons notre liste et recherchons les triplets Pythagoriciens
for i in range(n - 2):
for k in range(m + 1, n):
for j in range(k + 1, n - 1):
# Calculons le carré de chaque élément de la liste
x = list_[i] * list_[i]
y = list_[j] * list_[j]
z = list_[k] * list_[k]
if x == y + z or y == x + z or z == x + y:
triplet.append((int(sqrt(x)),
int(sqrt(y)),
int(sqrt(z))))
# Nous retournons la liste des triplets Pythagoriciens
return triplet # Notre liste peut être vide si nous en trouvons pas
# Application de notre fonction
print(is_Pythagorean_triplet([0, 3, 6, 1, 2, 4, 5]))
[Output]
[(3, 4, 5)]
La logique derrière cet algorithme est de parcourir la liste avec 3 valeurs différentes, calculer le carré de chaque nombre et faire la comparaison du théorème. S’il y a égalité, on renvoie la racine carrée de chaque nombre grâce à la fonction sqrt() – square root en anglais – du module math de Python.
L’une des limites de cet algorithme est sa complexité en temps : O(n3) ce qui peut prendre beaucoup de temps pour des listes de grande taille.
N’hésitez pas en commentaires à proposer des améliorations. 🤠
3. Longueur moyenne des mots
Nous avons la phrase suivante : "Le blog 'ledatascientist' est le blog français de référence en Data Science.". Nous allons maintenant écrire une fonction qui calcule la longueur moyenne des mots de notre texte.
Bien sûr que nous supprimons les ponctuations ! 😉
def average_words_length(sentence):
for punctuation in "!?',;.":
sentence = sentence.replace(punctuation, ' ') # remplacer dans notre texte, les caractères de ponctuation par un espace
words = sentence.split() # splitter notre texte en mots
return round(sum(len(word) for word in words)/len(words), 2) # retourner la longueur moyenne des mots avec deux décimales maximum
sentence1 = "Même les phrases avec des caractères de la langue française peuvent être utilisées."
sentence2 = "Le blog 'ledatascientist' est le blog français de référence en Data Science."
print(average_words_length(sentence1))
print(average_words_length(sentence2))
[Output]
5.38
5.17
Deux fonctions sont utiles pour réaliser cet algorithme : .replace() pour supprimer tous les caractères indésirables et .split() pour créer à partir de notre texte une liste des mots contenus dans le texte.
4. Suite de Fibonacci
On fait de tout dans cet article 😎
La célèbre suite de Fibonacci présente partout autour de nous, on la réinvente à notre manière ici mais on garde toujours le même principe.
Dans notre cas, on va chercher les nombres de Fibonacci compris entre deux entiers positifs.
Rappelons que pour une suite de Fibonacci, on a : Un = Un-1 + Un-2 avec n ≥ 2 et U1 = U0 = 1. On imagine donc les 5 premiers nombres de la suite : 1, 1, 2, 3 et 5. Quels nombres de Fibonacci y a-t-il entre 10 et 22 par exemple ? 🤔
# La fonction de calcul d'un nombre de Fibonacci
def fibonacci(n):
if n < 0 :
print("N doit être supérieur ou égal à 0")
if n <= 1:
return n
else:
return(fibonacci(n-1) + fibonacci(n-2))
# La fonction de calcul des nombres de Fibonacci compris entre 2 entiers positifs
def print_fibo_number(int_a, int_b):
n = 0
valueList = []
while fibonacci(n) <= max (int_a, int_b) :
valueList.append(fibonacci(n))
n+=1
return [i for i in valueList if min(int_a, int_b) <= i <= max (int_a, int_b)]
print_fibo_number(10, 22)
[Output]
[13, 21]
On utilise ici une fonction récursive fibonacci dans la seconde fonction. Et on calcule et compare l’ensemble des nombres de Fibonacci avec les entiers pour n’en retenir que ceux compris entre ces derniers.
5. Additionner deux strings
On veut avec cet algorithme pouvoir faire ceci : '100' + '150' = '250'. (Impossible car lorsqu’on fait '100' + '150', on obtient '100150' 🤨) Eh bien, pour faire cela, rien de plus fastoche que les cast encore une fois. 😃
def add_strings(num1, num2):
return str(int(num1) + int(num2))
result = add_strings('8573', '107')
print(result)
print(type(result))
[Output]
8680
<class 'str'>
Assez facile quand on sait manipuler les types Python !
6. Recherche dichotomique
Il est classique de demander dans des interviews l’implémentation d’un algorithme de recherche dichotomique. Au passage, il existe plusieurs types d’algorithmes de recherche et celle-ci est la plus robuste mais pas la plus rapide.
Le principe est de rechercher un nombre dans une liste triée. Cette méthode va découper la liste en deux et comparer à chaque itération l’élément recherché avec celui du milieu de la liste. Si l’élément recherché est plus grand que celui du milieu, on recherche dans la partie droite de la liste, sinon dans la partie gauche. Et on reprend la même chose avec la nouvelle liste jusqu’à trouver l’élément. Pour en savoir plus : ici.
def dicho(list_, element):
length = len(list_) # Longueur de la liste
# Si la liste est vide, on retourne False
if length == 0:
return False
mid = int(length/2) # L'index de notre élément du milieu
# Si l'élément recherché est celui du milieu, on le retourne directement
if list_[mid] == element:
return list_[mid]
# Si l'élément est inférieur, on recommence sur la partie gauche
if element < list_[mid]:
return dicho(list_[:mid], element)
# Si l'élément est supérieur, on recommence sur la partie droite
else:
return dicho(list_[mid+1:], element)
A = [1,2,3,5,8,9]
print(dicho(A, 5))
print(dicho(A, 10))
[Output]
5
False
7. Premier caractère unique
Nous avons un mot et nous voulons savoir quel est le premier caractère unique de ce mot, c’est-à-dire la lettre qui ne se répète pas dans le mot et la première. Prenons un exemple simple, le mot 'ledatascientist' ; le premier caractère unique est la lettre 'l' et se trouve à l’index 0.
import collections
def first_unique_character(word):
word = word.lower() # Mettre le mot en minuscule
# Construire une correspondance entre les lettres et leurs occurrences dans le mot
count = collections.Counter(word) # retourne un dictionnaire
for idx, ch in enumerate(count):
if count[ch] == 1:
return (ch, idx)
return -1
print(first_unique_character('coronavirus'))
print(first_unique_character('Europe'))
[Output]
('c', 0)
('u', 1)
Dans cet algorithme, nous utilisons la fonction .Counter() de la librairie collections. Cette fonction nous retourne un dictionnaire trié (type Counter) qui fait une correspondance entre chaque lettre et son occurrence dans le mot. Par exemple, collections.Counter('ledatascientist') donne le dictionnaire Counter({'t': 3, 'e': 2, 'a': 2, 's': 2, 'i': 2, 'l': 1, 'd': 1, 'c': 1, 'n': 1}).
8. Inverser et garder la position des caractères spéciaux
Inverser une chaîne de caractères sans modifier la position des caractères spéciaux : !@#$%^&*()-_=+~ etc. Prenons un exemple, c’est plus simple.
Nous avons notre string suivant "Alo*etui@l)ios82?" et notre algorithme doit permettre d’inverser tous les caractères sans faire bouger les caractères spéciaux comme ceci : "28s*oili@u)teolA?".
def inverse_special_char(word):
word1 = [x for x in word] # Créons une liste des caractères de word
index = -1
# Parcourons à partir du dernier index jusqu'à l'index de milieu
for i in range(len(word1)-1, int(len(word1)/2), -1):
# Vérifier si notre caractère est alphanumérique ou non
if word1[i].isalnum():
temp = word1[i]
while True:
index += 1
if word1[index].isalnum():
word1[i] = word1[index]
word1[index] = temp
break
inverse_special_char = '' # Initialisons notre nouveau mot à vide
# Construisons notre nouveau à partir de word1
for char in word1:
inverse_special_char += char # Concaténons chaque caractère de word1
return inverse_special_char
word = "Alo*etui@l)ios82?"
# expected : "28s*oili@u)teolA?"
print(inverse_special_char(word))
[Output]
28s*oili@u)teolA?
Cela paraissait compliqué au départ mais à l’aide de la manipulation de listes et la fonction .isalnum() qui permet de vérifier si un caractère est alphanumérique ou non, on s’en sort pas mal. 🎉
9. Presque palindrome
C’est l’un des exercices classiques en manipulation de chaînes de caractères : le palindrome. Le palindrome est un mot qui reste le même qu’on le lise de gauche à droite ou de droite à gauche pour faire simple. Dans notre exercice, nous allons vérifier si, en supprimant une (et une seule) lettre à un mot, on obtient un palindrome. Voyons ça dans notre code.
def almost_palindromic(word):
word = word.lower() # mettre le mot en minuscule
for i in range(len(word)):
t = word[:i] + word[i+1:]
if t == t[::-1]:
return (word[i], True, t) # retourne la lettre à supprimer, True et le palindrome trouvé
return word == word[::-1] # retourne True ou False
print(almost_palindromic('katyak'))
print(almost_palindromic('Hannah'))
[Output]
('t', True, 'kayak')
('n', True, 'hanah')
10. Chemin d’accès de mon fichier
Cet exercice revient très souvent dans un test CodinGame. L’idée est de retrouver le chemin d’accès d’un fichier à partir de la racine par exemple.root
├── directory1
├── directory2
| ├── file21
| ├── file22
└── file1
Notre algorithme prend en entrée root et le nom du fichier à trouver file22. Il doit nous retourner en sortie le chemin suivant : /root/directory2/file22/.
import os
def find_files(filename, search_path):
result = []
# Marche de haut en bas depuis la racine
for root, dir, files in os.walk(search_path):
if filename in files:
result.append(os.path.join(root, filename))
return result
! mkdir dir1
! mkdir dir2
! mkdir dir1/dir1_sub1
! mkdir dir2/dir2_sub1
# Creation des fichiers examples
! touch dir1/dir1_sub1/example1
! touch dir2/example1
find_files("example1", "/content")
[Output]
['/content/dir1/dir1_sub1/example1', '/content/dir2/example1']
Le module adapté à cet exercice est os. Sa fonction .walk() qui prend en entrée un chemin d’accès racine et renvoie la liste de tous les fichiers et dossiers présents dans cette racine par arborescence.
Quant à la fonction .join() des chaînes de caractères, elle permet de bien écrire le chemin d’accès (path) dans la fonction .path() de os.
11. Liste monotone
Nous allons dire si une liste est monotone ou non, c’est-à-dire si notre liste de nombres (entiers) est triée dans un ordre croissant ou décroissant.
Simple, n’est-ce pas !? 😃
def monotonic_array(nums):
return (all(nums[i] <= nums[i + 1] for i in range(len(nums) - 1))
or
all(nums[i] >= nums[i + 1] for i in range(len(nums) - 1)))
A = [6, 5, 4, 4]
B = [1,1,1,3,3,4,3,2,4,2]
C = [1,1,2,3,7]
print(monotonic_array(A))
print(monotonic_array(B))
print(monotonic_array(C))
[Output]
True
False
True
Notre fonction ne compte qu’une seule ligne de code 😎. Et bien c’est grâce à la fonction native all() de Python qui renvoie True si tous les éléments de iterable sont vrais (ou s’il est vide).
12. Chemins possibles croissants
Nous voulons afficher plusieurs listes comme des chemins croissants. L’idée est de prendre deux listes A et B, de faire un chemin croissant à partir d’un élément de A et des autres éléments de B. Regardons l’exemple ci-dessous pour comprendre tout ça.A = [9, 1, 23, 4] et B = [10, 20, 7], nous aurons les chemins possibles croissants :[1, 7]
[1, 7, 10]
[1, 7, 10, 20]
[4, 7]
[4, 7, 10]
[4, 7, 10, 20]
[9, 10, 20]
[23]
Le premier élément de la liste affiché vient toujours de A et les autres de B viennent à la suite s’ils sont plus grand que ce premier élément.
def growing_paths(array1, array2):
# Trier les deux listes de façon croissante
array1.sort()
array2.sort()
# Parcourir la première liste
# et comparer chaque élément avec ceux de la seconde liste
for number in array1:
# Initialiser notre liste
list_ = [number]
# Si l'élément de la première liste est supérieur au plus grand élément
# de la seconde liste, l'afficher et passer à l'élément suivant de la première liste
if number > array2[-1]:
print(list_)
continue
# Comparer l'élément avec chaque élément de la seconde liste
for i in range(len(array2)):
# Si l'élément de la seconde liste est plus petit que celui de la première
# On passe à l'élément suivant de la seconde liste
if array2[i] < number: continue
# Si l'élément de la seconde liste est plus grand ou égale que celui de la première
# On l'ajoute dans la liste et on l'affiche
else:
list_.append(array2[i])
print(list_)
A, B = [9, 1, 23, 4], [10, 20, 7]
print(growing_paths(A, B))
[Output]
[1, 7]
[1, 7, 10]
[1, 7, 10, 20]
[4, 7]
[4, 7, 10]
[4, 7, 10, 20]
[9, 10, 20]
[23]
13. Déplacement des zéros
Nous allons déplacer tous les zéros à la fin de notre liste tout en conservant l’ordre des autres chiffres (non-zéros). 🤠 Nous allons principalement utiliser les fonctions remove() et append() pour notre opération. Ces fonctions sont très importantes pour manipuler des arrays ou list.
def move_zeroes(nums):
for i in nums:
if 0 in nums:
nums.remove(0) # supprimer le premier zéro de la liste
nums.append(0) # ajouter 0 à la fin de la liste
return nums
array1 = [0, 1, 0, 3, 12]
array2 = [1, 7, 0, 0, 8, 0, 10, 12, 0, 4]
print(move_zeroes(array1))
print(move_zeroes(array2))
[Output]
[1, 3, 12, 0, 0]
[1, 7, 8, 10, 12, 4, 0, 0, 0, 0]
14. Adresse e-mail valide
Rien de mieux pour tester un module Python très utilisé : regex.
En utilisant les expressions régulières, écrire un algorithme qui permet de vérifier si une adresse e-mail est valide ou non. La fonction retournera False si l’e-mail est invalide et l’e-mail entré s’il est valide.
Par exemple, A = prenom.nom@contact.fr est valide et B = 123prenom,nom@contact.org.fr False car invalide selon ces règles suivantes.
from re import match
def is_email(email: str) -> str:
# Écrivons l'expression régulière d'une adresse email selon RFC 5322
email_regex = r"(^[a-zA-Z0-9_.+-]+@[a-zA-Z0-9-]+\.[a-zA-Z0-9-.]+$)"
# Vérifions que notre adresse email respecte ou non l'expression régulière
valid_email = match(email_regex, email)
if valid_email is None:
return False
else:
return valid_email[0]
A = "prenom.nom@contact.fr"
B = "123prenom,nom@contact.org.fr"
print(is_email(A))
print(is_email(B))
[Output]
prenom.nom@contact.fr
False
Si vous avez remarqué, on définit notre fonction en indiquant le type des paramètres et sortie de notre fonction. Oui c’est possible en Python pour ceux qui sont très habitués aux langages typés comme Java par exemple. Pour plus d’infos, suivre ce lien.
15. Combler les trous
Il est fréquent pour les Data Scientists de faire cette opération : remplir les valeurs None par d’autres valeurs grâce à des fonctions de la librairie Pandas. Dans notre cas, on ne travaille pas avec des DataFrames mais des listes.
Comment faire ? 🤔
Un peu de patience, on va dans notre exemple combler les trous avec la valeur qui précède (oui ça ressemble à pandas.DataFrame.ffill()) ou 0 si None se trouve en début de liste.
def fill_blanks(nums):
valid = 0
res = []
for i in nums:
if i is not None:
res.append(i)
valid = i
else:
res.append(valid)
return res
array1 = [1, None, 2, 3, None, None, 5, None]
array2 = [None, 7, 0, 0, 8, None, 10, None, None, None]
print(fill_blanks(array1))
print(fill_blanks(array2))
[Output]
[1, 1, 2, 3, 3, 3, 5, 5]
[0, 7, 0, 0, 8, 8, 10, 10, 10, 10]
16. Tri pair-impair
Trier une liste d’entiers en mettant les nombres pairs triés de façon croissante en début et à la fin les impairs triés de façon décroissante.
Par exemple, on a la liste suivante [93, 24, 38, 1, 96, 87, 100] et en sortie on aura : [24, 38, 96, 100, 93, 87, 1].
def even_odd_sort( numberList):
odd = list() #impair
even = list() #pair
for number in numberList :
if (number % 2) == 0:
#pair
even.append(number)
else:
odd.append(number)
even.sort()
odd.sort(reverse=True)
return even + odd
numbers = [93, 24, 38, 1, 96, 87, 100]
print(even_odd_sort(numbers))
[Output]
[24, 38, 96, 100, 93, 87, 1]
Eh oui, il est possible d’initialiser une liste autre qu’en faisant list_ = [], on vous le montre avec la fonction list().
Vous connaissez déjà .sort() pour trier une liste.
17. Mots correspondants et manquants
Nous avons deux textes et nous désirons connaître leurs différence et intersection.
Différence : liste de mots présents dans un texte et pas dans l’autre.
Intersection : liste de mots présents dans les deux textes.
Ah oui, on fait de la théorie des ensembles avec des listes 😎
def matching_words(sentence1, sentence2):
set1 = set(sentence1.split())
set2 = set(sentence2.split())
return sorted(list(set1^set2)), sorted(list(set1&set2)) # ^ A.symmetric_difference(B), & A.intersection(B)
sentence1 = "le blog 'ledatascientist' est le blog français de référence en data science"
sentence2 = "parmi tous les blogs de data science j'aime 'ledatascientist'"
print(matching_words(sentence1, sentence2))
[Output]
(['blog', 'blogs', 'en', 'est', 'français', "j'aime", 'le', 'les', 'parmi', 'référence', 'tous'], ["'ledatascientist'", 'data', 'de', 'science'])
& dans le code correspond en réalité au caractère ‘&’
18. Médiane
La médiane d’un ensemble de valeurs est une valeur x qui permet de couper l’ensemble des valeurs en deux parties égales : mettant d’un côté une moitié des valeurs, qui sont toutes inférieures ou égales à x et de l’autre côté l’autre moitié des valeurs, qui sont toutes supérieures ou égales à x (s’il y a un nombre impair de valeurs, la valeur centrale sera mise des deux côtés).
def median(list_):
# On garde la longueur de la liste pour éviter de l'appeler à chaque fois
length = len(list_)
if length % 2 == 0:
# Si 'length' est pair
return (list_[int(length/2)] + list_[int((length - 1)/2)])/2
# Sinon
return list_[int(length/2)]
A = [1, 92, 25, 30, 12, 1]
print(median(A))
[Output]
27.5
19. Liste de nombres premiers
Cet exercice est très souvent demandé dans les tests : retourner la liste des nombres premiers strictement inférieurs à un nombre donné.
Ah oui, un nombre premier est un entier naturel qui admet exactement deux diviseurs distincts entiers et positifs.
Voyons ce qu’on peut faire pour cet algorithme.
def prime_numbers(integer):
prime_nums = []
for num in range(integer):
if num > 1: # tous les nombres premiers sont supérieurs strictement à 1
for i in range(2, num):
if (num % i) == 0: # le reste de la division d'un nombre premier par un nombre inférieur à lui est toujours différent de 0
break
else:
prime_nums.append(num)
return prime_nums
print(prime_numbers(10))
print(prime_numbers(21))
[Output]
[2, 3, 5, 7]
[2, 3, 5, 7, 11, 13, 17, 19]
20. Nœuds et profondeur
Attaquons-nous maintenant à la structure des arbres 🌲
Nous avons un arbre binaire de profondeur K et nous voulons supprimer toutes les feuilles qui ont une profondeur inférieure à un k quelconque depuis la racine jusqu’à la feuille.
Illustrons cela donc :
# Créons une classe pour ajouter un noeud dans notre arbre
class newNode():
# Constructeur de la classe
def __init__(self, node):
self.node = node
self.left = self.right = None
# Fonction d'affichage de notre arbre
def print_tree(root):
if root :
print_tree(root.left)
print(root.node, end=" ")
print_tree(root.right)
def remove_leafs(root, k):
# Fonction de suppression des feuilles dont la profondeur est inférieure à k
def remove_leafs_from_short_depth(root, depth, k):
# On vérifie que nous avons vraiment un newNode en entrée sinon on ne retourne rien.
if root == None:
return None
# Nous parcourons notre arbre.
# On descend de la racine aux nœuds descendants
root.left = remove_leafs_from_short_depth(root.left, depth+1, k)
root.right = remove_leafs_from_short_depth(root.right, depth+1, k)
if root.left == None and root.right == None and depth < k:
return None
return root
# Notre fonction finale utilise la fonction remove_leafs_from_short_depth
new_tree = remove_leafs_from_short_depth(root, 1, k)
return new_tree
# expected_binary_tree = {1:[2, 3], 2:[4], 3:[5, 6], 4:[7, 8], 5:[9], 6:[], \
# 7:[10], 8:[], 9:[11, 12], 10:[], 11:[], 12:[]}
# Construisons notre arbre ci-dessus
root = newNode(1)
root.left, root.right = newNode(2), newNode(3)
root.left.left = newNode(4)
root.right.left, root.right.right = newNode(5), newNode(6)
root.left.left.left, root.left.left.right = newNode(7), newNode(8)
root.right.left.right = newNode(9)
root.left.left.left.left = newNode(10)
root.right.left.right.left, root.right.left.right.right = newNode(11), newNode(12)
# Affichons notre arbre avant suppression
print("Notre arbre avant suppression")
print_tree(root)
print()
print('-'*100)
# Supprimons les feuilles de longueur inférieur à 4
new_tree = remove_leafs(root, 4)
# Affichons notre arbre après suppression
print("Nouvel arbre obtenu")
print_tree(new_tree)
[Output]
Notre arbre avant suppression
10 7 4 8 2 1 5 11 9 12 3 6
----------------------------------------------------------------------------------------------------
Nouvel arbre obtenu
10 7 4 8 2 1 5 11 9 12 3
21. Conversion par changements de bits
Essayons de nous mettre à la place de nos machines 🤖
Nous allons travailler cette fois-ci avec des types binaires. Nous voulons connaître le nombre de bits dans la représentation binaire d’un entier n qu’il faut changer pour obtenir l’entier m. Par exemple, nous avons :
def count_flipped(a, b):
xor = a^b # OU Exclusif
xor_binary = str(bin(xor)) # Petit tweat pour convertir la valeur en binaire qu'on convertit en string
return xor_binary.count('1') # On compte le nombre de bits à 1
count_flipped(8, 6)
[Output]
3
En effet, l’opérateur XOR retourne vrai (1) uniquement lorsque les valeurs des deux opérandes A et B sont différentes. Cet opérateur est donc adapté pour déterminer tout changement de bits.
22. Plus longue séquence commune
Nous voulons détecter pour deux mots donnés, la plus longue séquence qu’ils ont en commun. Par exemple, nous avons les mots A = 'ledatascientist', B = dicodata, C = datascience et D = okihqgahye.
def lcs(word1, word2):
i = 0
so_far = ""
current = ""
# On parcours la première chaine de caractères
while i < len(word1):
# Si le i-ème caractère est dans 'word2' ...
if word1[i] in word2:
current = word1[i]
# ... on teste qu'avec les caractères qui suivent,
# le ils forment une chaine qui apparait aussi dans word2
for j in range(i+1, len(word1)):
if word1[i:j] in word2:
current = word1[i:j]
else:
# Quand on atteind un caractère qui, avec les caractères
# précédents ne forment pas une chaine qui est dans word2,
# on continue d'itérer sur word1 à partir de ce caractère
i = j - 1
break
# Si la dernière chaine detectée est plus longue que la plus
# longue chaine qui était detectée jusque là, on actualise
# cette dernière
if len(current)> len(so_far):
so_far = current
if len(so_far) > len(word1)-i:
# Si la séquence la plus longue trouvée jusque là est plus
# longue que la suite de word1, on peut sortir de la boucle
# ça ne sert à rien de continuer vu que 'so_far' est
# forcément la plus grande chaine en commun
break
else:
# Si le i-ème caractère de 'word1' n'est pas dans 'word2'
# on passe au suivant
i += 1
return so_far
A = 'ledatascientist'; B = 'dicodata'; C = 'datascience'; D = 'okihqgahye'
print(lcs(A,C))
print(lcs(A,B))
print(lcs(A,D))
[Output]
datascien
data
e
Cool n’est-ce pas !? 😎
23. Grand commun diviseur
Nous allons résoudre une équation : ax + by = gcd(a, b) où x, y et gcd(a, b) (grand commun diviseur des entiers a et b) sont les inconnus de l’équation.
Notre fonction prend en entrée les entiers a et b et notre fonction doit retourner : gcd(a, b), x et y. Par exemple, nous avons :a = 35 et b = 25 donc ax + by = gcd(a, b) donne :gcd(a, b) = 5, x = 1 et y = -2
def gcd_extended(a, b):
"""
Soit ax + by = gcd(a, b) avec a = 45 et b = 60.
Pour calculer le gcd(a, b), on décompose a et b avec des nombres premiers :
a = 3 * 3 * 5
b = 2 * 2 * 3 * 5
Ainsi, on aura :
gcd(a, b) = 3 * 5 = 15
x = -1
y = 1
"""
# Si l'un des deux entiers est nul, on retourne la valeur de l'autre, 0 et 1
if a == 0:
return b, 0, 1 # x = 0 et y = 1
# On calcule par récursivité le gcd et les variables permettant de trouver x et y
gcd, x1, y1 = gcd_extended(b%a, a)
# On reconstitue x et y avec les valeurs produites par récursivité
x = y1 - (b//a) * x1
y = x1
# On retourne enfin les solutions de notre équation ax + by = gcd(a, b)
return gcd, x, y
print(gcd_extended(45, 60))
[Output]
(15, -1, 1)
Je pense que tu es habitué maintenant à l’utilisation des fonctions récursives 😄.
Pour info, il existe une fonction Python pour calculer le GCD de deux entiers : math.gcd().
24. Tri par insertion
Si tu sais comment utiliser la fonction .sort() des listes, c’est très bien. Mais il existe plusieurs manières d’implémenter soit-même une fonction de tri et elle peut être plus ou moins performante que l’usuelle .sort().
Nous allons trier une liste de nombres de façon croissante ou décroissante en insérant les nombres les uns à la suite des autres.
Voyons cela par un exemple.
def insertionSort(arr , asc=True):
for i in range(1, len(arr)):
key = arr[i]
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
if not asc:
arr.reverse()
arr = [12, 11, 13, 5, 6]
insertionSort(arr, False)
for i in range(len(arr)):
print ("% d" % arr[i])
[Output]
13
12
11
6
5
Dans cet exemple, on retourne une liste décroissante grâce au paramètre asc qui est à False ; évidemment lorsqu’il est à True, la liste retournée est triée croissante.
25. Tri à bulle
Le tri à bulle est l’algorithme de tri le plus simple à implémenter mais également le plus coûteux en termes de temps d’exécution. Il consiste à comparer les éléments consécutifs de la liste et les ordonner à chaque fois.
def tri_bulle(list_):
length = len(list_)
for i in range(length-1, 0, -1):
for j in range(0,i):
if list_[j+1] < list_[j]:
list_[j+1], list_[j] = list_[j], list_[j+1]
return list_
tri_bulle([1,6,9,5,7,2,3,0,8,29,1,100])
[Output]
[0, 1, 1, 2, 3, 5, 6, 7, 8, 9, 29, 100]
Conclusion
Dans cet article, nous avons pris connaissance de 25 algorithmes à résoudre avant tout test technique. Évidemment qu’il existe plusieurs autres algorithmes demandés dans ces tests mais ceux-là (ou leurs variantes) sont les plus demandés dans les FAANG interviews.
Il existe plusieurs autres manières de résoudre ces différents algorithmes vus, donc n’hésitez pas à laisser des commentaires pour nous partager vos solutions, et pourquoi pas d’autres algorithmes que vous avez rencontrés pendant des tests techniques.
Sources et ressources complémentaires
[1] Towards Data Science, 10 Algorithms To Solve Before your Python Coding Interview, https://towardsdatascience.com/10-algorithms-to-solve-before-your-python-coding-interview-feb74fb9bc27
[2] GeeksforGeeks, Top 10 algorithms in Interview Questions, https://www.geeksforgeeks.org/top-10-algorithms-in-interview-questions/
[3] Wikiwand, Tri rapide, https://www.wikiwand.com/fr/Tri_rapide
[4] Towards Data Science, 30+ Data Science Interview Questions from FAANG Tech Giants, https://towardsdatascience.com/30-data-science-interview-questions-from-faang-tech-giants-1eea134db7c7
[5] Medium, The Best Code Assessment Platforms for Live Interviews in 2020, https://medium.com/coderbyte/the-best-platforms-for-live-coding-interviews-in-2020-19fb3661df84
Pour la question 2
Il faudrait peut être trier la liste avant ça ferait passer en O(n^2)
exercice numero2 une solution pour reduire la complexite
from math import sqrt
def is_Pythagorean_triplet(list_):
if len(list_)<3:
return 'pas de triplet pythagoricien'
else:
triplet=[]
list_.sort()
for i in range(len(list_)-1):
for j in range(i+1,len(list_)):
if sqrt(list_[i]**2+list_[j]**2) in list_ and sqrt(list_[i]**2+list_[j]**2)!=list_[i] and sqrt(list_[i]**2+list_[j]**2)!=list_[j]:
triplet.append((list_[i],list_[j],[z for z in list_ if z==sqrt(list_[i]**2+list_[j]**2) ][0]))
return (triplet)
Effectivement Habib, ta solution réduit grandement la complexité.
Merci pour ton aide 😊🎊
Ma version de ce code pour ceux que ça intéresse (c’est le même raisonnement que Habib, c’est juste la mise en forme qui est différente) :
from math import sqrt
def pythagorean_triples(integers_list):
if len(integers_list) < 3:
return "Il faut minimum 3 entiers pour trouver un triplet"
else:
integers_list.sort()
triples = []
n = len(integers_list)
for i in range(n-1):
for j in range(i+1, n):
a = integers_list[i]
b = integers_list[j]
c = sqrt(a**2 + b**2)
if c in integers_list and c!=a and c!=b:
triples.append((a, b, [z for z in integers_list if z==c][0]))
return(triples)
print(pythagorean_triples([0, 3, 6, 1, 2, 4, 5]))
Salut Soufian,
Merci pour ta réponse, Habib et toi êtes effectivement sur la même longueur d’onde.
N’hésitez pas à proposer d’autres exercices que vous avez rencontré en entretien technique que nous n’aurions pas présenté ici 😊
Bonjour, Il me semble qu’il faut effectivement faire un sort de la liste en exercice 2 avant de lancer l’exécution du programme sinon le programme ne prend pas en compte toutes les solutions. Prenons par exemple ce cas de figure [0, 3, 6, 1, 2, 5, 4], sachant que le programme parcours linéairement la liste afin d’affecter les valeurs à a,b,c tel que a**2 + b**2 = c**2. Nous aurons a=3, b=5 et c=5 ce qui ne vérifie pas la condition pour être un triplet alors que si l’on effectue un tri nous aurons alors notre triplet qui vérifie la solution (3,4,5). Bien sur, tous cela n’est vrai que si l’on suppose que l’énoncé cherche toutes les combinaisons possibles dans une liste en entré.
Bonjour Pedro,
Merci pour ton commentaire et ton exemple. Effectivement, le tri est primordial et permet d’avoir en sortie de bons résultats.
En essayant ton code avec ta liste [0, 3, 6, 1, 2, 5, 4], il ne renvoie aucune solution.
Comme je le recommande dans mon commentaire précédent, la proposition d’Habib est meilleure 😊 :
« exercice numero2 une solution pour reduire la complexite
from math import sqrt
def is_Pythagorean_triplet(list_):
if len(list_)<3:
return 'pas de triplet pythagoricien'
else:
triplet=[]
list_.sort()
for i in range(len(list_)-1):
for j in range(i+1,len(list_)):
if sqrt(list_[i]**2+list_[j]**2) in list_ and sqrt(list_[i]**2+list_[j]**2)!=list_[i] and sqrt(list_[i]**2+list_[j]**2)!=list_[j]:
triplet.append((list_[i],list_[j],[z for z in list_ if z==sqrt(list_[i]**2+list_[j]**2) ][0]))
return (triplet)``
Le sort() n’est pas primordial.
Voici une solution qui donne les bons triplets sans se soucier de l’ordre des valeurs:
def is_pythagorean_triplet_v1(list_):
if len(list_) < 3:
triplet = « »
else:
triplet = []
n = len(list_)
for i in range(n-1):
for j in range(i+1, n):
c = sqrt(list_[i]*list_[i] + list_[j]*list_[j])
if c != list_[i] and c != list_[j] and c in list_:
# debug
# print(f'{list_[i]}^2 + {list_[j]}^2 = {int(sqrt(list_[i]*list_[i] + list_[j]*list_[j]))}^2')
triplet.append((int(list_[i]),
int(list_[j]),
int(c)))
return triplet
Bonjour, merci pour cet article 🙂
Dans l’exercice 19 (Nombres premiers), on peut réduire la complexité de plusieurs manières :
– en traitant 2 comme cas à part puis en ne considérant que les entiers impairs dans la boucle externe
– en arrêtant la recherche de diviseur à la partie entière de la racine carrée du nombre à diviser dans la boucle interne
Bonjour Yoav,
Merci pour ton commentaire 😊.
Ta première proposition est géniale, je n’y avais pas pensé (tous les nombres premiers sauf 2 sont impairs) et effectivement pour 2 pas besoin de faire de boucle.
Par contre, pour ta deuxième idée, ce ne serait pas mal si tu nous donnais un petit exemple, histoire que toute la communauté en profite 🤠
pour la question 2 on peut utiliser
from itertools import combinations
list_test = [0, 3, 6, 1, 2, 4, 5]
list_test_carre = [x*x for x in list_test]
for y in combinations(sorted(list_test_carre),3):
if y[0] + y[1] == y[2]:
print(y)
Pour compléter ton code, étant donner que tu retournes les carrés des nombres je te propose de rajouter :
print([int(sqrt(i)) for i in y]) à la place de print(y)
from itertools import combinations
from math import sqrt
def triplet_pythagore(liste):
list_test_carre = [x*x for x in liste]
solution=[]
for y in combinations(sorted(list_test_carre),3):
if y[0] + y[1] == y[2]:
solution.append([int(sqrt(i)) for i in y])
return solution
Pour question 8, je vous propose une autre solution (la solution que vous montrez ne fonctionne pas pour le test string dessous
def inverse_special_char2(words):
words_list = list(words) # Créons une liste des caractères de word
temp_word = []
for word in words_list:
if word.isalnum():
temp_word.append(word)
temp_word.reverse()
index_w = 0
for ind, word in enumerate(words_list):
if word.isalnum():
words_list[ind] = temp_word[index_w]
index_w += 1
inverse_words = ».join(words_list)
return inverse_words
test_words = « Al******@)**@)@)os82? »
Attention aux retours de fonction -> Python est très permissif sur les retours possible mais il faut essayer de rester le plus logique et simple possible:
– Soit on retourne un booléen
– Soit on retourne un nombre (ou -1, ou None si -1 est une valeur possible)
– Soit on retourne un objet (ou None)
– Soit on retourne une liste (d’éléments ou vide) – pareil pour les autres conteneurs (dict, string, set, tuple…)
Bonsoir ,
Merci très interessent ton article.
Je suis entrain de la coder en JAVA.
list_numbers = [3,3,4,4,4,4,8,7,5,9,25]
list_results = []
for num in list_numbers:
for num2 in list_numbers:
if num**2 + num2**2 in list_numbers and num != num2 and (num,num2,num**2+num2**2) not in list_results and (num2,num,num**2+num2**2) not in list_results:
list_results.append((num,num2,num**2+num2**2))
print(list_results)
Merci pour cet article qui stimule nos méninges !
Pour le 8, je propose une autre version (on a tous une façon originale d’aborder les problèmes):
word = « Alo*etui@l)ios82? »
listSpe = []
wordPurge = »
for pos,l in enumerate(word):
if not l.isalnum(): listSpe += [(pos,l)] # liste de caractères spéciaux avec leur position
else: wordPurge += l # mot purgé des caractères spéciaux
wordInv = wordPurge[::-1] # inversion du mot purgé
for pos,l in listSpe:
wordInv = wordInv[:pos] + l + wordInv[pos:] # réintégration des caractères spéciaux
print(wordInv)
Pour le 7, on peut faire:
word = ‘propre’
carUni = [l for l in word if word.count(l) == 1]
print(carUni[0])
Pour le 8, une autre solution:
word = « Alo*etui@l)ios82? »
listSpe = []
wordPurge = »
for pos,l in enumerate(word):
if not l.isalnum(): listSpe += [(pos,l)] # liste de caractères spéciaux avec leur position
else: wordPurge += l # mot purgé des caractères spéciaux
wordInv = wordPurge[::-1] # inversion du mot purgé
for pos,l in listSpe:
wordInv = wordInv[:pos] + l + wordInv[pos:] # réintégration des caractères spéciaux
print(wordInv)
Bonjour,
pour le 8 à mon grand étonnement je me suis retrouvé avec une solution beaucoup plus courte que voici:
——————————————-
import string
def inverse_special_char(s):
# Find special characters along with their index
special = [(i,x) for i,x in enumerate(s) if x in string.punctuation]
# Clean and reverse the string without special characters
rclean = [x for x in s if x not in string.punctuation][::-1]
# Insert the special characters back to their original position
[rclean.insert(i, x) for (i,x) in special]
# Return string
return « ».join(rclean)
——————————————-