CodingCoding te propose chaque jour un nouvel exercice de programmation.
Améliore tes compétences en programmation et fais-toi remarquer.
Reçois des questions techniques posées en entretien par les GAFAM.
Améliore tes compétences en programmation et fais-toi remarquer
Vérifie ton code et améliore tes compétences jusqu'à ce que tu décroche le job de tes rêves !
Il existe un escalier à N marches, et vous pouvez monter 1 ou 2 marches à la fois. Étant donné N, écrivez une fonction qui renvoie le nombre de façons uniques de monter l'escalier. L'ordre des étapes compte.
Par exemple, si N est égal à 4, alors il y a 5 manières uniques :
Et si, au lieu de pouvoir monter 1 ou 2 marches à la fois, vous pouviez monter n'importe quel nombre à partir d'un ensemble d'entiers positifs X ? Par exemple, si X = {1, 3, 5}, vous pouvez monter 1, 3 ou 5 marches à la fois.
Il est toujours bon de commencer par quelques cas de test. Commençons par de petits cas et voyons si nous pouvons trouver une sorte de modèle.
Quelle est la relation ?
Le seul moyen d'arriver à N = 3, est d'abord d'arriver à N = 1, puis de monter de 2 pas, ou d'arriver à N = 2 et de monter d'un pas. Donc f(3) = f(2) + f(1).
Cela vaut-il pour N = 4 ? Oui. Puisque nous ne pouvons arriver à la 4ème étape qu'en allant à la 3ème étape et en remontant d'une unité, ou en allant à la 2ème étape et en remontant de deux. Donc f(4) = f(3) + f(2).
Pour généraliser, f (n) = f (n - 1) + f (n - 2). C'est simplement la Suite de Fibonacci !
def staircase(n):
if n <= 1:
return 1
return staircase(n - 1) + staircase(n - 2)
Bien sûr, c'est vraiment lent (O(2N)) - nous faisons beaucoup de calculs répétés ! Nous pouvons le faire beaucoup plus rapidement en calculant simplement de manière itérative :
def staircase(n):
a, b = 1, 2
for _ in range(n - 1):
a, b = b, a + b
return a
Maintenant, essayons de généraliser ce que nous avons appris pour que cela fonctionne si vous pouvez faire un certain nombre d'étapes à partir de l'ensemble X. Un raisonnement similaire nous dit que si X = {1, 3, 5}, alors notre algorithme devrait être f(n) = f(n - 1) + f(n - 3) + f(n - 5). Si n < 0, alors nous devrions retourner 0 car nous ne pouvons pas partir d'un nombre de pas négatif.
def staircase(n, X):
if n < 0:
return 0
elif n == 0:
return 1
else:
return sum(staircase(n - x, X) for x in X)
C'est encore une fois très lent (O(|X|N)) puisque nous répétons à nouveau les calculs. Nous pouvons utiliser la programmation dynamique pour l'accélérer.
Chaque cache d'entrée [i] contiendra le nombre de façons dont nous pouvons arriver à l'étape i avec l'ensemble X. Ensuite, nous allons construire le tableau à partir de zéro en utilisant la même récurrence que précédemment :
def staircase(n, X):
cache = [0 for _ in range(n + 1)]
cache[0] = 1
for i in range(1, n + 1):
cache[i] += sum(cache[i - x] for x in X if i - x >= 0)
return cache[n]
Cela prend maintenant le temps O(N * |X|) et l'espace O(N).
J'ai reçu une offre de Netflix grâce à CodingCoding. Je le recommande à tous mes amis à la recherche d'un emploi.
J'ai réussi à décrocher un emploi chez Google. J'ai utilisé le service pour environ 100 problèmes et cela a définitivement fait de moi une meilleure développeuse !
Après avoir été inscrit pendant seulement 3 mois, j'ai pu recevoir une offre d'ingénieur chez Amazon. Je recommande vivement CodingCoding !
J'ai décroché mon emploi chez Google après avoir régulièrement résolu des problèmes de la liste de diffusion. J'ai suivi des cours d'algorithmie mais je n'ai jamais pu réussir l'entretien jusqu'à présent !
J'ai accepté l'offre d'Airbnb ! J'ai adoré les questions et elles ont été extrêmement utiles, le tout pour un très bon prix !
Je suis ravi de vous dire que j'ai eu mon entretien avec Uber et que j'ai reçu une offre ! C'est précisément l'offre que je voulais, et cela n'aurait pas été possible sans CodingCoding !
Deviens vraiment doué•e en résolvant un problème de code chaque jour