Entretien d'embauche avec Google

Les RH de Google m'ont contacté il y a maintenant 3 semaines afin de me faire passer la première étape de leur entretien d'embauche.

L'interview, technique, c'est déroulé en 2 parties de 45 minutes chacune, durant lesquelles un ingénieur Google m'a posé des questions techniques. Apparemment il n'y avait pas un nombre défini de questions, mais tant qu'une réponse jugé satisfaisante était trouvée, on passait à une autre, inventée on the fly mais en relation avec notre CV.

Voici un petit aperçu des 10 questions auxquelles j'ai réussi à répondre. Elles sont traduites en franglais_geek1 pour les besoins du billet, et je n'y fait figurer que celles que j'ai trouvé intéressantes ou qui sont faciles d'exposer sur un blog :

1. Implémentez en C la fonction assert(i > 0) de manière à ce que la condition "i > 0" soit affichée en cas d'erreur
2. Même chose en C++, afin que le code suivant soit bien formé :
   assert(i > 0) << "message" << i ;
3. Triez un tableau d'un million d'entier (int sur 4 bytes) stockée sur un disque dur en ne disposant qu'une mémoire de 2 MB. Comment vous y prenez vous ?
4. Implémentez une classe qui contient 3 méthodes :
   - void push(int)
   - int pop()
   - int minimum()
   dont les 3 méthodes s'exécute avec une complexité en O(1)
5. Trouvez une méthode efficace qui permet de détecter une boucle dans une liste chainée, sans pouvoir modifier les éléments de la liste ni recopier en entier la liste.

Les questions sont posées sans temps de préparation, ni ordinateur ou autres documents d'aide. On remarquera que les réponses, une fois connue, ne sont pas si compliquées qu'elles en auraient l'air.

1. Première hypothèse, avant que l'expert ne précise que la condition "i > 0" doit être affichée :

void assert (int cond) {
  if (cond == 0) {
    printf("Erreur");
    exit(1);
  }
}

Le problème se corse quand il s'agit d'afficher textuellement "i > 0", car en passant par un argument, il sera évalué avant d'être passer par valeur, donc on perd toute chance de pouvoir l'afficher. Ma deuxième version en passant un pointeur de fonction en paramètre s'est vite avérée fastidieuse, et l'idée d'utiliser par une marco et ses possibilités de manipulation de strings m'a soudain frappée, pour finalement donner quelque chose :

#define assert(cond) if ((cond) == 0) { \
  printf("Erreur "); \
  printf(#(cond)); \
  exit(1); \
}

2. Une fois la première question complétée, la deuxième est devenue triviale : il suffit d'ajouter cout à la fin de la macro pour que si la condition était différente de 0, on continue avec cout.

#define assert(cond) if ((cond) == 0) { \
  printf("Erreur "); \
  printf(#(cond)); \
  exit(1); \
} \
cout

3. 1 million d'entiers sur 4 bytes nous fait 4MB, donc trop pour tenir en entier dans la mémoire. Il faut donc partager le tableau en 2, trier chaque partie en utilisant n'importe quel algorithme de tri, puis fusionner les 2 tableaux à l'aide d'un tri par fusion.

4. La complexité en O(1) nous suggère directement l'utilisation d'une liste chainée. Push et pop deviennent donc trivial, push ajoute l'élément à en tête de liste, pop retourne en enlève le premier élément de la liste.
Le problème se pose maintenant pour la méthode qui retourne le minimum, qui est doit aussi se faire en O(1). Il est donc impossible de faire une recherche, car aucune méthode de recherche n'est en O(1). L'idée est donc de maintenir une deuxième liste chainée qui contiendra ces minimums. Donc on modifie push pour tester si la valeur à ajouter est plus petite OU EGALE au minimum, et si c'est le cas on ajoute aussi l'élément dans la liste des minimums, et pop pour enlever l'élément de la liste des minimums si cet élément est le minimum.

En pseudo Java ça nous donne quelque chose du style :

LinkedList l;
LinkedList m;
void push (int e) {
  if (e <= m.top()) {
    m.push(e);
  }
  l.push(e);
}
int pop() {
  int e = l.pop();
  if (e == l.top()) {
    l.pop();
  }
  return e;
}
int minimum() {
  return m.top();
}

5. La solution trivial qui est de marquer les noeuds parcourus n'est pas envisageable, car elle sous-entendrait de modifier le contenu des noeuds, ce qui n'est justement pas possible.
Une bonne solution est donc d'inverser les liens en parcourant la liste, et si on revient au noeud initial on sera sûr d'avoir une boucle. En parcourant la liste dans l'ordre inverse et en réinversant les liens, il est possible de remettre la liste dans l'état qu'on avait avant de débuter la recherche. A noter qu'il est impératif de s'assurer qu'un seul processus n'accède à la liste en simultané, car durant la recherche la liste est modifiée.

2 entretiens sur 6, prochain épisode pour bientôt j'espère...