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.

Anuncios

11 comentarios en “Preguntas de entrevista de Google (con respuestas)

    1. Comentarios Random presenta a Ana, con un comentario totalmente fuera de lugar.

      Bueno, como no soy de los que borra comentarios y está bien escrito, aunque sea soez y esté totalmente no relacionado, te lo dejaré ahí pero te transmito que no me hace ninguna gracia.

  1. ¿La tapa de la alcantarilla es posible que tenga relación con aquello de “la esfera contiene el mayor volumen posible con la misma superficie”? La verdad es que mis matemáticas están muy oxidadas y no sé si el círculo hace lo mismo, pero de ser así también ahorraríamos en material para crearlas.

    1. No tiene pinta de que se relacione con la cantidad de material utilizado. De hecho, hacerlas redondas tienda a dejar sobrantes en la plancha madre lo que nos lleva a refundir dicho material y añadirlo al siguiente fundido, lo cual no creo que sea muy caro pero tampoco creo que abarate los costes.

  2. Estoy pensando que el tema del teléfono de Bob es más complejo. Decirle que te llame a tal hora es trampa, ya que si lo tiene mal, llegada esa hora ya no tiene solución. Tienes que conseguir asegurarte de que lo tiene bien, y de que es capaz de corregir un error si lo hay.
    Se me ocurre algo estilo CRC, le pasas una serie de operaciones a realizar con tu número (sin enviar el número) y el resultado que debería dar. Si está bien pensado, y el error que tiene es leve, incluso debería poder corregirlo con la info que le envías.

    1. Esa es facil, encripta tu numero utilizando tu numero como “clave” de encriptacion. Bob debería desencriptarlo con tu número, si el resultado es igual al número lo tiene bien, sino lo tiene mal.

      Número: 5681

      Por ejemplo lo encripto sumando las cifras y haciendo modulo 10.

      5+5 = 10
      6+6 = 12
      8+8 = 16
      1+1 = 2

      Aplico módulo 10 a cada uno y me queda el siguiente numero:

      0262

      Le envio este mensaje a Bob:

      “Restale a cada cifra del siguiente número la cifra correspondiente a mi número, si el resultado es mi número entonces lo tenés bien. El número es 0262. Si te da negativo la suma sumale 10, si te da 10 o mas de 10 restale 10. (Le hace el módulo 10).”

      Entonces Bob hará:

      0-5 = -5
      2-6 = -4
      6-8 = -2
      2-1 = 1

      Sumando 10 a los negativos:

      5
      6
      8
      1

      Listo, le da el mismo número entonces lo tiene bien anotado.

      1. Quizás sea más sencillo pedirle a Bob que nos diga un hash del número que tiene (MD5 por ejemplo). No creo que se pueda utilizar la vulnerabilidad de las colisiones hash en un dato tan pequeño como un número de teléfono.

        De todas formas, la pregunta dice “Necesitas comprobar que tu amigo Bob tiene tu número de teléfono correcto”. Al decir “QUE tiene tu número correcto” y no “SI tiene tu número correcto” me da que pensar que hay que garantizar que a Bob le llegue el número correcto.
        Si es así, no se me ocurre nada que no implique tener una clave pública de Bob para utilizar un cifrado asimétrico.

        Para lo de medir el cambio de contexto, estoy de acuerdo con el planteamiento del autor salvo por lo siguiente:
        Si utilizamos procesos, un cambio de proceso no sólo implica un cambio de contexto sino también un cambio de proceso donde se debe reemplazar toda la imagen del proceso (PID, datos, pila, memoria compartida…).
        Yo creo que habría que utilizar un hilo, donde sí que solamente es necesario un cambio de contexto que es lo que nos piden.

        La idea sería tal como dice el autor:
        1. Obtener timestamp
        2. Crear un hilo y ejecutarlo
        3. El hilo obtiene otro timestamp y calcula la diferencia

        Además los hilos comparten memoria así que acceder al primer timestamp sería trivial.

        De todas formas existe el problema de que no sabemos cómo se va a repartir la CPU para estar seguros de que esas tres operaciones se realizarán de manera atómica ya que si el SO nos quita la ejecución en medio de alguna operación la medición será errónea.
        Supongo que antes habría que darle máxima prioridad al proceso padre, incluso más prioridad que al kernel lo cual no tiene sentido, así que no se me ocurre una manera de llegar a un dato con un margen de error nulo. Habrá que estudiar más POSIX jejeje

        Respecto a la de la alcantarilla he encontrado un post curioso: http://www.ojocientifico.com/4334/por-que-las-tapas-de-las-alcantarillas-son-redondas

        Un saludo! 🙂

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