Chapitre 3: Algorithmes & Structures de Données
Ces exercices couvrent les questions classiques d'algorithmes posées en entrevue Java. Chaque solution inclut la complexité temporelle/spatiale et une phrase clé à dire en entrevue.
Exercice 1 — Compteur de fréquence de mots (HashMap)
"Comptez la fréquence de chaque mot dans une chaîne de caractères."
Solution impérative
public Map<String, Integer> wordCount(String text) {
Map<String, Integer> freq = new HashMap<>();
for (String word : text.toLowerCase().split("\\s+")) {
freq.merge(word, 1, Integer::sum);
}
return freq;
}
Solution avec Streams
public Map<String, Long> wordCountStream(String text) {
return Arrays.stream(text.toLowerCase().split("\\s+"))
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
}
Test : "hello world hello java" → {hello=2, world=1, java=1}
"I used merge() for the imperative approach and groupingBy for the stream approach. Both are O(n)."
Exercice 2 — Vérification de parenthèses valides (Stack)
"Vérifiez si une chaîne de parenthèses est valide : (), [], "
Solution
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
for (char c : s.toCharArray()) {
if (pairs.containsValue(c)) {
stack.push(c);
} else if (pairs.containsKey(c)) {
if (stack.isEmpty() || stack.pop() != pairs.get(c)) return false;
}
}
return stack.isEmpty();
}
Tests :
"({[]})" → true
"({[}])" → false
"(((" → false
"" → true
Complexité : O(n) temps, O(n) espace.
"Classic stack problem. O(n) time, O(n) space. I used ArrayDeque instead of the legacy Stack class because it's faster and recommended by the Java documentation."
Exercice 3 — Inverser une liste chaînée
"Inversez une liste chaînée simple (singly linked list)."
Solution
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next; // sauvegarder le suivant
curr.next = prev; // inverser le pointeur
prev = curr; // avancer prev
curr = next; // avancer curr
}
return prev;
}
Visualisation :
Avant : 1 → 2 → 3 → null
Après : 3 → 2 → 1 → null
Complexité : O(n) temps, O(1) espace.
"Three pointers: prev, curr, next. O(n) time, O(1) space. This is a classic that tests pointer manipulation."
Exercice 4 — Recherche binaire (Binary Search)
"Implémentez une recherche binaire sur un tableau trié."
Solution
public int binarySearch(int[] arr, int target) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2; // évite le dépassement d'entier
if (arr[mid] == target) return mid;
else if (arr[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1; // non trouvé
}
Test : [1, 3, 5, 7, 9, 11], target = 7 → retourne 3 (index)
Complexité : O(log n) temps, O(1) espace.
Pourquoi lo + (hi - lo) / 2 au lieu de (lo + hi) / 2 ?
Parce que lo + hi peut dépasser Integer.MAX_VALUE si les deux valeurs sont grandes. C'est un détail que les intervieweurs adorent.
"I use lo + (hi - lo) / 2 instead of (lo + hi) / 2 to avoid integer overflow. Classic O(log n) search on sorted data."
Exercice 5 — Two Sum (Deux nombres qui font un total)
"Trouvez deux nombres dans un tableau dont la somme est égale à une cible."
Solution O(n) avec HashMap
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[] { seen.get(complement), i };
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
Test : [2, 7, 11, 15], target = 9 → retourne [0, 1] (car 2 + 7 = 9)
Complexité : O(n) temps, O(n) espace.
L'idée
Pour chaque nombre x, on cherche si target - x a déjà été vu. La HashMap nous permet de faire cette recherche en O(1).
"Single-pass HashMap solution. For each number, I check if the complement exists in the map. O(n) time instead of the brute-force O(n²)."
Exercice 6 — FizzBuzz (le classique)
"Imprimez les nombres de 1 à n. Pour les multiples de 3 : 'Fizz'. Pour les multiples de 5 : 'Buzz'. Pour les deux : 'FizzBuzz'."
Solution propre
public List<String> fizzBuzz(int n) {
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (i % 15 == 0) result.add("FizzBuzz");
else if (i % 3 == 0) result.add("Fizz");
else if (i % 5 == 0) result.add("Buzz");
else result.add(String.valueOf(i));
}
return result;
}
Solution extensible (si l'intervieweur ajoute des règles)
public List<String> fizzBuzz(int n) {
record Rule(int divisor, String word) {}
List<Rule> rules = List.of(
new Rule(3, "Fizz"),
new Rule(5, "Buzz"),
new Rule(7, "Jazz") // facile à ajouter !
);
List<String> result = new ArrayList<>();
for (int i = 1; i <= n; i++) {
final int num = i;
String s = rules.stream()
.filter(r -> num % r.divisor() == 0)
.map(Rule::word)
.collect(Collectors.joining());
result.add(s.isEmpty() ? String.valueOf(i) : s);
}
return result;
}
"I start with the simple version, but if the interviewer asks for extensibility, I switch to a rule-based approach. Adding a new rule is just one line."
Exercice 7 — Trouver le premier doublon
"Trouvez le premier élément dupliqué dans un tableau."
Solution
public int firstDuplicate(int[] arr) {
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return num;
}
return -1; // pas de doublon
}
Astuce : Set.add() retourne false si l'élément existe déjà — pas besoin de contains() séparé.
Test : [2, 1, 3, 5, 3, 2] → retourne 3 (premier doublon rencontré)
Complexité : O(n) temps, O(n) espace.
Exercice 8 — Vérifier si deux chaînes sont des anagrammes
"Vérifiez si deux chaînes sont des anagrammes."
Solution
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) return false;
int[] count = new int[26];
for (int i = 0; i < s.length(); i++) {
count[s.charAt(i) - 'a']++;
count[t.charAt(i) - 'a']--;
}
for (int c : count) {
if (c != 0) return false;
}
return true;
}
Test : "listen", "silent" → true
Complexité : O(n) temps, O(1) espace (tableau de 26 fixe).
"I use a frequency counter array instead of sorting (O(n log n)). Single pass, O(n) time, O(1) space since the alphabet is fixed."
Résumé des complexités
| Exercice | Temps | Espace | Structure clé |
|---|---|---|---|
| Fréquence de mots | O(n) | O(n) | HashMap |
| Parenthèses valides | O(n) | O(n) | Stack (ArrayDeque) |
| Inverser linked list | O(n) | O(1) | 3 pointeurs |
| Binary Search | O(log n) | O(1) | Division par 2 |
| Two Sum | O(n) | O(n) | HashMap (complément) |
| FizzBuzz | O(n) | O(n) | Modulo |
| Premier doublon | O(n) | O(n) | HashSet |
| Anagramme | O(n) | O(1) | Tableau de fréquences |
⬅️ Chapitre 2: Refactoring | Chapitre 4: Conception REST & Patterns →