Achetez-Vendez Actions : Résolvez cette Question d’Entretien en Python
Introduction
Dans le cadre des entretiens techniques en programmation, il est fréquent de rencontrer des problèmes algorithmiques qui testent à la fois la capacité à concevoir une solution efficace et à la coder. Parmi ces défis, la question « Achetez-Vendez Actions » est particulièrement populaire. Son but est de maximiser le profit à partir d’une série de prix d’actions. Cet article a pour objectif de guider les lecteurs à travers ce problème, en explorant différentes approches de résolution en Python, et en fournissant des conseils pour s’y préparer lors d’un entretien.
Comprendre le Problème « Achetez-Vendez Actions »
1. Qu’est-ce que le problème Achetez-Vendez Actions ?
Le problème « Achetez-Vendez Actions » peut être défini de la manière suivante : étant donné un tableau représentant les prix d’une action pour chaque jour, déterminer quand acheter et quand vendre l’action pour obtenir le profit maximum. Vous ne pouvez acheter qu’une seule fois et vendre une seule fois.
Ce problème prend souvent place dans le contexte des entretiens techniques pour évaluer la capacité d’un candidat à appliquer des concepts algorithmiques dans le cadre d’une optimisation.
2. Représentation des données
Pour résoudre ce problème, les données sont généralement représentées par une liste de prix où chaque élément correspond au prix de l’action à un jour donné. Le défi consiste à identifier la paire de jours (achat et vente) qui permettra d’atteindre le profit maximum.
Approches de Résolution
1. Méthode Brute
La méthode force brute explore toutes les paires possibles de jours pour calculer le profit. Cela consiste à :
- Itérer sur chaque prix d’achat potentiel.
- Pour chaque prix d’achat, itérer sur chaque prix de vente possible ultérieur.
- Calculer le profit pour chaque paire (achat, vente) et conserver le maximum trouvé.
Avantages et Inconvénients
- Avantages : Simple à implémenter et facile à comprendre.
- Inconvénients : La complexité temporelle est O(n²), ce qui peut être prohibitif pour de grands ensembles de données.
2. Solution Optimisée avec une Approche Dynamique
La méthode optimisée réduit la complexité temporelle à O(n) en parcourant la liste une seule fois, tout en gardant en mémoire le plus bas prix d’achat trouvé :
- Maintenir une variable pour le prix d’achat minimum observé.
- Mettre à jour continuellement le profit maximum possible basé sur le prix actuel et le prix minimum.
Implémentation pas à pas en Python
Voici comment implémenter cette solution :
def max_profit(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
Implémentation en Python
1. Exemple de Code pour la Méthode Optimisée
L’exemple de code ci-dessus illustre une solution élégante et efficace pour calculer le profit maximum. Passons en revue les étapes importantes :
- Initialisez
min_price
à l’infini (ou un nombre très élevé) pour garantir qu’il sera remplacé par n’importe quel prix actual. - Parcourez chaque prix, en mettant à jour
min_price
si un prix inférieur est trouvé. - Calculez le profit potentiel en soustrayant
min_price
du prix actuel, et mettez à jourmax_profit
si ce profit est supérieur à n’importe quel précédent profit observé.
2. Tests Unitaires
Utiliser des tests unitaires pour valider l’implémentation est essentiel. Voici comment configurer un simple test avec unittest
:
import unittest
class TestMaxProfit(unittest.TestCase):
def test_cases(self):
self.assertEqual(max_profit([7, 1, 5, 3, 6, 4]), 5) # Acheter à 1, vendre à 6
self.assertEqual(max_profit([7, 6, 4, 3, 1]), 0) # Aucun profit possible
self.assertEqual(max_profit([1, 2, 3, 4, 5]), 4) # Acheter à 1, vendre à 5
self.assertEqual(max_profit([3, 3, 5, 0, 0, 3, 1, 4]), 4) # Acheter à 0, vendre à 4
if __name__ == '__main__':
unittest.main()
Performances et Optimisations
Avec une complexité temporelle de O(n), l’algorithme optimisé est très efficace pour une grande liste de prix. Cependant, lors de simulations ou applications réelles, d’autres facteurs comme les frais de transaction ou les restrictions de temps pourraient affecter les décisions.
Conseils pour l’Entretien Technique
Dans un entretien :
- Expliquez votre raisonnement : Détaillez chaque étape de votre approche, depuis l’analyse brute jusqu’à l’optimisation.
- Communiquez efficacement : Assurez-vous que l’interviewer comprenne bien votre démarche et vos choix.
- Testez vos solutions : Utilisez des exemples simples pour illustrer le fonctionnement de votre algorithme.
Conclusion
Nous avons abordé la résolution du problème « Achetez-Vendez Actions » en Python en passant d’une approche basique à une solution optimisée. En pratiquant ce problème et d’autres variantes, vous développerez votre capacité à appliquer ces concepts dans des situations réelles et lors d’entretiens.
Ressources Supplémentaires
- Cracking the Coding Interview
- Le site de LeetCode pour des problèmes similaires
- Blog d’algorithmes et de structures de données
Résumé
Cet article a permis de démystifier le problème « Achetez-Vendez Actions », en proposant une approche résolument pratique. J’encourage les lecteurs à continuer à s’exercer et à renforcer leurs compétences en algorithmique, précieuses en entretiens techniques et au-delà.