Questions d'entretien Google

Sur quoi portent les entretiens chez Google

Questions d'entretien courantes chez Google

• Étant donné un tableau d'entiers, retournez les indices des deux nombres tels qu'ils additionnent à une cible spécifique. (Classique two-sum, mais demandez plusieurs solutions et discutez de la complexité.)
  Ce qu'une bonne réponse couvre

  • Hash map (O(n) temps, O(n) espace)
  • Brute force double boucle (O(n^2))
  • Single-pass hash map
  • Gestion des doublons et indices

  Voir un exemple de réponse

  Pour résoudre le problème Two Sum, plusieurs approches existent. La plus naïve est une double boucle qui compare chaque paire, avec une complexité temporelle O(n^2) et spatiale O(1). La solution optimale utilise une table de hachage : on parcourt le tableau une fois, et pour chaque élément, on calcule le complément (cible - élément). Si le complément est dans la table, on retourne les indices. Sinon, on ajoute l'élément courant avec son indice dans la table. Cela donne O(n) en temps et O(n) en espace. Une variante single-pass fait tout en un seul parcours, contrairement à la version two-pass qui ajoute d'abord tous les éléments. Attention aux doublons : si la cible est 6 et qu'il y a deux 3, il faut s'assurer de ne pas utiliser le même élément deux fois. La version single-pass gère cela correctement car on vérifie avant d'insérer.

  def twoSum(nums, target):
      # Single-pass hash map
      seen = {}
      for i, num in enumerate(nums):
          complement = target - num
          if complement in seen:
              return [seen[complement], i]
          seen[num] = i
      return []

• Concevez un raccourcisseur d'URL comme bit.ly – discutez du schéma de base de données, du hachage, de la mise à l'échelle et de la gestion des redirections.
  Ce qu'une bonne réponse couvre

  • Génération d'un identifiant unique (base62, MD5 ou UUID)
  • Table de correspondance (URL longue -> ID, avec index)
  • Gestion des collisions (vérification ou réessai)
  • Redirection HTTP 301 ou 302
  • Mise à l'échelle : partitionnement, cache Redis, load balancer

  Voir un exemple de réponse

  Pour concevoir un raccourcisseur d'URL comme bit.ly, il faut d'abord générer un identifiant unique pour chaque URL longue. On peut utiliser base62 (chiffres + lettres minuscules/majuscules) sur un compteur global ou un hash (MD5 tronqué). La base de données peut être une table avec les colonnes : id (entier auto-incrémenté ou base62), url_longue, date_creation. On peut aussi ajouter un index sur l'URL longue pour éviter les doublons. Lorsqu'un utilisateur crée un raccourci, on vérifie si l'URL existe déjà ; si oui, on retourne l'existant. Pour la redirection, on utilise une redirection HTTP 301 (permanente) pour le cache et le SEO, ou 302 (temporaire) pour l'analytique. Pour la mise à l'échelle, on sharde la base de données par ID ou on utilise un système de cache distribué comme Redis. On peut aussi générer les ID hors ligne avec un service de séquence. Le hachage peut causer des collisions ; on peut les gérer en ajoutant un salt ou en réessayant. Enfin, on utilise des load balancers et du CDN pour distribuer les requêtes.

  import string
  import random
  
  class URLShortener:
      def __init__(self):
          self.url_to_id = {}
          self.id_to_url = {}
          self.chars = string.ascii_letters + string.digits  # base62
      
      def shorten(self, long_url):
          if long_url in self.url_to_id:
              return self.url_to_id[long_url]
          # Générer un ID aléatoire (normalement on utilise un compteur global)
          short_id = ''.join(random.choices(self.chars, k=6))
          self.url_to_id[long_url] = short_id
          self.id_to_url[short_id] = long_url
          return short_id
      
      def redirect(self, short_id):
          return self.id_to_url.get(short_id, None)

• Parlez-moi d'une fois où vous avez eu un conflit avec un collègue. Comment l'avez-vous résolu ? (Comportemental – concentrez-vous sur la collaboration et le résultat.)
  Ce qu'une bonne réponse couvre

  • Méthode STAR : Situation, Tâche, Action, Résultat
  • Conflit technique sur le choix d'une technologie
  • Écoute active et recherche de compromis basé sur des données
  • Résultat positif : solution hybride acceptée par l'équipe

  Voir un exemple de réponse

  Dans mon précédent poste, j'étais en désaccord avec un collègue sur le choix d'une base de données pour un nouveau service. Lui préférait MongoDB pour sa flexibilité, moi je penchais pour PostgreSQL pour la cohérence des transactions. La situation était tendue car le projet avait un calendrier serré. J'ai proposé une réunion pour discuter des avantages et inconvénients de chaque solution, en nous basant sur des critères objectifs : besoin de requêtes complexes, volume de données, et expérience de l'équipe. Après avoir présenté des benchmarks et des cas d'usage, nous avons convenu d'une approche hybride : utiliser PostgreSQL pour les données transactionnelles et MongoDB pour les logs et métriques. Ce compromis a satisfait les deux parties, et le projet a été livré à temps avec les deux bases. Cette expérience m'a appris l'importance de l'écoute et de la recherche de solutions fondées sur des preuves.

