Formations — 1 037 leçons en français

Accueil › Coding & algorithmique › Les chaînes de caractères

Les chaînes de caractères — entretien Coding & algorithmique

5 questions posées en entretien sur 3 sujets, avec la bonne réponse et son explication.

Chaînes

Quelle est la complexité de `for (String mot : mots) r += mot;` ?

  1. O(n)
  2. O(n²) : chaque concaténation recopie toute la chaîne accumulée ✓
  3. O(n log n)
  4. O(1)

Pourquoi : `String` est immuable : chaque `+=` alloue une nouvelle chaîne et recopie tout ce qui précède. Le compilateur optimise une concaténation simple, mais ne peut pas sortir l'optimisation d'une boucle. `StringBuilder` ramène l'ensemble en O(n).

Niveau junior

Que renvoie `"a.b.c".split(".")` ?

  1. ["a", "b", "c"]
  2. Un tableau vide : `.` est un métacaractère d'expression régulière ✓
  3. ["a.b.c"]
  4. Une exception

Pourquoi : `split` attend une regex : le point correspond à n'importe quel caractère, tout est consommé comme séparateur et les chaînes vides de fin sont supprimées. Il faut `split("\\.")` ou `Pattern.quote(".")`. Piège qui apparaît aussi en production.

Niveau confirme

Comptage

Pour trouver le premier caractère unique d'une chaîne, pourquoi reparcourir la chaîne plutôt que la Map ?

  1. Parce que c'est plus rapide
  2. Parce qu'une HashMap n'a aucun ordre : seul un parcours de la chaîne donne l'ordre d'apparition ✓
  3. Parce que la Map ne contient pas les caractères uniques
  4. Parce que la Map est immuable

Pourquoi : La HashMap ne garantit aucun ordre d'itération, et il peut varier d'une exécution à l'autre. Alternative : une LinkedHashMap, qui conserve l'ordre d'insertion et permet de parcourir la Map directement.

Niveau confirme

Problèmes classiques

Comment vérifier que `b` est une rotation de `a` ?

  1. `a.contains(b)`
  2. `a.length() == b.length() && (a + a).contains(b)` ✓
  3. Comparer les chaînes inversées
  4. Trier les deux chaînes

Pourquoi : Toute rotation de `a` apparaît dans `a + a`. Le test de longueur est indispensable : sans lui, « bon » passerait pour une rotation de « bonjour ».

Niveau confirme

Que doit renvoyer la compression de « abc » (« aaabb » → « a3b2 ») ?

  1. « a1b1c1 »
  2. « abc » : on renvoie l'original si la compression n'est pas plus courte ✓
  3. Une exception
  4. Une chaîne vide

Pourquoi : C'est la clause que la moitié des candidats oublie, alors qu'elle figure dans l'énoncé — et c'est le premier test que l'examinateur fera passer. On peut même estimer la taille compressée avant de construire, pour éviter le travail inutile.

Niveau confirme

S'entraîner sur ces questions, chronométré →