Réussis tes Tests Forme-toi pour l'École Simplon

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

Code Mieux. Deviens un Expert.

CodingCoding te propose chaque jour un nouvel exercice de programmation.
Améliore tes compétences en programmation et fais-toi remarquer.

Nous envoyons des questions

Reçois des questions techniques posées en entretien par les GAFAM.

Tu les résous

Résous un problème chaque jour et améliore tes compétences en programmation.

Premium

Tu reçois les solutions

Vérifie ton code et améliore tes compétences jusqu'à ce que tu décroche le job de tes rêves !

Reçois des challenges des meilleures entreprises de la tech

Un problème. Une solution

Chaque exercice est basé sur une vraie question posée récemment par les meilleures entreprises de la tech mondiale. Reçois chaque solution dès le lendemain matin et améliore tes compétences.

Voici un exemple d'exercice 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.

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

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 !

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 !

Code Mieux. Deviens un Expert.

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