Test Algorithmique

Discussion dans 'Travail, jobs' créé par freedumz, 9 Juillet 2014.

  1. Offline
    freedumz Chasseur de castors
    Salut tout le monde,
    Ce mercredi, je dois me presenter dans une boite pour faire un test algorithmique, auriez vous des exemples de ces tests, car je regarde sur le net, c'est un peu tout et n'importe quoi
    Si vous avez donc des exemples, je suis preneur
    Merci d'avance :)
    Ps: en allant à la bibliotheque, je suis tombé sur le bouquin: Cracking the code interview, je vais le lire pour voir ce qu'il faut mais dedans, il reprend 150 algorithmes généralement demandés en entretien
    freedumz, 9 Juillet 2014
    #1
  2. Offline
    jacko07 Elite
    salut,

    j'ai déjà eu lors d'entretien :
    - un programme qui doit dire si un mot est un palindrome
    - parcourir un tableau et le trier
    - trouver des nombres premiers ou autres entre 0 et 100
    - Faire une calculatrice RPN (test chez openERP)

    J'aimerai lire Cracking the code interview un de ces 4 car il est dans le top de Amazon.
    jacko07, 9 Juillet 2014
    #2
  3. Offline
    freedumz Chasseur de castors
    Okay merci donc ça reste faisable, enfin je vais me préparer, pas envie de me planter (après 1 an et demi sans faire de progra, il faut réactiver les compétences :D)
    freedumz, 9 Juillet 2014
    #3
  4. Offline
    Skarbone I would rather be snowboarding
    Code:
        String str = "un rock cornu";
        boolean ok = true;
        
        str=str.replace(" ","");
    
            for(int i=0;i<str.length()-1;i++){
                if( str.charAt(i) != str.charAt(str.length()-1-i)){
                    ok=false;
                }      
            }
            
            if(ok){
                System.out.println("palyndrome  ");
            }else{
                   System.out.println("pas un palydrome");
            }
        }
       
    
    ouiii :cool:.
    Skarbone, 9 Juillet 2014
    #4
    rtrmhl et fraggahh aiment ça.
  5. Offline
    Esta Boy's dream
    :gne:
    Esta, 9 Juillet 2014
    #5
  6. Offline
    Aqua Elite
    Code:
    public static bool isPalindrome(string s_) { return Enumerable.Range(0, s_.Replace(" ","").ToLowerInvariant().Length/2).Select(i => s_[i] == s_[s_.Length - i - 1]).All(b => b);
    }
    :cool:
    Aqua, 9 Juillet 2014
    #6
  7. Offline
    Skarbone I would rather be snowboarding
    http://stackoverflow.com/questions/5080593/linq-check-whether-a-string-is-palindrome-or-not

    C'est mal de copier :D. Ca passera pas dans un entretient :D

    note que dans ma "solution" pour un palyndrome, je pourrais arrêter de checker a la moitié du string. Si le premier char = le dernier... Alors le dernier est forcément égal au premier :D

    ?
    Skarbone, 9 Juillet 2014
    #7
  8. Offline
    jacko07 Elite
    Tricheurs, on demande de l'algo ! Pas d'utilisation de méthode propre au langage tel que charAt() ou autre ;)
    jacko07, 9 Juillet 2014
    #8
  9. Offline
    Dieu Bisounours a.k.a FFS
    Je ne capte tellement rien. Bonne chance @freedumz
    Dieu Bisounours, 9 Juillet 2014
    #9
    freedumz aime ça.
  10. Offline
    Skarbone I would rather be snowboarding
    oui moi. c est du java. Jme rappelle plus de mes cours mais a priori on peut remplacer ca par chaine[j] ou un truc du genre. donc ca a la meme forme ^:baille:
    Skarbone, 9 Juillet 2014
    #10
  11. Offline
    freedumz Chasseur de castors
    D'autres exemples? car j'ai parcouru le bouquin cracking the code, et les algo proposée me semble vraiment pas adapté au marché du travail européen

    J'ai également appris que j'allais devoir passé un test écrit en anglais, mais là c'est vaste comme truc, vous n'auriez pas également des exemples :D?
    freedumz, 12 Juillet 2014
    #11
  12. Offline
    freedumz Chasseur de castors
    Pour les nombres premiers, je viens de faire un programme, il y a t'il moyen de l'optimiser plus selon vous? merci pour vos conseils ;)

    public class premier {

    public static void main(String[] args) {
    for (int i=2; i<100; i++){
    boolean temoin=true;
    for (int j=2;j<i/2 && temoin;j++){
    if(i%j==0){
    temoin=false;
    }



    }
    if(temoin){
    System.out.println(i);
    }
    }


    }
    }
    freedumz, 14 Juillet 2014
    #12
  13. Offline
    MacEugene POUICbuster

    Bien sûr, c'est atroce comme algorithme. Cherche sur le net "Generating Primes", tu trouveras par exemple celui-ci: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
    C'est pas le plus rapide mais il est facile à comprendre et implémenter.
    MacEugene, 14 Juillet 2014
    #13
    Sim_ aime ça.
  14. Offline
    mderie Elite
    Vecu : inverser une string, fusion de deux liste triees
    Autre : fibonacci, ...

    Bonne m*

    NB : mais est-ce encore la vrai vie ?-)
    mderie, 14 Juillet 2014
    #14
  15. Offline
    Skarbone I would rather be snowboarding
    Un chiffre pair ne peut jamais être premier (sauf 2). Dans ton programme, tu fais le truc simple, "i++".

    C'est peut être "plus optimisé" de faire:

    for (int i = 3; i < 100; i+=2)

    En effet, il ne sert absolument a rien de tester tous les chiffres pair, vu que par définition ils ne peuvent pas être premier. Tu tests 4,6,8,10, etc, sans raison donc. Dans le for que je te donne, on ne teste pas le chiffre 2, qui est le premier nombre premier. Tu peux a la limite ajouter un println de 2 avant le for, pas spécialement joli.

    Ou bien tu peux garder la même boucle for et faire directement:
    if(j%2!=0) et la deuxieme boucle dans ce if. Ainsi, tu ne testera pas les chiffres pairs. (bon, pareil, ca pose problème pour le chiffre 2)

    Dans les deux cas, vu que grâce a ca tu sais que ton chiffre n'est pas pair, tu peu faire un i+=2 dans le deuxieme for aussi. En effet, tu ne vas tester QUE les chiffres impairs (car ils sont les seuls a pouvoir être premier). Hors, les chiffres impairs sont TOUJOURS indivisibles par des chiffres pairs.
    On a donc aucun intéret a essayer de diviser 21 par 2,4,6,8 ou 10, car mathématiquement il est impossible que cela donne un résultat entier.


    Pour le deuxieme for, je trouve qu'un while serait plus adapté. Ca me parait bizarre un for avec deux conditions :)

    Sinon, pour aller encore plus loin dans la deuxieme boucle, tu sais que si le chiffre est indivisibles, disons, par 3, alors il ne pourrait pas être divisibles par des multiples de 3.

    97 n'est PAS divisibles par 3. On est donc CERTAIN qu'il ne pourra jamais être divisé par 6,9,12,15,18,21,24,27,30,33,36,39,42,45,48. Tu peux trouver un moyen de faire sauter ces diviseurs la pour encore optimiser ton truc :)

    (mais je n'ai pas, la, d'idée pour faire ca efficacement)
    Skarbone, 14 Juillet 2014
    #15
  16. Offline
    Skarbone I would rather be snowboarding
    En plus, ton programme nous donne le chiffre 4 comme étant un premier ;)

    Après une petite modification, ton programme a besoin de 591 divisions pour obtenir les 25 nombres premiers inférieur a 100 (enfin, 26 chez toi, vu qu'il donne le 4 :)). Avec une petite modification, ce nombre passe a 291 divisions:


    public class Premier {



    public static void main(String[] args) {

    int nombreTests = 0;
    int nbPremiers = 0;
    System.out.println(2);
    for (int i = 3; i < 100; i+=2) {
    boolean temoin = true;
    for (int j = 3; j < i / 2 && temoin; j+=2) {
    nombreTests++;
    if (i % j == 0) {
    temoin = false;
    }
    }
    if (temoin) {
    System.out.println(i);
    nbPremiers++;
    }
    }
    System.out.println("nombre de tests= "+ nombreTests);
    System.out.println("nombre de premier trouvés = "+ nbPremiers);
    }
    }

    C'est bien sur encore plus probant en cherchant les premiers jusqu'a 1.000.000. Ma petite modification demande 805.838.865 divisions pour trouver 78497 nombres premiers. C'est déja énorme (et ca prends quelques secondes...).

    Avec ton programme, un int n'est même pas suffisant pour compter le nombre de divisions :D. En utilisant un Long, on voit qu'il te faut 9.395.773.457 divisions. Presque 10 fois plus, pour une optimisation de rien du tout :D
    Skarbone, 14 Juillet 2014
    #16
  17. Offline
    MacEugene POUICbuster

    T'as toujours le même time complexity.
    MacEugene, 14 Juillet 2014
    #17
  18. Offline
    Skarbone I would rather be snowboarding
    En faisant if(j%2!=0) avant le deuxieme for, oui effectivement. J'avais pas tout de suite vu sa double condition dans le for, jpensais qu'il testait tous les chiffres sans sortir en cas de division réussie.

    Mais en faisant des incréments de 2 au lieu de 1, on y gagne.
    Skarbone, 14 Juillet 2014
    #18
  19. Offline
    MacEugene POUICbuster

    Certes, mais c'est toujours le même time complexity quand même. :D
    L'algorithme que j'ai donné plus haut est O(n) lui, et beaucoup plus facile à comprendre que ce que tu fais. ;)
    MacEugene, 14 Juillet 2014
    #19
  20. Offline
    Skarbone I would rather be snowboarding
    J'ai pas vraiment de souvenirs sur comment calculer la complexité d'un algorithme je t'avoue :D. Dans tous les cas, le calcul est plus rapide, donc c'est au moins un minimum plus optimisé :D.

    Puis je me doute bien qu'il existe de meilleures méthodes, mais je répond a sa demande: "comment améliorer CE code" :D. La solution que tu donne est effectivement largement plus optimisée, elle correspond d'ailleurs vaguement à ce que je disais:

    (mais je n'avais pas envie de me faire chier a trouver comment coder ca :D)


    Voici un code correspondant a cette méthode, trouvé vite fait sur le net:

    [public class Erato {
    public static void main(String[] args) {
    int N = 1000000;

    // initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
    isPrime = true;
    }

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i*i <= N; i++) {

    // if i is prime, then mark multiples of i as nonprime
    // suffices to consider mutiples i, i+1, ..., N/i
    if (isPrime) {
    for (int j = i; i*j <= N; j++) {
    isPrime[i*j] = false;
    }
    }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
    if (isPrime) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
    }
    }

    C'est clairement mieux :);
    Skarbone, 14 Juillet 2014
    #20