Renverser une String en Java : une question d’entretien technique

Un de mes collègues aime bien poser la question suivante en entretien technique : « Comment écrire une fonction Java qui renverse une String ». Le sujet est assez simple mais perturbe une bonne partie des candidats. Voici ma réponse…

Pour bien comprendre le sujet, il faut s’imaginer une String :

1
final String s = "abcd";

On veut la passer dans une moulinette, qu’on appellera « reverse » tout simplement, et qui renverra donc « dcba »… Je crois que cela ne nécessite pas plus d’explications.

Pour commencer, on va donc écrire un prototype de moulinette :

1
2
3
4
5
6
7
8
9
10
11
/**
 * Renverse une chaine.
 *
 * @param s
 *            La chaine a renverse.
 * @return la chaine renversee.
 */
public static String reverse(final String s) {

    throw new UnsupportedOperationException("Cette fonction n est pas encore disponible");
}

Pour le moment, la méthode ne fait rien. Avant de la coder, je veux faire des tests. Et je veux faire ça avec une approche TDD et plus spécifiquement 3T :

1
2
3
4
5
6
7
8
9
10
11
12
13
@Test
public void testReversePair() {
   
    // Arrange
    final String s = "abcd";
    final String expected = "dcba";
   
    // Act
    final String result = MyUtilities.reverse(s);
   
    // Assert
    Assert.assertEquals(expected, result);
}

Je lance mon test et je constate qu’il est rouge (i.e. en échec). Ca me renvoie une UOE, ce qui est précisément ce que je voulais à ce stade.

Une analyse rapide me dit que j’ai quatre cas seulement à tester :

  • une String de taille paire ;
  • une String de taille impaire ;
  • une String vide ;
  • une String nulle.

Je prépare donc des tests pour ces différents cas et j’en profite pour factoriser dès que je commence à dupliquer du code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
@Test
public void testReversePair() {

    // Arrange
    final String s = "abcd";
    final String expected = "dcba";

    // Act and Assert
    doTestReverse(s, expected);
}

@Test
public void testReverseImpair() {

    // Arrange
    final String s = "abcde";
    final String expected = "edcba";

    // Act and Assert
    doTestReverse(s, expected);
}

@Test
public void testReverseVide() {

    // Arrange
    final String s = "";
    final String expected = "";

    // Act and Assert
    doTestReverse(s, expected);
}

@Test
public void testReverseNulle() {

    // Arrange
    final String s = null;
    final String expected = null;

    // Act and Assert
    doTestReverse(s, expected);
}

private void doTestReverse(final String s, final String expected) {
    // Act
    final String result = MyUtilities.reverse(s);

    // Assert
    Assert.assertEquals(expected, result);
}

Tout est rouge ? Parfait… On peut attaquer la phase 3 décrite dans la méthode 3T : le code.

Bon je vous le fais simple : on utilise un StringBuilder :

1
2
3
4
public static String reverse(final String s) {

    return new StringBuilder(s).reverse().toString();
}

Ici, j’utilise un StringBuilder et non un StringBuffer car on n’a manifestement pas besoin de synchronisation.

Les trois premiers tests passent maintenant au vert. Il ne reste que le dernier qui lance une NPE. Bon c’est facile, on fait juste un Early Return :

1
2
3
4
5
6
7
8
public static String reverse(final String s) {

    if (s == null) {
        return null;
    }

    return new StringBuilder(s).reverse().toString();
}

Et voilà. C’était facile. J’aime bien passer un peu de temps sur les tests en entretien, histoire de montrer le cheminement. Dès qu’on a 2-3 ans d’expérience, la programmation de cette fonction ne devrait pas poser beaucoup de difficultés…

De nombreux candidats essaient de le programmer à la main. C’est inutile et loin d’être si trivial pour des String très grosses… Si le recruteur insiste, c’est qu’il n’a rien compris à la programmation. Mais bon, pour la forme, voici comme c’est fait dans la classe StringBuilder :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public AbstractStringBuilder reverse() {
    boolean hasSurrogate = false;
    int n = count - 1;
    for (int j = (n - 1) >> 1; j >= 0; --j) {
        char temp = value[j];
        char temp2 = value[n - j];
        if (!hasSurrogate) {
            hasSurrogate = (temp >= Character.MIN_SURROGATE && temp = Character.MIN_SURROGATE && temp2 <= Character.MAX_SURROGATE);
        }
        value[j] = temp2;
        value[n - j] = temp;
    }
    if (hasSurrogate) {
        // Reverse back all valid surrogate pairs
        for (int i = 0; i < count - 1; i++) {
            char c2 = value[i];
            if (Character.isLowSurrogate(c2)) {
                char c1 = value[i + 1];
                if (Character.isHighSurrogate(c1)) {
                    value[i++] = c1;
                    value[i] = c2;
                }
            }
        }
    }
    return this;
}

Ouais je sais : ça pique un peu les yeux, comme quoi ce n’est finalement pas si trivial que ça. Mais en fait, il est fort peu probable que le recruteur qui vous demande ça saura expliquer pourquoi ça ne l’est pas. D’ailleurs, en général, si vous arrivez à pondre une version qui fonctionne tant bien que mal, il sera déjà très content, pour peu que vous sachiez l’expliquer…

Une réflexion au sujet de « Renverser une String en Java : une question d’entretien technique »

  1. Avatar de icexplorericexplorer

    Sinon voici une version qui « fonctionne tant bien que mal » sans prise en compte des caractères spéciaux (ça peut servir au candidat fainéant :p)

    1
    2
    3
    4
    5
    6
    7
    final String chaine = "abc";
    final char[] chaineArray = chaine.toCharArray();
    final StringBuilder s = new StringBuilder();
    for (final char c : chaineArray) {
        s.insert(0, c);
    }
    System.out.println(s.toString());

Laisser un commentaire