Question d'entretien d'embauche Shift Technology: Comment vérifie-tu qu'un élem... | Glassdoor.fr

Question d'entretien d'embauche

Entretien de Data Scientist Paris

Comment vérifie-tu qu'un élement se trouve dans une liste

  d'entier ordonnée? Qu'elle est la complexité de votre algorithme ?
Répondre

Réponse de l'entretien

1 réponse

1

Par dichotomie, en faisant une récursion. On selectionne l'entier du milieu de la liste, on le compare à notre élément. Si il est plus grand on lance la récursion sur la premiere partie de la liste sinon sur la plus grande. Ceci jusqu'a ce que notre liste contiennent plus qu'un élement ou qu'on ai une égalité.

La complexité et en 2log(n) puis que, avec cette methode on a 2^n etape si n est la taille de la liste

Candidat à l'entretien, le 22 févr. 2017

Ajouter des réponses ou des commentaires

Pour commenter ceci, se connecter ou s'inscrire