Mi primera entrevista con Google

Bueno, el pasado Jueves pasé mi primera entrevista con Google y el Viernes me dijeron que la había hecho satisfactoriamente y que a la semana siguiente me pasarían otra. ¡Algo es algo!

Fueron unos 45-50min de entrevista en Inglés con uno de los ingenieros de Google. Para mi el tiempo se me hizo eterno y entre los nervios, el calor, el teléfono y mi dicción inglesa, me dio la impresión de que lo había hecho fatal aunque reconocía que era fácil. De hecho la sensación era “avergonzado de lo mal que lo había hecho para lo fácil que era”. Afortunadamente no fue así.

La entrevista se dividión en tres partes: una parte de teoría y dos problemas. Aunque me habían pedido Java o C++, me pude defender perfectamente en Python y a continuación os cuento un poco la entrevista, cómo respondí y cómo me hubiera gustado responder…

En Python ¿Qué diferencia existe entre una tupla y una lista?

Lo primero que respondí fue que la tupla es inmutable mientras que la lista no. Sin embargo el entrevistador estaba más interesado en las diferencias a nivel semántico. No entendí lo que quiso decir hasta que me dijo “Si tuvieras que devolver un entero, una cadena y un objeto de una función… ¿qué usarías?” Aquí –dije– usaría sin duda una tupla.

Sí, la diferencia a la que se refería era a la del concepto matemático detrás de la tupla. La tupla es la forma de representar los elementos del producto cartesiano de dos conjuntos. Los conjuntos pueden no tener nada que ver entre sí. Visto de otr forma, como leí una vez por ahí, una “tupla es una estructura de C ligera“. Cuando trabajas con listas, se supone que los tipos de los elementos son el mismo o están relacionados.

¿Por qué en Java no hay que liberar la memoria de un objeto?

Bueno, pues porque Java tiene un mecanismo llamado recolector de basura (garbage collector) encargado de contabilizar qué objetos están siendo referenciados y cuáles no y liberar el espacio de los que no.

¿Qué implicaciones en rendimiento tiene el recolector de basura?

A esta no supe responder. Por supuesto, las hay, pero no sabía cuantificarlas. No obstante, mi coleg Adri me pasó este artículo de IBM sobre el recolector de basura que afirma que la sobrecarga inducida por el recolector de Java apenas sobrecarga el rendimiento e incluso hace que la reserva de memoria sea más rápida de lo que es en C.

¿Qué es una función lambda y para qué se utilizan?

La primera vez que dijo lambda no lo entendí así que le pedí si podía escribir la palabra en el Google Doc que compartíamos. Cuando vi escrito lambda afirmé y contesté.

Las funciones lambda son funciones sin nombre que devuelven una sola expresión. En python una función lambda tiene la siguiente pinta:

>>> (lambda x:x**2)(9) # Esta función sin nombre, aplicada sobre 9, devuelve el cuadrado de 9
81

Las funciones lambda son útiles en el contexto de uso junto con funciones de segundo orden. Esto es, funciones capaces de acepta otra funciones o devolver nuevas funciones. Algunas funciones de segundo orden son map, filter, sort… Os dejo un ejemplo de utilidad:

def elevado_a (exponente):
return lambda x : x**exponente # Devuelve una nueva función que eleva al exponente dado

cuadrado = elevado_a(2) # Ahora cuadrado es una función que eleva a 2
cubo = elevado_a(3) # Ahora cubo es una función que eleva a 3

print cuadrado(5) # Imprimirá 25
print cubo(3) # Imprimirá 27
print elevado_a(4)(2) # Imprimirá 16 (2 elevado a 4)

¿Diferencias entre un set y un hash set en la STL?

Creo que esta pregunta me salió muy bien. La STL es la Standard Template Library de C++. Primero le dije que hacía mucho tiempo que no tocaba la STL aunque estaba acostumbrado a tratar con los tipos de datos que formaban la librería. De esta forma me preguntó la diferencia entre un set (un conjunto) y un hash set (un conjunto hash).

