Je pourrais (presque) être recruté chez Google! Retour sur le GLAT #17
Bonjour à tous,
Désolé, mais ce billet risque d’être très geek !
Suite à la lecture du très bon billet sur le blog [Bim Manners] de mon copain/camarade Alex, je me suis
interrogé sur les quelques lignes de code qui trainent au fond de son article.
Ces lignes sont la solution du problème nº 17 du fameux GLAT: Google Labs Aptitude Test. C’est les questions posées par Google lors d’un entretien d’embauche. Je pense que je ferai un billet complet sur celui-ci, car il vaut vraiment le détour !
La question #17 est la suivante :
Issue du document original
GLAT Question 17: “Consider a function which, for a given whole number n, returns the number of ones required when writing out all numbers between 0 and n. For example, f(13)=6. Notice that f(1)=1. What is the next largest n such that f(n)=n?”
Version Française:
GLAT Question 17: ” Considérer une fonction telle qu’à chaque entier n, elle retourne le nombre de ‘1′ nécessaire à l’écriture de tous les nombres compris entre 0 et n. Par exemple: f(13) = 6. On a f(1) = 1 quel est la valeur de n suivante pour que f(n) = n .
Sympas la question non? Ça me rappelle à l’époque (presque lointaine) ou je faisais encore des mathématiques avec toutes les histoires de valeurs propres et d’espace vectoriel :).
Bon f(13) = 6 car 13=>1, 12=>1, 11=>2, 10=>1 et 1 => 1.
Bon la première question que je me suis posé est de savoir si ce nombre existe. Or c’est Google donc de l’informatique et par conséquent pas des maths. Donc, ce nombre tel que f(n) = n existe (CQFD)
ensuite j’ai regardé le script qu’Alex a mis dans son article et j’ai trouvé pas mal d’erreur. Je me suis donc permis de le modifier un peu afin qu’il soit fonctionnel.
Le script PHP suivant donne donc la solution:
<?php
$n=199981-10; // on triche un peu pour accélérer la réponse
$var=”";
$fn=0;
while( $flag ==0 )
{echo “n = “.$n.” | “;
for($i=1; $i <= $n ; $i++)
{$var=(string)$i;
$cpt = substr_count($var,”1″);
$fn+=$cpt;}
if( $fn == $n AND $n != 0 AND $n != 1) $flag = 1;
else
{$flag = 0;
echo “fn = “.$fn.”<br />”;
$n++;
$var=”";
$fn=0;}
}
echo “le nombre tel que f(n) = n avec n!=1 est: “.$n.”<br />”;
?>
Voilà ce code fonctionne, si vous voulais le tester il vous faudra peut être modifier le fichier de configuration d’Apache, car il limite le temps des scripts à 30 secondes. Pour cela, éditer le fichier wamp\bin\apache\apache2.2.8\bin\php.ini et modifier la ligne max_execution_time = 30 ; (remplacer 30 par 120 par exemple).
Ce script n’est pas optimisé afin de faciliter la lecture, en effet on peut supprimer un grand nombre de variables inutiles.
Hop, je reviens sur ce billet après être allé boire un verre avec des amis. Je viens de me rendre compte que le script si dessus est très mauvais. Car pour chaque n il recalcule tout depuis le début ce qui est idiot, car par exemple, pour f(14) il pourrait utiliser le f(13). Demain si j’ai le courage je le réécrirai en entier afin de vraiment optimiser le résultat.
Désolé pour ce mauvais script, mais c’est en prolongement du billet d’Alex.
See u,
Jaguie
[edit: La suite et fin de l'histoire avec la très belle solution de Luc, se trouve ICI . ]
En fait l’idéal ce serait de la faire en C.
j’avoue avoir eu la flemme
ce blog fait partie de mon quotidien !:D
Vraiment Jaguie quelle honte de nous presenter un script que tu qualifie de “très mauvais.”
J’ai bien aimé ta phrase: c’est Google donc de l’informatique et par conséquent pas des maths, c’est brillant
c’est bon je viens de poster un billet. J’ai fait le truc en C
a pluche
merci je vais regarder ça
MOUAAARFFF !!!
zetes nuls les mecs !!
Soluce trouvé en 2 min qui est exécutée en 2 sec et qui prends 2 lignes !!
Je te croyais plus geek que ca jaguie :p
Voila le code php qui n’est pas passé avec els balises…
for($i=3,$j=1;$i!=$j;$i++,$j+=substr_count((string)$i, ‘1′));
echo $j;
méthode bourrin.
classe ta solution …. je m’incline et j’avoue que mon script est tout pourri !