Cuando Google llama a tu puerta

Hace tiempo que no escribo nada por aquí, salvo alguna foto. No sé a qué se debe exactamente. Quizá a que tengo que hacer tantas cosas que escribir aquí me parece una pérdida de tiempo.

Sin embargo, están pasando muchas cosas en mi vida, bastante importantes, y quiero escribir alguna de ellas. Por ejemplo, como el título indica, Google me ha llamado porque están montando un centro de investigación en Zúrich. Esto sucedió hace unos meses. Hablaron conmigo, les envié el currículum y no supe nada más hasta hace poco. Pensé que mi currículum no era ninguna cosa del otro mundo y que se habían olvidado del tema, ya que tendrían cien mil solicitudes mejor que la mía.

Hace poco recibí una llamada al móvil de la que no entendí una palabra al principio. Decía algo así como "Hi sfdsfaisodfsifd sfsf Google UK". Cuando entendí esto último y logré cambiar el chip a inglés... por fin pude entender lo que me decía. Según parece, la que habló conmigo en primera instancia ya no estaba en Google y por eso se habían retrasado en llamarme.

En fin, que concertaron una entrevista con alguien de Google Zurich. Me explicaron que Google es una empresa guiada por el "Engineering", por lo que ellos mismos eran los que en última instancia decidían si contrataban o no. Por lo tanto, la entrevista sabía que iba a ser de corte tecnológico, con acertijos, etc.

Esta tarde me han llamado. Después de preguntarme cosas sobre el currículum (como en qué medida había participado en evolution y en Mono, si había escrito tests unitarios para mi código, en qué había consistido la revisión de código que había hecho, etc.) ha cambiado el tercio para hacerme preguntas de programación que tienen preparadas. Reproduzco más o menos en español lo más interesante del diálogo. En realidad ha sido en inglés: (G = Google, D = Diego):


[G] - Déjame que te pregunte una coas. Imagina que tienes una cadena de caracteres con palabras dentro y quieres ordenar las palabras en orden inverso. ¿Cómo lo harías?

[D] - Eh... esto... Construiría una lista de palabras con un list<string>, iría introduciendo las palabras en ella y luego recorrería la lista de forma inversa escribiendo en la cadena original.

[G] - OK, ¿y qué complejidad tendría eso?

[D] - Sería O(n), porque se tienen que hacer un par de recorridos por la cadena de longitud n.

[G] - OK, ¿Y en cuanto a memoria?

[D] - Pues sería también de orden O(n+m), donde n es el número de caracteres de la cadena (duplicados en total, ya que la lista contiene los mismos caracteres en total) más m nodos de lista donde m es el número de palabras.

[G] - OK. ¿Y se te ocurre una manera de hacerla usando sólo la cadena original?

(Aquí, en vez de estar pensando en el algoritmo, yo sólo pensaba "¡Coño, esto tiene que ser fácil!" "Me cago en la leche" Y a la vez pensando en qué decirle al tipo en inglés para que no se aburriera)

[D] - Let me see... si invierto la cadena... no, eso no, porque blah blah...

(pienso un poco ... Después me he dado cuenta)

[D] - Ahh, OK, si invierto la cadena, luego puedo invertir cada palabra dentro de esa cadena, y ya está.

[G] - OK, sí, esa es la respuesta, ¿cuál es la complejidad, etc.?

...

(La siguiente pregunta era de otro algoritmo. En realidad ninguno de los dos eran muy complicados, pero sí que indican a ellos que tienes las herramientas necesarias)

[G] - OK, ahora otro problema diferente. Imagina que tienes una secuencia de números, y que te digo que busques si en la secuencia hay dos números tales que sumados me de otro número.

[D] - Yo le he dicho, para ir aclarando, por ejemplo, que tengo dos números dentro de la cadena, i y j, que al sumarlos dan k: i+j=k

[G] - Así es.

(piensa otro medio minuto)

[D] - OK, ordeno la secuencia y empiezo a recorrerla con dos índices. Uno al principio y otro al final. Avanzo el del final hacia el principio mientras el resultado del índice de la izquierda más el de la derecha sea mayor que k. Cuando llegue a uno que es menor que k, incremento el índice de la derecha, y así sucesivamente.

[G] - OK, ¿y qué orden tiene eso?

[D] - (aquí me he equivocado y le he dicho que ordenar era O(log2n), cuando en realidad es O(nlog2n). No importa, él me ha corregido). OK, sería O(log2n), porque el recorrido final es O(n).

[G] - O(n log2n)

[D] - Oh, sí, efectivamente, perdón.

[G] - ¿Y no se podría hacer más rápido?

[D] - (claro, he pensado "¡coño!" otra vez...) Se podría construir otro array, donde se apuntara de alguna manera el número necesario... no, espere... pero eso necesitaría de otro array, y antes me ha dicho que no utilizara mucha memoria

[G] - Sí, pero eso era para el de ahora. ¿Qué harías si puedes utilizar más memoria y otros arrays?

[D] - Si puedo utilizar bastante memoria, lo mejor sería un hash o un array de booleanos inverso si sé ma magnitud de los números (por ejemplo, de 1 a 1000 puedo construir un array de booleanos de 1000 elementos).

[G] - OK, y si usas hash, ¿qué función usarías?

[D] - Pues depende de la cantidad de memoria que quisiera utilizar. Eso define el tamaño del hash y el número de bits de la indización. Normalmente se utilizan funciones módulo N, donde N es el tamaño de los índices del hash, y también se pueden evitar colisiones y hacer algoritmos más eficientes con el direccionamiento abierto y el doble hashing, o incluso teniendo tablas precalculadas de hash como utiliza gperf, que siempre da O(1) al evitar las colisiones.

[G] - OK, muchas gracias. Creo que la entrevista está llegando a su fin... Si tienes alguna pregunta que hacerme...

[D] - Hombre, pues si puedo preguntarte, me gustaría que me comentaras qué te ha parecido la entrevista :)

[G] - Hombre.... no te lo puedo decir... esto no soy yo quien lo evalúa... Pero en fin... te puedo decir que vas a hacer la siguiente entrevista...


Lo cual quiere decir que quizá no lo haya hecho tan mal...

Sinceramente, lo que más trabajo me ha costado es explicar por el teléfono y sin saber el problema de antemano en inglés las cosas... Cosas como "recorrer un array", no recordaba cómo se decían. Quizá como "go through the array", pero no estoy muy seguro... He querido poner esta entrevista para que si alguien se ve después en esta tesitura, al menos sepa a qué enfrentarse.

Y ahora el verdadero problema... Esto es un sueño, sin duda. Google es una de las empresas más importantes e innovadoras del mundo. Pero esto también significaría dejar mi vida aquí y emprender otra dirección. Es difícil conciliar pareja y familia con eso.

blog comments powered by Disqus