Voici la question posée lors d'un entretien :
Vous êtes placé dans une rue qui est très longue. C'est dans cette rue que vous avez garé votre voiture. Vous devez retrouver votre voiture dans cette rue.
Quel est l'algorithme pour trouver votre voiture et quelle est sa complexité. La réponse qu'ils cherchaient était O(nlogn)... mais vous devez prouver pourquoi c'est O(nlogn)... indice : beaucoup de mathématiques impliquées pour arriver à cette réponse.
Je suppose n voici la distance jusqu'à la voiture. Le problème est que vous vous trouvez au milieu d'une rue/ligne infinie et que vous ne savez pas dans quelle direction aller.
Une solution pour cela est d'aller x unités dans une direction, puis 2x dans l'autre, puis 4x en avant, 8x en arrière etc... Et la marche nécessaire est O(n*logn) O(n).
Il s'agit d'un cas particulier de l'application en ligne problème du chemin des vaches . La mesure habituelle est la distance de déplacement dans le pire des cas par rapport à la distance que vous parcourriez si vous saviez où se trouve la voiture ( rapport de compétitivité ). Cela fait 9n, ce qui est en fait O(n), et non O(n log n). Vous effectuez cependant O(log n) changements de direction.
Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.
