Hommes

Recrutement Google : l’entretien technique

J’ai passé il y a quelques temps une série d’entretiens de recrutement chez Google et je suis certain que ça intéressera un candidat potentiel de connaître le « genre de questions » que l’on peut vous poser…

Voici un simple copié-collé du Google-document qui a servi de support lors de mon premier entretien technique.

Les entretiens techniques de Google font suite à une série de coup de fils (variant entre 20 et 45 minutes), en anglais, visant à vous cerner davantage. Comme les précédents, ces entretiens techniques sont téléphoniques et durent officiellement 45 minutes – le mien a duré 1h30 – en anglais bien sûr…

Vous devez être devant votre écran, connecté à Internet avec pour mission de répondre à votre « interviewer » principalement en écrivant du code sur un Google doc que vous partagez avec lui.

Voici donc comment s’est déroulé mon entretien :

« … imaginez un échiquier de 80 cases de côtés, blanches et noires alternativement,écrivez une fonction qui génère cet échiquier. »

J’avais pour ma part choisi de traiter le sujet en python…J’ai l’habitude de tester mon code en codant, ou du moins en partie mais il a fallut me détacher de cette facilité… Pendant l’entretien technique, pas de possibilité de tester, il fallait écrire sur un simple document. Mon interviewer, un « software engineer », avait probablement pour sa part un compilateur intégré dans le cerveau…

Ma première fonction était un peu basique et surtout assez verbeuse – le temps de m’échauffer :

// 80x80 black=0 white=1

# 010101....0101
# 010101 bug
def generateArray():
l__array = []
l__case = 1
l__temp_array = range(80)
for l__row in l__temp_array:
  l__array.append([])
  for l__col in l__temp_array:
    if l__case == 1:
      l__case = 0
    else:
      l__case = 1
    l__array[l__row].append(l__case)
   # fix here
return l__array

… un peu buguée, puis je l’ai améliorée en discutant avec mon interviewer :

# 010101010...
# 1010101010...
def generateArray2():
l__array = []
for l__row in xrange(80):
  l__array.append([])
  for l__col in xrange(80):
    l__array[l__row].append((l__col+l__row)%2)
return l__array

Au passage une question sur la différence entre range() et xrange() en python (range utilise un tableau, xrange un curseur)…

Puis l’interviewer a modifié son énoncé pour générer un échiquier de 80×80 avec 8 cases nulles, 8 cases « 1″, etc…

# 0000000000111111111100000000001...
# 0000000000111111111100000000001...
# …. 8 more starting with 0
# 11111111110000
def generateArray3():
l__array = []
for l__row in xrange(80):
  l__array.append([])
  for l__col in xrange(80):
    l__array[l__row].append((l__col//10+l__row//10)%2)
return l__array

Notez ici l’astuce « append((l__col//10+l__row//10)%2) » qui a valut quelques minutes de réflexion, mais c’est ce genre de choses qu’ils attendent : astuces, amélioration de code, factorisation, etc.

Ensuite, nouvelle modification de l’énoncé pour générer un tableau équivalent mais codé… en octets :

def generateArray4():
# [0..255, 0..255, ...]
l__array = []
for l__row in xrange(80):
  for l__col in xrange(80):
    l__array.append((l__col//10+l__row//10)%2)
return l__array

def generateArray5():
# [0..255, 0..255, ...]
l__array = []
i = 0
l__temp_string = “”
for l__row in xrange(80):
  for l__col in xrange(80):
    if i==8:
      l__array.append(int(l__temp_string,2))
      l__temp_string = “”
      i = 0
    l__temp_string += str(l__col//10+l__row//10)%2)
    i += 1
l__array.append(int(l__temp_string,2))
return l__array

def generateArray5b():
# [0..255, 0..255, ...]
l__array = []
l__temp_number = 0
for l__row in xrange(80):
  for l__col in xrange(80):
    l__temp_number = (l__temp_number << 1 + (l__col//10+l__row//10)%2)
    if l__col%8 == 7:
      l__array.append(l__temp_number)
      l__temp_number = 0
return l__array

Je n’ai jamais testé ces fonctions et elles comportent peut être des erreurs mais peu importe, ce qui compte c’est démontrer que vous savez coder efficacement et… intelligemment. (Notez que j’utilisais xrange…)

Puis un deuxième exercice, assez basique, qui consistait à créer une nouvelle fonctionnalité « fictive » dans GMail : programmer l’heure d’envoi d’un mail ; l’objet de données étant stocké en RAM et contenant l’ID du message et le « timestamp » d’envoi.

Bon… sans faire dans le détail, j’ai proposé d’organiser les données sous forme de « tas » (« heap »), ça a eu l’air de lui plaire… S’en sont suivies des questions théoriques sur la complexité des algorithmes de parcours d’arbres (les tas sont des arbres) ; pour finir sur une question de taille des données à calculer : le milliard tiendra-t-il en RAM sur une seule machine ? La réponse est oui.

# ---

# If the heap contains n pairs, then
# inserting 1 more pair takes O(log(n)) maximum time.

# search find 0(1)
# remove min time O(log(n))

# timestamp: 32-bit integer
# message ID: 64-bit integer
# 1 billion pairs

struct Message {  // 20 bytes
int32 timestamp;
int64 message_id;
int32 pointer_left;
int32 pointer_right;
};
// bin(1000000000) = 0b111011100110101100101000000000
// 2**32 == 4 * 1024 * 1024 * 1024

// 19531250 KB
// 19073 MB
// 18 GB

Alors… pas si sorcier ? A vous de voir… Mais sachez que j’ai révisé cet entretien, comme un examen, pendant 2 semaines. J’écrirai un prochain billet en vous donnant l’ensemble des connaissances à avoir pour passer un entretien technique chez Google !

Related Posts with Thumbnails

3 Commentaires

  1. Etienne dit :

    Thomas,
    Ton article est très intéressant, et ca ne m’étonnes pas que tu sois intéressé par Google !
    Je te souhaite bonne chance dans ta candidature.
    Un autre moyen d’y rentrer, c’est de monter son entreprise et de se faire racheter !

    En tout cas bien joué pour tes factorisations en python !
    Ca doit pas être facile de tenir 1h30 à ce niveau !

  2. Cédric dit :

    Intéressant ! Et le verdict ? Tu es encore dans le process ou pas ?

Laisser une réponse

Connect with Facebook