Résoudre l’énigme « Deux Sommes » en Python: Question Courante en Entretien d’Embauche

Introduction

L’énigme « Deux Sommes » est l’un des problèmes les plus fréquemment rencontrés lors des entretiens d’embauche pour des postes de développeurs logiciels. Le problème requiert de trouver deux nombres dans une liste qui, lorsqu’ils sont ajoutés, donnent un total égal à un nombre cible spécifique. Cette énigme est souvent utilisée pour évaluer les compétences algorithmiques fondamentales et la capacité à résoudre des problèmes de manière efficace.

L’importance de maîtriser des algorithmes efficaces pour résoudre de tels problèmes ne peut être surestimée, car elle est cruciale pour réussir dans les évaluations techniques. Dans cet article, nous examinerons le problème « Deux Sommes », différentes approches pour le résoudre, et fournirons une solution Python étape par étape.

Comprendre le problème « Deux Sommes »

Définition du problème :
Étant donné un tableau d’entiers nums et un entier target, trouvez les indices de deux nombres tels que leur somme soit égale à target. Vous pouvez supposer qu’il y aura exactement une seule solution, et vous ne pouvez pas utiliser le même élément deux fois.

Exemple Illustratif :

Entrée : nums = [2, 7, 11, 15], target = 9
Sortie : [0, 1]

Dans l’exemple ci-dessus, la somme de nums[0] et nums[1] est égale à 9.

Analyser les exigences et contraintes

• Entrées : Une liste de nombres entiers et un nombre cible.
• Sorties : Une liste contenant les indices de deux nombres.

Approches pour résoudre le problème

Stratégies de base

La méthode la plus simple consiste à utiliser deux boucles imbriquées pour vérifier la somme de chaque paire de nombres dans le tableau.

def deux_sommes_boucles(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

Complexité temporelle et spatiale :
– Complexité temporelle : O(n²) en raison des deux boucles imbriquées.
– Complexité spatiale : O(1), car nous n’utilisons pas de structure additionnelle significative.

Optimisation avec les structures de données

1. Utilisation d’un dictionnaire pour une recherche plus rapide

L’idée ici est d’utiliser un dictionnaire pour enregistrer les nombres déjà parcourus et vérifier rapidement si la complétion (target - current_number) existe.

Implémentation en Python :

def deux_sommes_dictionnaire(nums, target):
    hash_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_map:
            return [hash_map[complement], i]
        hash_map[num] = i

    return None

Avantages :
– Réduit la complexité temporelle à O(n) grâce à l’utilisation du dictionnaire.

2. Méthode du tri et deux pointeurs

Cette méthode est efficace lorsque la modification de l’ordre des éléments est acceptable. Elle implique de trier d’abord la liste, puis d’utiliser deux pointeurs pour trouver la solution. Cependant, il faut garder une trace des indices d’origine.

Complexité et limites :
– Cette méthode a une complexité temporelle de O(n log n) due au tri, et O(n) pour le parcours avec deux pointeurs.
– Complexité spatiale : pourrait être O(n) pour stocker les indices originaux.

Programmation en Python: Codage de la solution optimale

Étapes de développement en Python

Pour coder la solution optimale, nous devons :

1. Préparer l’environnement de travail pour recevoir les données d’entrée.
2. Développer un script Python pour résoudre le problème « Deux Sommes » efficacement.

1. Initialisation et Entrée utilisateur

Collecter les entrées de l’utilisateur et valider :

def collecter_entrees():
    try:
        nums = list(map(int, input("Entrez la liste de nombres, séparés par des espaces : ").split()))
        target = int(input("Entrez la cible : "))
    except ValueError:
        print("Entrée invalide, veuillez entrer des entiers.")
        return None, None
    return nums, target

2. Implémentation de l’algorithme utilisant le dictionnaire

Implémentons le code optimal avec des commentaires explicatifs :

def deux_sommes_optimal(nums, target):
    # Dictionnaire pour stocker les valeurs déjà vues
    hash_map = {}

    # Parcourir chaque élément avec son index
    for i, num in enumerate(nums):
        # Calculer la complétion
        complement = target - num

        # Vérifier si la complétion est déjà dans le dictionnaire
        if complement in hash_map:
            return [hash_map[complement], i]

        # Enregistrer le numéro actuel avec son index
        hash_map[num] = i

    return None

# Exemple d'utilisation
nums, target = collecter_entrees()
resultat = deux_sommes_optimal(nums, target)
if resultat:
    print(f"Indices des nombres solutions : {resultat}")
else:
    print("Aucune solution n'a été trouvée.")

3. Tester la solution

Utilisez des tests unitaires pour valider la solution :

import unittest

class TestDeuxSommes(unittest.TestCase):
    def test_cas_simple(self):
        self.assertEqual(deux_sommes_optimal([2, 7, 11, 15], 9), [0, 1])

    def test_aucune_solution(self):
        self.assertIsNone(deux_sommes_optimal([1, 2, 3], 7))

    def test_valeurs_negatives(self):
        self.assertEqual(deux_sommes_optimal([-1, -2, -3, -4, -5], -8), [2, 4])

if __name__ == "__main__":
    unittest.main()

Analyse de la performance

Comparons les différentes approches :

L’approche utilisant un dictionnaire est généralement la plus efficace pour cette problématique.

Variantes du problème « Deux Sommes »

« Deux Sommes II – Entrée triée »

Étant donné un tableau trié, utilisez deux pointeurs pour trouver le couple de nombres.

« Somme à Trois »

Extension du problème où vous devez trouver trois nombres dont la somme est égale à un cible précise.

L’algorithme peut être adapté en utilisant des approches similaires en modifiant les indices et les niveaux d’interactions.

Conclusion

Nous avons passé en revue l’énigme « Deux Sommes » et exploré différentes méthodes pour la résoudre. Ce problème constitue un excellent moyen de pratiquer les algorithmes de base en Python, avec une solution optimale utilisant un dictionnaire pour une efficacité accrue. Il est crucial de comprendre ces paradigmes algorithmiques car ils apparaissent souvent dans des variantes lors des entretiens d’embauche.

Ressources supplémentaires

• Cours avancés d’algorithmes : coursera.org
• Plateforme de pratique : LeetCode
• Outils Python : PyCharm, VSCode

Appel à l’action

Je vous encourage à essayer d’autres problèmes d’algorithmes pour aiguiser vos compétences. Partagez vos solutions et vos approches avec la communauté Python pour créer des discussions enrichissantes et apprendre ensemble.