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;` ?
- O(n)
- O(n²) : chaque concaténation recopie toute la chaîne accumulée ✓
- O(n log n)
- 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(".")` ?
- ["a", "b", "c"]
- Un tableau vide : `.` est un métacaractère d'expression régulière ✓
- ["a.b.c"]
- 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 ?
- Parce que c'est plus rapide
- Parce qu'une HashMap n'a aucun ordre : seul un parcours de la chaîne donne l'ordre d'apparition ✓
- Parce que la Map ne contient pas les caractères uniques
- 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` ?
- `a.contains(b)`
- `a.length() == b.length() && (a + a).contains(b)` ✓
- Comparer les chaînes inversées
- 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 ») ?
- « a1b1c1 »
- « abc » : on renvoie l'original si la compression n'est pas plus courte ✓
- Une exception
- 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