Entraînez-vous pour la Piscine de l'École 42

Devenez vraiment doué•e en résolvant un problème de code chaque jour

Aucun spam. Désinscription facile.

La meilleure façon de s'entraîner à coder

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

Nous écrivons des problèmes

Recevez des exercices et des problèmes de programmation posés par des entreprises de premier plan.

Vous les résolvez

Résolvez un exercice de programmation par jour et apprenez à bien coder

Premium

Nous vous envoyons la solution

Vérifiez votre code et améliorez vos connaissances jusqu'à ce que vous décrochiez le job de vos rêves !

Recevez des problèmes de programmation venant des meilleures entreprises du numérique

Exemple de problème pour apprendre à bien coder

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

Ce problème a été posé par

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 :

  • 1, 1, 1, 1
  • 2, 1, 1
  • 1, 2, 1
  • 1, 1, 2
  • 2, 2

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.

  • N = 1: [1]
  • N = 2: [1, 1], [2]
  • N = 3: [1, 2], [1, 1, 1], [2, 1]
  • N = 4: [1, 1, 2], [2, 2], [1, 2, 1], [1, 1, 1, 1], [2, 1, 1]

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).

Témoignages

Eric

Eric +

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 !

Claudio

Olivia +

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 !

Evan

Evan +

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 !

Calvin

Maxime +

J'ai reçu une offre de Netflix grâce à CodingCoding. Je le recommande à tous mes amis à la recherche d'un emploi.

Owen

Allisson +

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 !

Donnie

Kevin +

Après avoir été inscrit pendant seulement 3 mois, j'ai pu recevoir une offre d'ingénieur chez Amazon. Je recommande vivement CodingCoding !

Apprenez à coder. Apprenez vraiment à bien coder.

Devenez vraiment doué•e en résolvant un problème de code chaque jour