Cette leçon a été traduite automatiquement en français et n'a pas encore été relue par une personne. Si quelque chose vous semble étrange, la version anglaise fait foi.
Voici un secret que les meilleurs coachs d'entretien ne vous factureront pas 500 $ pour l'apprendre : environ 90 % des problèmes d'entretien de codage tournent autour de seulement sept structures de données. Si vous comprenez profondément quand et pourquoi atteindre chacun d’eux, vous avez déjà gagné la moitié de la bataille. L’autre moitié est la pratique – mais sans les bons modèles mentaux, la pratique n’est qu’une simple mémorisation. Cette leçon vous donne la carte pour que chaque problème que vous rencontrez ressemble à un territoire familier.
Chaque entretien technique puise dans le même puits. Voici les structures que vous rencontrerez, classées par fréquence :
| Structure des données | Fréquence des entretiens | Opérations de base | Quand les enquêteurs s'y attendent | |---|---|---|---| | Tableaux / Chaînes | ★★★★★ | Accéder à O(1), rechercher O(n), insérer O(n) | Presque tous les problèmes commencent ici | | Cartes/ensembles de hachage | ★★★★★ | Insérer O(1), Rechercher O(1), Supprimer O(1) | "Optimisez cela de O(n²) à O(n)" | | Listes liées | ★★★★☆ | Insérer O(1), Supprimer O(1), Accéder O(n) | Manipulation du pointeur, détection de cycle | | ** Piles et files d'attente ** | ★★★★☆ | Push/Pop O(1), Mise en file d'attente/Suppression de la file d'attente O(1) | Analyse, BFS, opérations d'annulation | | Arbres (binaire, BST) | ★★★★☆ | Rechercher O (log n), Insérer O (log n) | Données hiérarchiques, opérations triées | | Graphiques | ★★★☆☆ | Dépend de la représentation | Relations, chemins, connectivité | | Des tas | ★★★☆☆ | Insérer O (log n), Extraire-min O (log n) | "Trouver le k le plus grand/le plus petit" |
Les tableaux sont le point de départ de presque tous les problèmes d’entretien. L'idée clé est que la plupart des problèmes liés aux tableaux ne concernent pas vraiment les tableaux, mais plutôt la reconnaissance de modèles tels que deux pointeurs, une fenêtre coulissante ou des sommes de préfixes.
# Two Sum — the most classic interview problem
# "Given an array and target, find two numbers that add to target"
def two_sum(nums, target):
seen = {} # Hash map to store complement
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# Time: O(n), Space: O(n) — trading space for time
Connectez-vous pour rejoindre la discussion
Remarquez que même ce problème de « tableau » est en réalité un problème de carte de hachage. Ce modèle se répète constamment : la force brute utilise des boucles imbriquées sur un tableau et la solution optimale introduit une carte de hachage.
Si vous êtes bloqué sur un problème et que la force brute est O(n²), demandez-vous : « Une carte de hachage peut-elle réduire cela à O(n) ? La réponse est oui, étonnamment souvent.
Les cartes de hachage brillent lorsque vous avez besoin de :
// Group Anagrams — a classic hash map problem
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}
Les problèmes de liste chaînée testent votre capacité à manipuler des pointeurs sans perdre la trace des nœuds. Les trois techniques dont vous avez besoin sont :
# Detect a cycle in a linked list (Floyd's Algorithm)
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Les piles (LIFO) et les files d'attente (FIFO) sont des structures plus simples, mais elles débloquent des catégories entières de problèmes :
# Valid Parentheses — classic stack problem
def is_valid(s: str) -> bool:
stack = []
matching = {')': '(', '}': '{', ']': '['}
for char in s:
if char in matching:
if not stack or stack[-1] != matching[char]:
return False
stack.pop()
else:
stack.append(char)
return len(stack) == 0
Les problèmes d'arbre impliquent généralement la récursivité et l'un des trois ordres de parcours (dans l'ordre, pré-ordre, post-ordre). Le modèle mental à développer est le suivant : « De quoi ai-je besoin du sous-arbre de gauche, du sous-arbre de droite, et comment puis-je les combiner au niveau du nœud actuel ? »
# Maximum depth of a binary tree — the template for tree recursion
def max_depth(root):
if not root:
return 0
left_depth = max_depth(root.left)
right_depth = max_depth(root.right)
return 1 + max(left_depth, right_depth)
Les problèmes BST (Binary Search Tree) ajoutent une propriété cruciale : le parcours dans l'ordre produit des éléments triés. Si vous voyez « trié » et « arbre » dans le même problème, pensez immédiatement à BST.
Les problèmes de graphiques semblent intimidants, mais la plupart se réduisent à BFS ou DFS une fois que vous avez construit la liste de contiguïté. Les compétences clés sont :
# BFS shortest path in an unweighted graph
from collections import deque
def shortest_path(graph, start, end):
queue = deque([(start, 0)])
visited = {start}
while queue:
node, distance = queue.popleft()
if node == end:
return distance
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append((neighbour, distance + 1))
return -1 # Not reachable
Chaque fois qu'un problème dit "trouver les K les plus grands", "les K les plus proches" ou "fusionner les K listes triées", un tas (file d'attente prioritaire) est presque certainement la réponse. En Python, heapq fournit un min-heap ; pour un tas maximum, annulez les valeurs.
import heapq
# Find the K largest elements in an array
def k_largest(nums, k):
return heapq.nlargest(k, nums) # Uses a min-heap of size k internally
Vous devez trouver la médiane d'un flux de nombres en O(log n) par insertion. Quelle combinaison de structures de données est la plus appropriée ?
| Structure | Accès | Rechercher | Insérer | Supprimer | Espace | |---|---|---|---|---|---| | Tableau | O(1) | O(n) | O(n) | O(n) | O(n) | | Carte de hachage | — | O(1)* | O(1)* | O(1)* | O(n) | | Liste liée | O(n) | O(n) | O(1) | O(1) | O(n) | | Pile/File d'attente | O(n) | O(n) | O(1) | O(1) | O(n) | | BST (équilibré) | O(logn) | O(logn) | O(logn) | O(logn) | O(n) | | Tas | — | O(n) | O(logn) | O(logn) | O(n) |
* Cas moyen ; le pire des cas est O(n) en raison de collisions de hachage.
Développez cette liste de contrôle mentale lors de la lecture d’un problème :