Preguntas de entrevista de Google (con respuestas)

Bueno, ayer me rechazaron en Gameloft. Pero vamos, estoy en tropocientos procesos de selección y no me precoupa demasiado. Al parecer uno de ellos parace que será con Google. Alguien de Google Careers se puso en contacto conmigo y me dijo que había pasado mi CV (del que tenéis una versión recién actualizada en el blog). Así que supongo que en me llamarán en breve. ¡Y voy a hacer trampas!

No, ahora en serio. Sencillamente se ha presentado una muy buena escusa para coger una lista de preguntas que Google acostumbra a preguntar y responderlas. Evidentemente no me las sé todas y la mayoría están buscadas por ahí pero espero que sirvan para el enriquecimiento personal y profesional de todo programador. Por supuesto, si alguien quiere proporcionar una respuesta mejor, que lo haga. Yo voy a intentar ser sencillo, abstracto e independiente de la implementación. A ver si hay suerte. Aquí van las 10 primeras:

#1 ¿Por qué las tapas de las alcantarillas son redondas?

Para no caer a través de su propio agujero. Y por supuesto, porque suponen un fácil transporte.

EDIT: He encontrado este enlace del Blog de Raul Ochoa que, a parte de dar respuestas convincentes, también se da una mejor respuesta y cito textualmente:

Las tapas de las alcantarillas son redondas para que las Tortugas Ninja puedan pasar sus pizzas^* a través de ellas.

^* Donde el radio de la pizza < radio de la tapa de alcantarilla.

#2 ¿Cuál es la diferencia entre un mutex y un semáforo? ¿Cuál usarías para proteger una operación de incremento?

En sincronización, ambas son formas de proporcionar acceso simultaneo a un recurso cmpartido. El mutex sólo permite un acceso simultaneo mientras que el semáforo permite varios. Si quieres simular un incremento atómico, márcalo como sección crítica con un mutex y asegurarás que sólo el hilo que haya tratado de acceder a él en primer lugar puede modificarlo.

#3 Un hombre llevó su coche hasta un hotel y perdió su fortuna. ¿Qué ha pasado?

Bueno, esto es muy friki. Lo que ha pasado es que jugaba acaba de perder en el Monopoly (su ficha era el coche y ha caído en una casilla de un rival).

Fuente: http://wiki.answers.com/Q/A_man_pushed_his_car_to_a_hotel_and_lost_his_fortune_What_happened

#4 Explica el significado de DEAD BEEF

No pienses en la traducción. DEAD BEEF es una cadena cláramente reconocible entre un código expresado en hexadecimal. Se usa en depuración como palabra mágica para identificar situaciones de cuelgue o interbloqueo.

Fuente: http://en.wikipedia.org/wiki/Hexspeak

# 5 Escribe un programa en C que mida un cambio de contexto en UNIX/Linux

Vale, esta es chunga, y yo sólo tengo una vaga idea de cómo hacerlo pero si alguien quiere darme código explícito y explicado lo agradecería. La idea es más o menos la siguiente:

1. Crea un proceso que se divida en dos.
2. Duerme al hijo.
3. En el padre obten un timestamp (por tiempo, por ticks…)
4. Despierta al hijo
5. Duerme al padre
6. En el hijo obten el mismo timestamp
7. Resta los timestamps

Creo que, en teoría, eso está bien.

#8 Dada una función que produce un número aleatorio del 1 al 5, crea una función que obtenga números aleatorios del 1 al 7.

Este problema parece sencillo pero tiene algo de chicha detrás. Primero vamos con una solución muy elegante que he encontrado por ahí.

La idea es rellenar los tres primeros bits (los de menor orden) de un entero tomando 0 ó 1 dependiendo de si nuestra función azarosa del 1 al 5 devuelve algo menor que 3 o mayor que 3 respectivamente. Si devuelve 3, ignoramos el resultado y volvemos a probar. Teneis el código en Python justo a continuación:

