Mi segunda entrevista con Google

Bueno, antes de nada decir que no la he pasado, pero que no hay nada que lamentar. Estoy trabajando en Telefónica I+D desde hace tres semanas y me gusta mucho el puesto en el que estoy (sólo tengo que conseguir que me contraten ellos y no andar de subcontratado, jejeje).

Esta vez fueron otros 45 minutos; me puse muy nervioso y me trababa cada dos por tres. Es lo más negativo que observé de mi actuación: que me faltaban las palabras. De nuevo se dividió en dos partes: durante la primera tuve que describir mis experiencias trabajando y durante la segunda hacer algo de programación y analizar mis propios algoritmos. Salí muy convencido de que esta parte la había hecho bien pero, mira tú por dónde, hoy mismo me di cuenta de que hubo un par de problemas en mis respuestas.

En fin, espero que mis errores ayuden a otros. Vamos con el contenido de la entrevista.

Tienes 6 minutos para describir tus mejores experiencias de trabajo, qué aspectos te gustaron y cuáles no.

Iba a contar tres de mis experiencias y sólo me dio tiempo a dos: mi trabajo como investigador para el grupo NIL y mi trabajo como autónomo para Kurma y Buroges. El primero porque me introdujo en el mundo de la investigación y este me gustó mucho. Además derivó en una arquitectura reutilizable y práctica. El segundo porque me enseñó a administra mi tiempo, a gestionar mi propio trabajo y a responder de cara a mis jefes directamente.

Lo que no me gusta de mis trabajos es no encontrar el por qué de un fallo. No encontrar la solución no es muy problemático pero no encontrar la causa de una fallo es muy frustrante y lo mejor es dejarlo un rato y volver a ello un poco más tarde.

Escribe una función que imprima los números primos hasta un máximo dado. ¿Cómo justificarías que la solución es correcta? ¿Qué complejidad tiene?

Bueno, el algoritmo que implementé fue la criba de Eratóstenes con la mejora de avanzar sólo hasta la raíz del máximo. Cuando dije que iba a implementar esa solución me quedé atrancado con la palabra criba porque no tenía ni idea de cómo era en inglés.

Este es el código que dí*:

def primes(max):
    limit = int(max **.5)
    sieve = [(n, True] for n in range(1,max+1)]
    sieve[0][1] = False # 1 is not prime
    i = 1
    while i<=limit:
        n = sieve[i]

        # Mark multiplies
        m = 2
        r = m * n
        while r <= max:
            sieve[r][1] = False
            m += 1
            r = m * n

        # Skip already marked
        i += 1
        while i<=limit and not sieve[i][1]:
            i += 1

    for n, is_prime in sieve:
        if is_prime: print n

* Miento, creo que no es el código que  di exactamente y probablemente ahí estuviera uno de mis errores. Es muy probable que me colara en la inicialización de i por tratar de hacer las cosas mejor de lo que debiera en vez de fáciles. Ya veis, primer consejo: primero fácil.

El caso es que ese código obtiene los números primos así que vayamos con las siguientes preguntas.

Justificar que la respuesta es correcta no es fácil: lo que tienes que justificar es que la criba de Eratóstenes no puede imprimir otra cosa que no sean números primos porque todos los múltiplos han sido marcados. Comprobar si la salida son primos viendo si pueden factorizarse, desde luego, no es una opción dado que la factorización no es un problema resoluble en tiempo polinómico.

Por otro lado, la complejidad de la solución, que yo dije, fue O(n). Lo cual, pa empezar, ya está mal. El entrevistador me hizo darme cuenta de que esto no es así porque dependen de la distribución de los primos en el segmento. Todo se debe a este bucle:

        # Skip already marked
        i += 1
        while i<=limit and not sieve[i][1]:
            i += 1

Tal es el que hace que sea impredecible cuándo parará. De no existir el bucle, la complejidad se encontraría en O(n · sqr(n)) no obstante. ¿Por qué? Porque el bucle exterior opera sqr(n) veces mientras que el interios, como mucho, opera n/2 veces (al tachar todos los pares, por ejemplo). Luego el número de iteraciones es sqr(n) · n/2 que pertenece a O(n · sqr(n)). Primer fallo.

Escribe una función que obtenga la mediana de 3 números enteros. ¿Cuántas comparaciones son necesarias? ¿Cuál es la complejidad del problema de la mediana?

Creo que este lo hice bien. Para evitar el follón de ponerme a hacer comparaciones decidí resolver el problema así:

def mediana(a, b, c):
    return sorted([a, b, c])[1]

El entrevistador dijo que era una solución muy elegante pero que quería saber cuántas comparaciones eran necesarias. Le dije que si el problema era equivalente ordenar el vector, el número de comparaciones debía ser 3 poruqe el método de ordenación por selección sólo necesitaba 3 comparaciones.

En cuanto a la complejidad, dado que el problema de la mediana es equivalente a ordenar el vector, tenemos que con un buen algoritmo de ordenación como quicksort o mergesort, la complejidad se va a O(n·log n).

Sabía que lo del número de comparaciones era cierto, pero para demostrároslo en este artículo quería implementar la solución sólo con comparaciones. Ha costado pero aquí está:

def mediana(a, b, c):
    min = a
    med = b
    max = c
    if med < min:
        min, med = med, min
    if max < med:
        med, max = max, med
    if med < min:
        min, med = med, min
    return med

