Test Algorithmique

freedumz

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
 
J

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.
 
1er
OP
freedumz

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)
 
Skarbone

Skarbone

Le méchant Ω
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:.
 
Esta

Esta

Boy's dream
Skarbone a dit:
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:.
Cliquez pour agrandir...
:gne:
 
Aqua

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:
 
Skarbone

Skarbone

Le méchant Ω
Aqua a dit:
Code: 
public bool isPalindrome(string s_)
        {
            s_ = s_.Replace(" ","").ToLowerInvariant();
 
            return    Enumerable.Range(0, s_.Length/2)
                    .Select(i => s_[i] == s_[s_.Length - i - 1])
                    .All(b => b);
        }
:cool:
Cliquez pour agrandir...
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

Sim_ a dit:
:gne:
Cliquez pour agrandir...
?
 
J

jacko07

Elite
Tricheurs, on demande de l'algo ! Pas d'utilisation de méthode propre au langage tel que charAt() ou autre ;)
 
Skarbone

Skarbone

Le méchant Ω
jacko07 a dit:
Tricheurs, on demande de l'algo ! Pas d'utilisation de méthode propre au langage tel que charAt() ou autre ;)
Cliquez pour agrandir...
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:
 
1er
OP
freedumz

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?
 
1er
OP
freedumz

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);
}
}


}
}
 
MacEugene

MacEugene

POUICbuster
freedumz a dit:
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);
}
}


}
}
Cliquez pour agrandir...

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.
 
  • J'aime
Les réactions: Sim_
mderie

mderie

Elite
Vecu : inverser une string, fusion de deux liste triees
Autre : fibonacci, ...

Bonne m*

NB : mais est-ce encore la vrai vie ?-)
 
Skarbone

Skarbone

Le méchant Ω
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

Skarbone

Le méchant Ω
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 :mrgreen:. 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
 
MacEugene

MacEugene

POUICbuster
Skarbone a dit:
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);
}
}
Cliquez pour agrandir...

T'as toujours le même time complexity.
 
Skarbone

Skarbone

Le méchant Ω
MacEugene a dit:
T'as toujours le même time complexity.
Cliquez pour agrandir...
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.
 
MacEugene

MacEugene

POUICbuster
Skarbone a dit:
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.
Cliquez pour agrandir...

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. ;)
 
Skarbone

Skarbone

Le méchant Ω
MacEugene a dit:
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. ;)
Cliquez pour agrandir...
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:

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
Cliquez pour agrandir...
(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 :);
 
Connectez-vous pour réagir !
Haut