La diferencia radica en el rendimiento de acceso e inserción. Normalmente, los conjuntos se implementan utilizando un árbol de búsqueda por lo que tanto la inserción como la recuperación de un elemento se realizan en O(log n) para el caso medio.

Con un hash set, el conjunto se implementa como una tabla hash por lo que los accesos e inserciones se realizan en O(1) para el caso medio. En el caso peor, si se producen un montón de colisiones y todos los elementos se encuentran en el mismo bucket de la tabla hash, si estos buckets están bien implementados es posible que sean árboles de búsqueda por lo que a las malas, tendrá el mismo rendimiento que un set normal.

Haz una función que, tomando una lista de listas que representa los píxeles de una imagen, rote la imagen 90º a la derecha.

Este fue el primero de los problemas. Lo primero que respondí es que el problema se resolvía con cuaterniones pero que para 90º seguro que podía obtener otra solución más sencilla.

La clave estaba en darse cuenta de que la rotación a la derecha era como obtener la traspuesta del array bidimensional y luego tomar cada fila al reves. La refleja de la traspuesta. Así, dada la sigiuente imagen:

[
  [1, 2, 3],
  [4, 5, 6]
]

El objetivo era obtener:

[
  [4, 1],
  [5, 2],
  [6, 3]
[

La solución que implemente fue:

def rotate(image):
l = len(image[0])
new_image = []
for pixel in range(l):
aux = reverse([subelement[pixel] for subelement in image])
new_image.append(aux)

return new_image
Podría haber recorrido los píxeles directamente al revés, pero bueno, así queda claro que es la refleja de la traspuesta y me curo en salud.

Considera un tablero de ajedrez, un alfil en una casilla y una casilla objetivo a la que tiene que llegar el alfil. Crea una función que devuelva en cuántos movimientos llega el alfil a la casilla.

Esta es la última pregunta y la que peor creía que me había saludo. No obstante, bien pensado, tampoco destiné más de 15  minutos (que no es mucho) a cada probelma por lo que imagino que eso, sumado a que el entrevistador no hacía más que repetir la frase “make sense” eran indicadores de que iba por el buen camino. Mi desconcierto vino de la representación del tablero de ejemplo (donde SS y TT son origen y destino respectivamente:

00 SS 02 TT 04 05 06 07
08 09 10 11 12 13 14 15
16 17 ...

El caso es que mi cerebro se dividió entre una solución numérica, que trabajara con los números de las casillas buscando alguna relación entre ellos y otra algoritmica, calculando las diagonales y demás. Tenía claro que si no se llegaba en 1 movimiento, se llegaba en 2 (siempre que estuviera en el mismo color, claro). Pero no lo dije.

En un rato el entrevistador me preguntó si no había localizado una cota y le dije que sí, que la cota era evidentemente 2. Entonces, al decirlo en alto me di cuenta de que era siempre 2 a menos que ya estuvieran alineados.

Para ver si estaban alineados podría calcular la diagonal pero la iluminación me vino justo antes del fin de la entrevista, cuando me di cuenta de que si estaban alineados por la diagonal entonces, entre el origen y el destino debía haber un cuadrado, por lo que bastaba con ver si la distancia entre las coordenadas X e Y del origen y el destino eran iguales. Así de tonto:

def movements(source, target):
ss = (source % 8, int(source / 8))
    tt = (target % 8, int(target / 8))
if abs(ss[0]-tt[0]) == abs(ss[1]-tt[1]):
        return 1
return 2

Y eso fue todo, la próxima entrevista la tendré este Viernes, ya os contaré (qué nervios).

Anuncios

7 comentarios en “Mi primera entrevista con Google

  1. Muy bien explicado todo. Así, parece muy sencillo.

    Creo que el WP ha hecho estragos con los smilies en el código de la solución al problema del alfil. ¿Te dijeron que podía haber otras fichas en el tablero?

    1. Sí, WP ha hecho cosas rarunas con el último ejemplo (ahora lo arreglo).

      No, sin más fichas. De hecho son supergenéricos en las preguntas y tu vas hacindo consideraciones. Por ejemplo, en el set vs hash set les dije “voy a considerar que el caso peor es que haya muchas colisiones porque se ha elegido mal la función hash y que los buckets están implementados por árboles binarios”.

      Si no, no hay tu tía.

  2. Salva, el recolector de basura de Java tiene una consecuencia muy elemental en el rendimiento: tendrás picos de trabajo distribuidos de forma aleatoria a lo largo del programa. Eso implica que no se pueden utilizar ese tipo de estrategias en aplicaciones con requisitos de tiempo real, por ejemplo.

    Otra cosa es que el mito de que la gestión de memoria con recolector es más eficiente es eso, un mito. Cuando haces tú la gestión de memoria, a la hora de liberar un puntero suele estar ya en cache (porque acabas de utilizarlo) y la liberación se puede gestionar mucho más deprisa. Con el recolector de basura suele pasar todo lo contrario, que al ser elementos que no han sido referenciados en una buena temporada, no están en cache. Además, como la visibilidad de variables y su declaración no tiene una relación fuerte, es bastante probable que tengas un fallo de cache por casi cada puntero que hay que liberar.

    De todos modos, te preguntaban por lo primero, los problemas con sistemas en tiempo real.

    1. Bueno, no me parecía tan elemental, xP. Pero queda aprendido. De todas formas, hay alternativas al recolector de basura clásico, tal y como se explica aquí:
      http://www.ibm.com/developerworks/java/library/j-rtj4/index.html

      Parece ser que este sistema se basa en una recogida incremental de basura (cosa bastante razonable) y se llama Metronome.

      En cuanto a lo del mito, entiendo lo que quieres decir. Lo veo razonable. ¿Lo dices por algo de lo que he puesto en el artículo?

      De todas formas, en cuanto a lo de los fallos de caché, no sé si se comportaría así el sistema generacional que lo que hace es copiar los vivos a otra región de memoria y luego reclamar toda la memoria como libre. Creo que en el momento que referencias el punto de entrada al montón, te traes todos (casi todos) los objetos vivos. Pero no lo sé, creo que depende de la implementación.

      ¡De todas formas, gracias por los aportes!

      1. Digo elemental porque todos hemos usado programas en java y hemos sufrido el recolector, no porque sea algo que uno nace sabiendo xD Vamos, es que yo oigo “recolector de basura” y pienso “trompicones”.

        Lo del mito lo digo por el artículo de IBM. Da igual que el sistema sea generacional o como sea, el caso es que si tienes un sitio donde guardas direcciones de memoria que quieres liberar, y lo haces todo de golpe y después de un tiempo, por cada dirección que pidas para “hacer un free”, vas a tener un miss. Por supuesto, hay estrategias más y menos eficientes, que favorecen una situación u otra, pero en general (y lo digo sin haber perfilado un recolector, hablo por intuición), una buena política manual va a ser más eficiente que cualquier sistema gestión automático.

        Para que te hagas a la idea, en general en los recolectores se tiende a no hacer la recolección a no ser que te estés quedando sin memoria. Si la aplicación termina y no has tenido necesidad de memoria, el recolector ganará a una estrategia manual (fundamentalmente porque no entra en funcionamiento); pero como entre a funcionar…

        Las ventajas del recolector están en tiempo de programación, no en tiempo de ejecución 😛

  3. No seré yo quien diga que la gestión manual de memoria no es la mejor.

    No obstante, el hecho de que en la gestión manual el puntero ya se encuentre en caché “porque acabas de usarlo” no me convence. El caso que comentas se daría en el momento de la destrucción de objetos temporales de corta duración (objetos de función, de ámbito en C y cosas así). De hecho, si ese fuera el problema, la máquina virtual podría estar atenta a las salidas de ámbito de las variables y destruir los objetos muertos (cosa que ya hace), emulando el comportamiento que tu describes y con el mismo overhead (él detecta la salida de ámbito y hace un free y tu lo invocas explícitamente antes de salir de ámbito).

    En realidad, la liberación explícita no ocurre tan a menudo como podría parecer. En general, los objetos están ahí para que vivan.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s