Maîtriser la Théorie des Graphes pour les Entretiens Techniques : Le Guide Complet

1. Introduction : L'Attente des Graphes chez FAANG

Si vous passez en revue des textes d'algorithmes standard tels que Introduction to Algorithms (CLRS) ou Elements of Programming Interviews (EPI), vous remarquerez rapidement que la théorie des graphes constitue l'un des chapitres les plus vastes et les plus denses sur le plan théorique. Dans le contexte des entretiens de codage dans les entreprises de premier plan, les problèmes de graphes sont fréquemment utilisés comme mécanisme de filtrage critique.

Pourquoi les intervieweurs s'appuient-ils autant sur les graphes ?

• Évaluation Multidimensionnelle : Une seule question sur les graphes évalue votre compréhension des structures de données fondamentales (Tables de Hachage, Files, Piles, Files de Priorité), de la récursivité, du parcours d'arbres (puisque les arbres sont des graphes restreints) et de l'analyse de la complexité espace-temps.
• Applicabilité dans le Monde Réel : Les graphes modélisent nativement les réseaux. Qu'il s'agisse du routage du trafic Internet, du calcul d'amis communs sur une plateforme sociale, de la résolution des dépendances logicielles (comme npm ou pip) ou de la recherche de l'itinéraire le plus rapide sur Google Maps, les graphes constituent la couche de données sous-jacente.
• Reconnaissance de Modèles : Les intervieweurs veulent voir si vous pouvez abstraire un problème verbeux basé sur un scénario en un modèle mathématique standard (sommets et arêtes) et appliquer un modèle connu.

"Le secret pour maîtriser les entretiens sur les graphes est de réaliser qu'il y a rarement de 'nouvelles' questions sur les graphes. Il n'y a que de nouveaux déguisements pour environ six modèles de graphes de base." — Méthodologies de Cracking the Coding Interview (CTCI).

2. Concepts Fondamentaux et Compromis Espace-Temps

Avant de plonger dans des modèles spécifiques, établissons le vocabulaire de base et les compromis critiques dont vous devez discuter avec votre intervieweur lors de la phase de planification.

Représenter le Graphe

Vous disposez généralement de trois manières pour représenter un graphe en mémoire. Choisir la bonne est souvent le premier test.

• Liste d'Adjacence (Le Plus Courant) : Une Table de Hachage (ou un Tableau de Tableaux) où les clés sont les sommets et les valeurs sont des listes de sommets voisins. Temps pour trouver les voisins : O(1). Espace : O(V + E). Utilisez ceci 95 % du temps.
• Matrice d'Adjacence : Un tableau 2D de taille V x V où matrix[i][j] = 1 indique une arête. Temps pour vérifier une arête spécifique : O(1). Espace : O(V^2). N'utilisez ceci que pour les graphes très denses où E ≈ V^2.
• Liste d'Arêtes : Une simple liste de paires de coordonnées [[u, v], [x, y]]. C'est souvent ainsi que l'entrée est fournie, mais c'est terrible pour le parcours. Convertissez toujours ceci en Liste d'Adjacence avant le traitement.

La Règle d'Or du Parcours de Graphe

Contrairement aux arbres, les graphes peuvent avoir des cycles. Si vous ne gardez pas la trace des nœuds que vous avez déjà visités, votre algorithme entrera dans une boucle infinie entraînant une erreur de dépassement de pile (Stack Overflow) ou de dépassement de la limite de temps (TLE). Maintenez toujours un ensemble ou tableau visited (visité).

3. Modèle 1 : Le Graphe Grille Implicite

Souvent, un problème vous donnera une matrice 2D représentant une carte, un labyrinthe ou un plateau. L'astuce est de réaliser que la matrice elle-même est le graphe. Chaque cellule (r, c) est un sommet, et une arête existe entre elle et ses voisins orthogonaux immédiats : (r+1, c), (r-1, c), (r, c+1), (r, c-1).

3.1 Nombre d'Îles (Classique)

Le Problème : Étant donné une grille binaire 2D m x n représentant une carte de '1's (terre) et de '0's (eau), retournez le nombre d'îles. Une île est entourée d'eau et est formée en connectant des terres adjacentes horizontalement ou verticalement.

L'Approche : Nous itérons à travers chaque cellule. Lorsque nous rencontrons un '1', cela indique une nouvelle île. Nous incrémentons notre compteur, puis utilisons DFS pour "couler" l'île (convertir tous les '1's connectés en '0's). Cela garantit que nous ne comptons pas la même île deux fois.