Pensada del tirón no es fácil. Lo mejor es desarrollar el bucle de la ordenación por selección. La idea radica en mantener las relaciones entre min, med y max, a saber: min <= med <= max. Esto puede determinarse en dos comparaciones: min <= med and med <= min que es precisamente el efecto obtenido al no entrar por ninguno de las dos primeros if. El tercero está ahí para comprobar que, tras el cambio del segundo if el valor en min sigue siendo menor que el medio, y corregirlo en caso contrario.

Tienes muchos archivos en tu disco duro y necesitas saber si están repetidos. Describe cómo lo harías. Complejidad.

Se refiere a repetición del contenido. Se trata del problema de ver si dos archivos son iguales. Esto se puede hacer utilizando algoritmos de digest y hashes. Si las claves resultantes no son iguales, seguro que los archivos no son iguales. En caso contrario, si quisiéramos asegurarnos al 100% compararíamos los archivos bien restándolos en memoria, bien poco a poco si no cupiesen enteros. Si no necesitamos el 100% de certeza, podemos aplicar otros algoritmos de hash.

Aquí la fastidié en la complejidad. Pensé: “para tener todas las comprobaciones necesitas el productos cartesiano de los archivos”. Y lo pensé convencido de que así no habría repeticiones por el orden. Convencido porque en el trabajo me había enfrentado a una cosa similar en la que el producto cartesiano sí era la respuesta… pero no aquí. Evidentemente si tienes el conjunto de ficheros {F1, F2} y haces el producto cartesiano consigo mismo, resulta que el conjunto resultante es { (F1, F1), (F1,F2), (F2.F1), (F2, F2)}. Resultando que, donde sólo necesitabas una comparación, te salen 4. La respuesta correcta es la misma que el problema de los apretones de manos. Es decir, ¿en una fiesta de N personas, si todo el mundo se dé la mano con todo el mundo, cuántos apretones hay?.

Bueno pues habrá 1 + 2 + 3 + 4 + … + N-1. Lo cual supone N(N-1)/2 por lo que sí, la función pertenece al O(N^2) pero no siguiendo el razonamiento que yo había hecho. Además, esto es suponiendo un tamaño de archivo pequeño en comparación con el número de archivos en el disco duro. El bucle encargado de lanzar las comparaciones iteraría N(N-1)/2 veces y dentro realizaría una (o varias) operaciones de hash con complejidad en (seamos buenos) O(l) donde l es el tamaño medio del archivo. Mi scrummaster y estudioso de la narrativa interactiva, Mel Hython, me hizo ver que todo dependía de la relación entre l y N. Considerando l como la media del tamaño del archivo tendríamos L = l · N con L el tamaño total de todos los archivos. Así, despejando l tendríamos que l = L/N y por tanto la complejidad quedaría como N(N-1)·L/N·2 = L(N-1)/2. Como N puede variar entre 1 (muy pocos archivos muy grandes) a L (muchos archivos muy pequeños), la complejidad varía entre O(L) (cuando N=1) y O(L^2 ) (cuando N=L).

Y bueno, eso es todo. Como veis, el último fallo bastante tonto. Lo podría haber sacado de haber pensado un poquito pero me traicionaron los nervios y razoné de forma equivocada… Me alegro no obstante de haberme dado cuenta de mis fallos y sé que he aprendido de ellos. También he aprendido que no trabajo bien bajo tanta presión… Ay.

Una anécdota antes de terminar es que recibí el último correo, avisándome de que estaba fuera del proceso, a nombre de otro. Así, viendo la estructura del mismo parecía el típico correo genérico así que supuse que no era el único en recibir malas noticias hoy 😉 De todas formas escribí a mi contacto en recursos humanos para que me lo aclarara y, no habrían pasado ni cinco minutos, me llamó al móvil para decirme que, desafortunadamente, el mail sí que era para mi: que según el entrevistador, lo había hecho bien “pero no lo suficiente” y que lo volviese a intentar en 12 meses. Le contesté pidiendo que si podía echar un vistazo a los informes sobre mí, que esp me ayudaría a mejorar. Los estoy esperando, pero no creo que reciba nada.

Y esa ha sido mi corta historia con Google. No me preocupa demasiado, no es malo para nada e, insisto, ando muy contento donde estoy y seguro que más de uno hasta se alegra de que no me vaya.

Anuncios

3 comentarios en “Mi segunda entrevista con Google

  1. No termino de entender la última parte, acerca de la distribución del tamaño de los archivos, pero dado que no todos los archivos tienen por qué tener el mismo tamaño, y dos archivos con el distinto tamaño no pueden ser iguales, yo hubiese comenzado por agruparlos por tamaño antes de compararlos, van por ahí los tiros?

    1. Sí, si te das cuenta, el tamaño puede ser parte de la función hash. Puedes tomar una función has con el tamaño y el tipo, para empezar.

      Yo lo que había asumido con esto (para hacerlo interesante) es que todos los archivos tenían el mismo tamaño l. Es decir, que tenías que pasarles una checksum como mínimo.

  2. Bueno, ha estado bien y te animan a repetir dentro de 12 meses, lo cual es bueno, porque significa que en algún momento acabarás entrando.
    Si yo quisiera entrar por programación lo pasaría regular, menos mal que no sería el caso xD

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