CodingCoding est un site qui vous propose chaque jour un nouvel exercice de programmation.
Vous pouvez ainsi apprendre à bien coder, progresser dans votre maîtrise du code informatique, tout en vous perfectionnant au fur et à mesure.
Recevez des exercices et des problèmes de programmation posés par des entreprises de premier plan.
Résolvez un exercice de programmation par jour et apprenez à bien coder
Vérifiez votre code et améliorez vos connaissances jusqu'à ce que vous décrochiez le job de vos rêves !
Chaque exercice est basé sur une vraie question de programmation qui a été posée en entretien d'embauche par une entreprise du numérique de premier plan
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.
Solution
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 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 !
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 !
Devenez vraiment doué•e en résolvant un problème de code chaque jour