Test technique Python : top 25 des algorithmes à résoudre avant son entretien

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.

Exemple de test CodinGame
Exemple de test CodinGame

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'])

&amp; 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). 

\(Médiane(X) = \begin{cases} (X[n/2]+X[(n+1)/2])/2, si \ n \ est \ pair \\ X[(n+1)/2], si \ n \ est \ impair \\ \end{cases} \)
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 = dicodataC = 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

14 commentaires
  1. Bierent dit

    Pour la question 2
    Il faudrait peut être trier la liste avant ça ferait passer en O(n^2)

  2. habib dit

    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)

    1. Alban dit

      Effectivement Habib, ta solution réduit grandement la complexité.
      Merci pour ton aide 😊🎊

    2. Soufian dit

      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]))

      1. Alban dit

        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 😊

  3. Pedro dit

    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é.

    1. Alban dit

      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)``

      1. aguerax9 dit

        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

  4. Yoav dit

    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

    1. Alban dit

      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 🤠

  5. louarradi dit

    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)

    1. Btns dit

      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)

  6. Hahaha dit

    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? »

  7. mikae dit

    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…)

Laisser un commentaire

Votre adresse email ne sera pas publiée.

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Voulez-vous en savoir plus sur la Data Science ?

Inscrivez-vous alors à notre newsletter et vous receverez gratuitement nos derniers articles et actualités ! 
S'INSCRIRE MAINTENANT 
close-link