• Implémentez une fonction pour sérialiser et désérialiser un arbre binaire. (Test de la gestion des nulls, de la récursion et de l'itération.)
  Ce qu'une bonne réponse couvre

  • Parcours pré-ordre avec marqueurs null
  • Sérialisation en chaîne de caractères ou JSON
  • Récursion pour sérialiser et désérialiser
  • Gestion des arbres asymétriques et des nœuds vides
  • Complexité O(n) en temps et espace

  Voir un exemple de réponse

  Pour sérialiser un arbre binaire, on peut utiliser un parcours pré-ordre (racine, gauche, droite) et représenter les enfants null par un marqueur spécial (par exemple '#'). On sépare les nœuds par des virgules. La désérialisation utilise une file d'attente ou un index global pour reconstruire l'arbre. La version récursive est simple : sérialiser écrit la valeur du nœud, puis appelle récursivement sur les enfants, en écrivant '#' pour null. Désérialiser lit la prochaine valeur ; si c'est '#', retourne None, sinon crée un nœud et remplit ses enfants. On peut aussi utiliser une version itérative avec une pile. La complexité est O(n) en temps et en espace, car on visite chaque nœud une fois et on stocke la chaîne. Attention à gérer les grands arbres : une chaîne linéaire peut être longue, mais c'est acceptable.

  class TreeNode:
      def __init__(self, val=0, left=None, right=None):
          self.val = val
          self.left = left
          self.right = right
  
  def serialize(root):
      """Sérialisation pré-ordre avec '#' pour null."""
      def helper(node):
          if not node:
              vals.append('#')
          else:
              vals.append(str(node.val))
              helper(node.left)
              helper(node.right)
      vals = []
      helper(root)
      return ','.join(vals)
  
  def deserialize(data):
      """Désérialisation à partir d'une chaîne."""
      def helper():
          val = next(vals)
          if val == '#':
              return None
          node = TreeNode(int(val))
          node.left = helper()
          node.right = helper()
          return node
      vals = iter(data.split(','))
      return helper()

• Concevez la fonctionnalité de trafic en temps réel de Google Maps – comment collecteriez-vous les données, mettriez-vous à jour les itinéraires et géreriez-vous des millions d'utilisateurs ?
  Ce qu'une bonne réponse couvre

  • Sources de données : GPS mobiles, capteurs routiers, partenaires
  • Map-matching et filtrage des données brutes
  • Aggrégation et calcul de vitesse moyenne par segment
  • Mise à jour des itinéraires : algorithme de Dijkstra ou A* avec poids dynamiques
  • Scalabilité : partitionnement géographique, cache, traitement asynchrone

  Voir un exemple de réponse

  Pour le trafic en temps réel, Google Maps collecte des données provenant de sources diverses : les mobiles utilisateurs (avec consentement), les capteurs routiers, et des partenaires. Les données brutes (position, vitesse) sont d'abord nettoyées et map-matchées sur le réseau routier. Ensuite, on calcule des vitesses moyennes par segment de route sur des fenêtres de temps (par exemple 5 minutes). Ces vitesses sont stockées dans une base de données clé-valeur (comme Bigtable) avec une clé composée de segment + intervalle de temps. Pour mettre à jour les itinéraires, on utilise des variantes de Dijkstra ou A* avec des poids de segments dynamiques basés sur les vitesses actuelles. Pour des millions d'utilisateurs, on sharde les données par région géographique, on utilise des caches (Redis) pour les routes populaires, et on traite les mises à jour de manière asynchrone avec des files de messages. Le calcul d'itinéraire doit être rapide : on pré-calcule des chemins pour les trajets fréquents. La redirection des requêtes vers le serveur régional approprié est cruciale.

• Expliquez un projet dont vous êtes le plus fier. Quel était votre rôle, les défis et l'impact ? (Comportemental – évaluez la prise en charge et l'influence.)
  Ce qu'une bonne réponse couvre

  • Méthode STAR : Situation, Tâche, Action, Résultat
  • Projet d'optimisation d'un pipeline de données
  • Défis : volumétrie massive, latence, coordination inter-équipe
  • Impact : réduction du temps de traitement de 40%, adoption par l'équipe

  Voir un exemple de réponse

  Le projet dont je suis le plus fier est l'optimisation d'un pipeline de données en temps réel chez mon précédent employeur. Le pipeline traitait des millions d'événements par seconde et souffrait de latences élevées. Mon rôle était de concevoir une architecture plus efficace. Le défi principal était de réduire la latence tout en maintenant la fiabilité, et de coordonner avec les équipes produit et infrastructure. J'ai proposé d'utiliser Apache Kafka pour le streaming, avec une transformation asynchrone plutôt que synchrone. J'ai également implémenté un système de back-pressure pour gérer les pics. Après plusieurs itérations et tests, nous avons réduit la latence de 40%, ce qui a permis à l'équipe produit de déployer des fonctionnalités temps réel. L'impact financier a été significatif. Cette expérience m'a appris l'importance de l'expérimentation et de la collaboration étroite avec les parties prenantes.