def numIslands(grid):
    if not grid: return 0
    
    rows, cols = len(grid), len(grid[0])
    islands = 0
    
    def dfs(r, c):
        # Cas de base : Hors limites ou eau
        if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
            return
            
        # Couler la terre (marquer comme visité)
        grid[r][c] = '0'
        
        # Explorer les 4 directions
        dfs(r + 1, c)
        dfs(r - 1, c)
        dfs(r, c + 1)
        dfs(r, c - 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                islands += 1
                dfs(r, c)
                
    return islands

Analyse de la Complexité :
- Complexité Temporelle : O(M * N) où M est le nombre de lignes et N le nombre de colonnes. Chaque cellule est visitée au plus un nombre constant de fois.
- Complexité Spatiale : O(M * N) dans le pire des cas (si la grille entière est une île massive, la pile d'appels ira à une profondeur de M*N). Si la modification de l'entrée est interdite, un ensemble visited externe nécessite un espace de O(M * N).

3.2 Nombre d'Îles Distinctes (Variation Avancée)

Le Problème : Similaire au Nombre d'Îles, mais retournez le nombre de formes d'îles uniques. Deux îles sont considérées comme identiques si l'une peut être translatée (non tournée ou réfléchie) pour égaler l'autre.

L'Approche : Nous utilisons toujours DFS pour trouver les îles. Cependant, nous avons besoin d'un moyen de prendre "l'empreinte digitale" ou de sérialiser la forme de l'île. Nous pouvons le faire en enregistrant le chemin de parcours par rapport à la cellule de départ (par exemple, "Droite, Bas, Gauche, Haut"). Nous stockons ces signatures de chaînes dans un Hash Set. La réponse finale est la taille de l'ensemble.

Il s'agit d'un exemple classique de la combinaison d'un modèle de parcours de graphe avec la sérialisation de chaînes pour résoudre une contrainte plus difficile.

4. Modèle 2 : Parcours et Gestion d'État

Ce modèle teste votre capacité brute à traverser un graphe explicite (généralement fourni via une liste d'adjacence ou des références de nœuds) tout en gardant une trace minutieuse de ce qui a été construit ou visité pour gérer les dépendances cycliques de manière native.

4.1 Cloner un Graphe

Le Problème : Étant donné une référence à un nœud dans un graphe connexe non orienté, retournez une copie profonde (clone) du graphe. Chaque nœud contient une valeur (int) et une liste (List[Node]) de ses voisins.

L'Approche : Le principal danger est la récursivité infinie due aux cycles. Nous utilisons une Table de Hachage où la clé est le nœud d'origine et la valeur est le nœud nouvellement cloné. Lors du DFS, si un nœud est déjà dans la table, nous retournons simplement son clone.

class Node:
    def __init__(self, val = 0, neighbors = None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node: return None
    
    # Mappage nœud original -> nœud cloné
    old_to_new = {}
    
    def dfs(node):
        if node in old_to_new:
            return old_to_new[node]
            
        # Créer le clone et l'ajouter à la table AVANT d'itérer les voisins
        copy = Node(node.val)
        old_to_new[node] = copy
        
        for nei in node.neighbors:
            copy.neighbors.append(dfs(nei))
            
        return copy
        
    return dfs(node)

Analyse de la Complexité :
- Complexité Temporelle : O(V + E). Nous visitons chaque sommet et arête exactement une fois.
- Complexité Spatiale : O(V). La table de hachage et la pile de récursivité occupent un espace proportionnel au nombre de sommets.

4.2 Flux d'Eau Pacifique/Atlantique (Multi-Source BFS/DFS)

Le Problème : Étant donné une matrice m x n d'entiers non négatifs représentant la hauteur de chaque cellule unitaire sur un continent, l'océan Pacifique touche les bords gauche et supérieur, et l'océan Atlantique touche les bords droit et inférieur. L'eau peut s'écouler dans 4 directions vers les cellules voisines ayant une hauteur égale ou inférieure. Trouvez toutes les coordonnées de la grille où l'eau peut s'écouler vers les deux océans.

L'Approche : L'approche naïve consiste à exécuter un DFS à partir de chaque cellule individuelle et à vérifier si elle atteint les deux océans (O((M*N)^2)).
L'approche optimale inverse la logique : Commencez depuis les océans et coulez vers le haut. Exécutez un DFS multi-source depuis toutes les cellules touchant le Pacifique, en marquant les cellules accessibles. Faites de même pour l'Atlantique. L'intersection des deux ensembles accessibles est la réponse.

5. Modèle 3 : Détection de Cycles et Tri Topologique

Les Graphes Orientés Acycliques (DAG) sont fréquents dans l'ordonnancement, la compilation et la résolution des dépendances. Chaque fois que des tâches ont des prérequis (A doit se produire avant B), vous avez affaire à un DAG. S'il y a un cycle, les tâches ne peuvent pas être terminées.

5.1 Calendrier des Cours (Algorithme de Kahn)

Le Problème : Il y a numCourses cours étiquetés de 0 à numCourses - 1. On vous donne un tableau prerequisites où [a, b] indique que vous devez d'abord suivre le cours b si vous voulez suivre le cours a. Retournez true si vous pouvez terminer tous les cours.

L'Approche (Algorithme de Kahn) : Nous calculons le degré entrant (in-degree) de chaque nœud (combien de prérequis il a). Nous ajoutons tous les nœuds avec un degré entrant de 0 à une File (Queue). Nous retirons les nœuds de la file, "suivant" logiquement le cours, et diminuons le degré entrant de tous ses voisins. Si le degré entrant d'un voisin tombe à 0, il est ajouté à la file. Si nous traitons tous les nœuds, il n'y a pas de cycle.

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    adj_list = defaultdict(list)
    in_degree = {i: 0 for i in range(numCourses)}
    
    # Construire le graphe et les degrés entrants
    for crs, pre in prerequisites:
        adj_list[pre].append(crs)
        in_degree[crs] += 1
        
    # Trouver tous les cours sans prérequis
    queue = deque([crs for crs in in_degree if in_degree[crs] == 0])
    courses_taken = 0
    
    # Traiter les cours
    while queue:
        current = queue.popleft()
        courses_taken += 1
        
        for neighbor in adj_list[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
                
    return courses_taken == numCourses

5.2 Dictionnaire Alien (Difficile)

Le Problème : Il existe une nouvelle langue extraterrestre qui utilise l'alphabet anglais. Cependant, l'ordre des lettres vous est inconnu. On vous donne une liste de chaînes words du dictionnaire de la langue extraterrestre, où les chaînes dans words sont triées lexicographiquement selon les règles de cette nouvelle langue. Retournez une chaîne des lettres uniques dans la nouvelle langue extraterrestre triées par ordre lexicographique croissant selon les règles de la nouvelle langue.

L'Approche : Ceci est considéré comme l'une des questions d'entretien les plus difficiles, mais se réduit à un Tri Topologique standard.
1. Comparez les mots adjacents pour trouver le premier caractère différent. Cela établit une arête orientée (par exemple, si "wrt" vient avant "wrf", alors 't' -> 'f').
2. Construisez la liste d'adjacence et la carte des degrés entrants pour tous les caractères uniques.
3. Exécutez l'Algorithme de Kahn. S'il y a un cycle (par exemple, a -> b et b -> a), retournez une chaîne vide. Sinon, l'ordre dans lequel les caractères sont retirés de la file est l'alphabet alien valide.

6. Modèle 4 : Chemins les Plus Courts (Non Pondérés et Pondérés)

Les problèmes de chemin le plus court sont divisés entièrement selon que les arêtes ont des poids (coûts, distances, temps) ou non. Confondre les algorithmes pour ces deux types est un signal d'alarme immédiat lors d'un entretien.

6.1 Échelle de Mots (BFS)

Le Problème : Étant donné deux mots, beginWord et endWord, et un dictionnaire wordList, retournez le nombre de mots dans la séquence de transformation la plus courte de beginWord à endWord. Chaque paire de mots adjacente doit différer d'exactement une lettre.

L'Approche : Il s'agit de trouver le chemin le plus court dans un graphe non pondéré. Les mots sont des nœuds, et des arêtes existent entre des mots qui diffèrent d'une lettre.

from collections import deque

def ladderLength(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0
        
    queue = deque([(beginWord, 1)])
    
    while queue:
        word, steps = queue.popleft()
        
        if word == endWord:
            return steps
            
        # Essayer de changer chaque caractère
        for i in range(len(word)):
            for char in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + char + word[i+1:]
                
                if next_word in word_set:
                    word_set.remove(next_word) # Marquer comme visité
                    queue.append((next_word, steps + 1))
                    
    return 0

Analyse de la Complexité :
- Complexité Temporelle : O(M^2 * N), où M est la longueur du mot et N est le nombre total de mots. Pour chaque mot retiré de la file, nous générons 26 * M nouveaux mots, et le découpage de chaînes prend un temps O(M).
- Complexité Spatiale : O(M * N) pour stocker les mots dans la file et l'ensemble.

6.2 Temps de Délai Réseau (Algorithme de Dijkstra)

Le Problème : On vous donne un réseau de n nœuds, étiquetés de 1 à n. On vous donne également times, une liste de temps de trajet sous forme d'arêtes orientées times[i] = (ui, vi, wi), où ui est la source, vi est la cible, et wi est le temps qu'il faut pour qu'un signal voyage de la source à la cible. Nous enverrons un signal à partir d'un nœud donné k. Retournez le temps minimum qu'il faut pour que tous les n nœuds reçoivent le signal.

L'Approche : Parce que les arêtes ont des poids (temps) qui sont non négatifs, il s'agit d'une application classique de l'Algorithme de Dijkstra. Nous utilisons un Min-Heap pour toujours traiter le nœud avec la distance connue la plus courte actuelle depuis le nœud de départ.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    edges = defaultdict(list)
    for u, v, w in times:
        edges[u].append((v, w))
        
    min_heap = [(0, k)] # (distance, nœud)
    visited = set()
    t = 0
    
    while min_heap:
        w1, n1 = heapq.heappop(min_heap)
        
        if n1 in visited:
            continue
            
        visited.add(n1)
        t = max(t, w1)
        
        for n2, w2 in edges[n1]:
            if n2 not in visited:
                heapq.heappush(min_heap, (w1 + w2, n2))
                
    return t if len(visited) == n else -1

7. Modèle 5 : Ensembles Disjoints (Union-Find)

La structure de données Union-Find est incroyablement élégante et très appréciée par les intervieweurs chez Google et Amazon. Elle est spécialement conçue pour répondre extrêmement rapidement à une question : "Ces deux nœuds appartiennent-ils à la même composante connexe ?"

7.1 Connexion Redondante

Le Problème : Dans ce problème, un arbre est un graphe non orienté qui est connexe et n'a pas de cycles. On vous donne un graphe qui a commencé comme un arbre avec n nœuds, avec une arête supplémentaire ajoutée. L'arête ajoutée a deux sommets différents choisis de 1 à n, et n'était pas une arête qui existait déjà. Retournez une arête qui peut être supprimée afin que le graphe résultant soit un arbre de n nœuds.

L'Approche : Nous itérons à travers les arêtes données. Pour chaque arête (u, v), nous vérifons si u et v sont déjà dans le même ensemble en utilisant Union-Find. Si c'est le cas, l'ajout de cette arête crée un cycle, cette arête est donc la redondante ! S'ils ne le sont pas, nous les Unissons (Union).

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size + 1))
        self.rank = [1] * (size + 1)
        
    def find(self, n):
        # Compression de chemin
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]
        
    def union(self, n1, n2):
        p1, p2 = self.find(n1), self.find(n2)
        
        if p1 == p2:
            return False # Cycle détecté
            
        # Union par rang
        if self.rank[p1] > self.rank[p2]:
            self.parent[p2] = p1
            self.rank[p1] += self.rank[p2]
        else:
            self.parent[p1] = p2
            self.rank[p2] += self.rank[p1]
        return True

def findRedundantConnection(edges):
    uf = UnionFind(len(edges))
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]

Analyse de la Complexité :
- Complexité Temporelle : O(E * α(V)) où α est la fonction inverse d'Ackermann. En pratique, c'est O(1) par opération, ce qui signifie que le temps global est linéaire par rapport au nombre d'arêtes.
- Complexité Spatiale : O(V) pour stocker les tableaux parent et rank.

8. Stratégie d'Exécution pour l'Entretien de 45 Minutes

Avoir les connaissances techniques n'est que la moitié de la bataille. L'exécution sans faille sous pression nécessite un cadre comportemental strict. Suivez cette séquence lorsqu'on vous donne un problème de graphes :

1. Clarifier les Caractéristiques du Graphe (Minutes 1-5) :
   • Est-il Orienté ou Non Orienté ?
   • Les arêtes sont-elles Pondérées ou Non Pondérées ?
   • Peut-il y avoir des cycles ?
   • Le graphe peut-il être non connexe ? (Crucial pour savoir si vous avez besoin d'une boucle extérieure sur tous les sommets).
2. Énoncer le Modèle (Minutes 5-10) : Dites explicitement à l'intervieweur : "Je vais modéliser cela comme un graphe orienté, non pondéré où les nœuds sont X et les arêtes sont Y. Parce que nous cherchons le chemin le plus court, je vais appliquer la Recherche en Largeur (BFS)."
3. Analyser la Complexité Avant de Coder (Minutes 10-15) : Définissez V et E en fonction des variables du problème. Indiquez la complexité de temps et d'espace de votre solution proposée. Obtenez le signe d'approbation de l'intervieweur avant de toucher le tableau/l'éditeur.
4. Mettre en Œuvre Mécaniquement (Minutes 15-35) : Si vous avez reconnu le modèle, l'implémentation devrait être un réflexe. Écrivez toujours votre ensemble visited en premier pour éviter de l'oublier.
5. Essai à Sec (Minutes 35-45) : Tracez votre code avec un petit exemple. Mettez à jour manuellement vos files et ensembles visités pendant que vous parcourez ligne par ligne. Cela attrape 90 % des erreurs de décalage d'un (off-by-one).

En étudiant ces cinq modèles fondamentaux – Grilles Implicites, Parcours, Tri Topologique, Chemins les Plus Courts et Ensembles Disjoints – vous passez de la tentative de mémorisation de centaines de solutions LeetCode à la simple mise en correspondance de nouveaux problèmes avec des plans architecturaux connus. Bonne chance pour votre entretien !