Meilleur Moment pour Acheter et Vendre des Actions : Question d’Entretien en Python

Introduction

Dans le domaine des entretiens techniques, la question de l’achat et de la vente d’actions est un classique pour évaluer la compréhension des algorithmes et structures de données. Ce problème requiert non seulement une bonne compréhension des concepts algorithmiques, mais aussi la capacité de proposer des solutions optimisées. L’objectif de cet article est de vous guider à travers la résolution de ce problème populaire, du concept initial à l’implémentation en Python.

Contexte et Définition du Problème

Le problème de base consiste à acheter et vendre des actions afin de maximiser le profit. Le but est de déterminer les meilleurs jours pour effectuer ces transactions sur la base d’une liste de prix donnée pour chaque jour. Cependant, des contraintes typiques s’appliquent : on ne peut vendre qu’après avoir acheté, et l’objectif est d’acheter et vendre une seule fois. Par exemple, avec les prix [7, 1, 5, 3, 6, 4], acheter au prix de 1 et vendre au prix de 6 fournit le profit maximal de 5.

Comprendre le Problème à Travers un Exemple

Pour disséquer ce problème, prenons la liste de prix suivante : [7, 1, 5, 3, 6, 4]. Dans ce cas, l’approche optimale est d’acheter au prix de 1 le deuxième jour et de vendre au prix de 6 le cinquième jour pour un profit de 5.

Concepts Fondamentaux

La clé pour résoudre ce problème réside dans la compréhension des tableaux et des itérations. Il est crucial de repérer les points minimums pour acheter et les points maximums pour vendre. Nous abordons ici des techniques comme la fenêtre glissante pour une optimisation efficace.

Approches pour Résoudre le Problème

Il existe plusieurs manières de résoudre ce problème.

Méthode Naïve ou Bruteforce

Cette approche implique de tester toutes les combinaisons possibles d’achat et de vente pour calculer le profit maximal. Bien que simple à comprendre, elle a une complexité temporelle élevée de O(n²) en raison des boucles imbriquées.

Optimisation par Approche à un Passage (O(n))

En une seule itération du tableau de prix, nous pouvons calculer le profit optimal. Cela se fait en gardant une trace du prix d’achat minimal rencontré et en calculant le profit en tant que différence entre le prix actuel et ce minimum.

Implémentation en Python

Discutons d’une implémentation optimisée en Python.

def maxProfit(prices):
    if not prices:
        return 0

    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

# Exemple d'utilisation
prices = [7, 1, 5, 3, 6, 4]
print(f"Profit maximum : {maxProfit(prices)}")

Explication du Code

• Initialisation : min_price est initialisé à l’infini pour garantir que tout prix rencontré sera plus bas. max_profit est initialisé à 0.
• Parcours du Tableau : À chaque itération, on vérifie si le prix actuel est inférieur au minimum. Si oui, on met à jour min_price.
• Calcul du Profit : Si le profit potentiellement réalisé, price - min_price, dépasse max_profit, nous le mettons à jour.

Complexité Temporelle et Spatiale

• Complexité Temporelle : La solution optimisée a une complexité de O(n), avec n comme nombre de prix.
• Complexité Spatiale : La solution utilise O(1) d’espace supplémentaire, car elle ne dépend pas de structures de données supplémentaires.

Cas Particuliers et Gestion des Exceptions

Certains cas particuliers incluent des séquences de prix décroissants, où aucun profit n’est possible. Dans ces cas, notre fonction retourne un profit de 0.

Tests Unitaires et Validation

Les tests unitaires sont cruciaux pour s’assurer que la solution fonctionne pour tous les scenarios.

import unittest

class TestMaxProfit(unittest.TestCase):
    def test_maxProfit(self):
        self.assertEqual(maxProfit([7, 1, 5, 3, 6, 4]), 5)
        self.assertEqual(maxProfit([7, 6, 4, 3, 1]), 0)
        self.assertEqual(maxProfit([1, 2]), 1)
        self.assertEqual(maxProfit([]), 0)

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

Ces tests valident non seulement le cas général, mais aussi les scénarios où aucun profit n’est possible.

Conseils pour Aborder des Questions d’Entretien Similaires

Lors des entretiens, déconstruire le problème et le reformuler peut être utile. Il est aussi crucial de discuter à voix haute des contraintes et des choix d’implémentation.

• Stratégie : Identifiez rapidement la complexité temporelle optimale que vous pouvez atteindre.
• Optimisation : Même pendant la pression d’un entretien, cherchez des moyens d’optimiser votre approche.
• Ressources : Utilisez des plateformes de codage pratique pour affiner vos compétences.

Conclusion

Dans cet article, nous avons exploré un problème classique des entretiens d’embauche, examiné les différentes approches de résolution et implementé la solution la plus efficace en Python. Cette préparation est essentielle pour bien réussir dans des entrevues axées sur les algorithmes.

Ressources Supplémentaires

• LeetCode: Best Time to Buy and Sell Stock
• Livres recommandés : « Cracking the Coding Interview » de Gayle Laakmann McDowell.
• Plateformes en ligne comme LeetCode et HackerRank pour pratiquer davantage.

Appendice

Code Source Complet

def maxProfit(prices):
    if not prices:
        return 0

    min_price = float('inf')
    max_profit = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_profit:
            max_profit = price - min_price
    return max_profit

FAQ

Q : Que faire si aucune transaction n’est profitable ?
R : La fonction doit retourner un profit de 0, comme vérifié par les tests.

Cet article vous a fourni les outils nécessaires pour aborder efficacement le problème de l’achat et de la vente d’actions en Python, vous préparant ainsi pour vos prochains entretiens techniques.