• Étant donné un flux d'entiers, trouvez la médiane à tout moment. (Utilisez deux tas – max-heap et min-heap.)
  Ce qu'une bonne réponse couvre

  • Deux tas : max-heap pour la moitié inférieure, min-heap pour la moitié supérieure
  • Équilibrage des tailles : les tas diffèrent au plus de 1
  • Insertion O(log n), médiane O(1)
  • Gestion des cas pairs et impairs

  Voir un exemple de réponse

  Pour trouver la médiane d'un flux d'entiers, on utilise deux tas : un max-heap (ou tas max) pour la moitié inférieure des nombres et un min-heap (tas min) pour la moitié supérieure. On maintient l'invariant que la taille du max-heap est soit égale à celle du min-heap, soit supérieure de 1 (si le nombre total d'éléments est impair). Lors de l'insertion d'un nouveau nombre, on le compare d'abord au sommet du max-heap ; s'il est plus petit, on l'ajoute au max-heap, sinon au min-heap. Ensuite, on rééquilibre si la différence de taille dépasse 1 : on déplace le sommet du tas le plus grand vers l'autre. La médiane est alors le sommet du max-heap si impair, ou la moyenne des deux sommets si pair. L'insertion prend O(log n) et l'obtention de la médiane est O(1). Cette méthode est efficace pour des flux continus. Attention à l'implémentation : en Python, on utilise heapq mais avec négation pour simuler un max-heap.

  import heapq
  
  class MedianFinder:
      def __init__(self):
          self.max_heap = []  # moitié inférieure (inversé pour tas max)
          self.min_heap = []  # moitié supérieure
  
      def addNum(self, num: int) -> None:
          # Ajouter dans le tas approprié
          if not self.max_heap or num <= -self.max_heap[0]:
              heapq.heappush(self.max_heap, -num)
          else:
              heapq.heappush(self.min_heap, num)
          # Rééquilibrer
          if len(self.max_heap) > len(self.min_heap) + 1:
              move = -heapq.heappop(self.max_heap)
              heapq.heappush(self.min_heap, move)
          elif len(self.min_heap) > len(self.max_heap):
              move = heapq.heappop(self.min_heap)
              heapq.heappush(self.max_heap, -move)
  
      def findMedian(self) -> float:
          if len(self.max_heap) > len(self.min_heap):
              return -self.max_heap[0]
          else:
              return (-self.max_heap[0] + self.min_heap[0]) / 2.0

• Pourquoi Google ? Qu'est-ce qui fait de vous un bon candidat pour notre culture ? (Comportemental – reliez les valeurs personnelles à la mission de Google.)
  Ce qu'une bonne réponse couvre

  • Alignement avec la mission de Google : organiser l'information et la rendre accessible
  • Culture d'innovation et de prise de risques calculés
  • Valeur personnelle : résolution de problèmes complexes à grande échelle
  • Exemple concret de contribution possible chez Google

  Voir un exemple de réponse

  Je suis attiré par Google car sa mission 'organiser l'information mondiale et la rendre universellement accessible et utile' résonne profondément avec mes valeurs. J'ai toujours été passionné par la résolution de problèmes à grande échelle, et Google offre des défis techniques uniques, comme le traitement de données massives ou l'IA. De plus, la culture de Google, qui encourage l'innovation, la collaboration et la prise de risques calculés, correspond à mon style de travail. Par exemple, dans mon projet précédent, j'ai proposé une architecture non conventionnelle qui a amélioré les performances de 40% – ce type d'initiative est valorisé chez Google. Je suis convaincu que je peux contribuer à des projets impactants, que ce soit dans la recherche, les infrastructures ou les produits utilisateurs, tout en apprenant des meilleurs ingénieurs du monde. Enfin, je partage les valeurs de diversité et d'inclusion, et j'aimerais participer à des communautés comme Google Developer Groups.

Conseils pour se préparer

• Entraînez-vous à coder sur un tableau blanc ou sans IDE : les entretiens Google exigent souvent d'écrire du code à la main, alors habituez-vous à penser et écrire sur une surface plane.
• Pensez toujours à voix haute : les recruteurs veulent voir votre processus de résolution de problèmes, alors racontez votre approche, les compromis et les étapes de débogage.
• Maîtrisez les structures de données de base : concentrez-vous sur les tableaux, les chaînes, les arbres, les graphes et les tables de hachage – ils apparaissent dans la plupart des problèmes de codage. Soyez prêt à discuter de la complexité temporelle et spatiale.
• Préparez-vous pour la conception de systèmes en étudiant la scalabilité : comprenez la mise en cache, l'équilibrage de charge, le partitionnement et le théorème CAP. Entraînez-vous à concevoir des systèmes comme YouTube, Twitter ou un service de chat.
• Révisez vos histoires comportementales avec la méthode STAR : structurez vos réponses autour de la Situation, de la Tâche, de l'Action et du Résultat, et adaptez-les aux principes de leadership de Google (par exemple, 'Ayez une colonne vertébrale, soyez en désaccord et engagez-vous').

Questions fréquentes