n = 0
for i in range(3):
    while ((r = rnd5()) == 3):
        pass
    if (r > 3):
        n += 2**i

Fuente: http://commoninterview.com/Programming_Interview_Questions/write-a-function-which-produces-a-random-integer-in-the-range-1-to-7-based-on-function-which-returns-random-integer-in-the-range-1-to-5–1/

Como veis, hay una ligera probabilidad de que no salga jamás del bucle while (muy, muy leve: con sólo 10 iteraciones hay una probabilidad del 0,00001%) y esto tiene que ver con la explicación extendida del problema.

Por lo visto en una respuesta en Stack Overflow, este tipo de problemas sólo tienen solución siempre (es decir, sin probabilidad de que no terminen) si un número divide a alguna potencia del otro. En este caso si 7 dividiera a alguna potencia de 5. Como 7 y 5 son coprimos esto es imposible. ¿Cuál es la explicación? Bueno, intuitivamente se puede ver así:

int rand7() {
 int vals[5][5] = { { 1, 2, 3, 4, 5 },
                    { 6, 7, 1, 2, 3 },
                    { 4, 5, 6, 7, 1 },
                    { 2, 3, 4, 5, 6 },
                    { 7, 0, 0, 0, 0 } };

 int result = 0;
 while (result == 0) {
    int i = rand5();
    int j = rand5();
    result = vals[i-1][j-1];
 }
 return result;
}

El algoritmo es bastante autoexplicativo. Para generalizar, supongamos que queremos producir un número al azar del 1 al N con una funcion que genera números del 1 al n, con n<N. Se repite el rango de 1 hasta N, un número entero de veces en un array multidimensional (cada dimensión de longitud n) con posiciones suficientes como para albergarlo. El resto se rellena con ceros. Se escoge un número al azar del array seleccionando las componentes del 1 al n por separado. Si es 0, repetimos. Si no lo es tomamos ese número.

En nuestro caso, la probabilidad de que no salgamos nunca del bucle while existe (es de (4/25)^iteraciones) y la probabilidad de escoger un número cualquiera es de 3/21 o, lo que es lo mismo, 1/7.

El array no tiene por qué limitarse a ser bidimensional: puede ser de la dimensión que se necesite para albergar el rango 1 a N deseado y la única manera de no rellenar con ceros es que dicho rango quepa un número entero de veces en el array.

#9 Describe el algoritmo «primero en profundidad» para atravesar un grafo

Primero, cuidado porque se trata de un grafo cualquiera, no de un árbol así que podría haber ciclos. El código en python es algo así:

def depth_first(root):
    # Necesario para evitar visitar dos veces el mismo nodo. Evita ciclos
    if (not root.was_visited):
        visit(root)
        root.was_visited = True

        for child in root.children:
            depth_first(child)

#10 Necesitas comprobar que tu amigo Bob tiene tu número de teléfono correcto pero no le puedes preguntar directamente. Tienes que preguntarle algo en un papel que le darás a Eva quien se lo dará a Bob y te devolverá su respuesta. ¿Qué debes escribir en el papel, a parte de la pregunta, para asegurarte de que Bob codifica el mensaje de manera que Eva no pueda leer tu número de teléfono?

Contestando estrictamente, cuéntale cualquier algoritmo de encriptación asimétrica. Dile que coja tu número y lo codifique de la forma descrita en el papel con la clave indicada en la nota y que escriba el resultado. Tu, con tu clave privada, sabrás desencriptarlo.

Otra forma, bastante original que he leído, es pedirle a Bob que sume los dígitos de tu número de teléfono y que te trate de llamar a una determinada hora. Si la suma no coincide ya sabes que no lo tiene bien y si coincide y te llama a la hora que habeis quedado es que lo tiene bien.

Y eso es todo por el momento. Supongo que me llamarán uno de estos días así que seguiré resolviendo y posteando preguntas que vaya encontrando. Por favor, esto será mucho más divertido si participais así que si teneis soluciones alternativas, pasadlas.