¿Voy a tener suerte? » Ruido blanco

Ayer tuve la oportunidad de que dos ingenieros de Google me hicieran algunas preguntillas (dos entrevistas de 45 minutos), para no olvidarlas (creo que no he olvidado ninguna por ahora) y por si a alguién le interesan las voy a escribir por aquí…

Primera entrevista

• Escribir una estructura de árbol binario y una función que lo recorriera inorder (primero la rama izquierda, luego el nodo, y finalmente la rama derecha).
• Escribir la función para recorrer el árbol inorder sin utilizar recursividad (mi primera solución era recursiva).
• Comentar que métodos utilizaría para separar los artículos relacionados con el deporte entre muchos artículos relacionados con el deporte o no.
• Si tenemos una matriz M×N de la que tenemos que partir de la esquina superior izquierda y llegar a la esquina inferior derecha moviendonos únicamente hacia la derecha y hacia abajo ¿cúal es la longitud mínima del camino?
• Sobre la misma matriz del caso anterior ¿cuál es el número de caminos posibles? (en este me atranqué un poco, pero tiene una interesante solución).

Segunda entrevista

• Si tenemos un array de enteros del que sabemos que más de la mitad (es decir, la mitad más uno, al menos) son el mismo elemento, escribir una función que devuelva el elemento repetido (de este problema comento cosas más abajo, que me llevo mi tiempo).
• Si tenemos un texto en un idioma previamente conocido, pero al que hemos quitado todos los espacios, comentar métodos que se podrían utilizar para volver a obtener los espacios del texto original.

El problema del array

La segunda entrevista solo tiene dos “puntos” porque el primer problema me llevó un tiempo. Lo curioso es que respondí con una solución (que yo considero extraña, como poco) casi al segundo (en plan epifanía o similar): si se ordena el array, el elemento de la mitad del array es el elemento buscado:

# Posibles arrays ordenados existentes
#        ↓ Elemento medio
[a a a a a b c d e]
[a b c d e e e e e]
[a b c c c c c d e]

Solución con complejidad O(1) en memoria, pero O(n log n) en tiempo (por la ordenación). El entrevistador me preguntó si se podría hacer en tiempo O(n). Por supuesto: utilizando un hash (solución en Ruby, aunque en la entrevista utilicé algo entre C y Java):

def find_repeated_number(numbers):
  h = Hash.new(0) # Los elementos que no existan en el hash se inicializan a 0
  numbers.each do |number|
    h[number] += 1
  end
  
  h_keys = h.keys
  max_count = h[h_keys.first]
  max_element = h_keys.first
  h_keys.each do |number|
    max_count, max_element = number, h[number] if max_count < h[number]
  end
  
  return max_element
end

El tiempo tiene complejidad O(n+m) siendo m el número de elementos diferentes del array, pero la complejidad final es de orden O(n). El problema es que esta solución tiene una complejidad en memoria de orden O(m) (debido al hash).

La siguiente pregunta era obvia ¿existe una solución O(n) en tiempo y en memoria? Pues sí existe, pero desde luego no es obvia (de cierto modo aún me pregunto como funciona del todo).

La idea es la siguiente: imaginad que tenemos un array de tres elementos que cumple la condición del problema (es decir, tiene dos elementos iguales y uno diferente): [a a b], [a b a], [b a a]. Si miramos a los dos primeros elementos del array podemos ver que o son diferentes o son iguales. Si son iguales se quedan en el array, pero si son diferentes los podemos eliminar y el array resultante sigue cumpliendo la condición del problema (un array de un elemento siempre cumple la condición del problema).

Se puede comprobar que en arrays más grandes y con más elementos diferentes se pueden seguir eliminando los pares de elementos diferentes según avanzamos en el recorrido del array sin que el array resultante pierda la propiedad impuesta por el problema. Ejemplo con un array de 15 elementos y 5 elementos diferentes:

[2, 2, 4, 2, 3, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 5] # Avanzamos
[2, 2, 4, 3, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 5] # Se eliminan y se retrocede 1
[2, 3, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 5] # Se eliminan
[1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 5] # Se eliminan
[1, 1, 1, 3, 1, 1, 1, 1, 5] # Avanzamos
[1, 1, 1, 3, 1, 1, 1, 1, 5] # Avanzamos
[1, 1, 1, 3, 1, 1, 1, 1, 5] # Se eliminan
[1, 1, 1, 1, 1, 1, 5] # Avanzamos
[1, 1, 1, 1, 1, 1, 5] # Avanzamos
[1, 1, 1, 1, 1, 1, 5] # Avanzamos
[1, 1, 1, 1, 1, 1, 5] # Se eliminan
[1, 1, 1, 1, 1] # El elemento buscado es el 1.

El algoritmo que se puede intuir de proceso anterior es de orden lineal en el tiempo, pero las eliminanciones de los elementos del array podrían hacer que este orden se modificara (a parte de que se destruiría el array). ¿Se puede hacer sin eliminar elementos del array?

Sí, se puede. En el proceso anterior se puede ver que el índice del elemento consultado siempre avanza (a veces dos unidades) excepto en el caso cuando se eliminan elementos que se debe comprobar el siguiente elemento con los que ya hemos superado (2ª y 3ª líneas del ejemplo, aunque podría haber muchos doses antes y se deberían ir comprobando todos). La solución consiste en almacenar el elemento repetido (su valor) y el número de veces que se repitió y comprobar frente a esos valores antes de avanzar.

Mi solución (mejorada frente a la implementación naïve que propuse durante la entrevista, y de nuevo en Ruby):

def find_number(numbers)
  count = 0           # No hay nada
  stored = nil # en nuestro "almacén"
  index = 0
  length = numbers.size
  while (index < length - 1) do
    if (count > 0 && stored == numbers[index]) then
      # Si hay almacén y es igual al elemento, aumentamos el almacén
      count += 1
    elsif (count > 0)
      # Si hay almacén pero es diferente, eliminamos uno del almacén
      count -= 1
    elsif (numbers[index] == numbers[index+1]) then
      # Si no hay almacén y el elemento es el mismo que el anterior…
      stored = numbers[index] # almacenamos el elemento
      count = 1               # con su contador a 1
    else
      # Si los elementos son diferentes saltamos sobre uno
      index += 1
    end
    index += 1 # Siempre avanzamos uno
  end
  
  return count > 0 ? stored : numbers[length-1]
end

Creo que no tiene fallos, y me gustaría pensar que es la forma más sencilla de escribir el algoritmo, pero he sido incapaz de encontrar el problema descrito y solucionado en Internet. Si alguién encuentra un array que no proporcione la salida correcta que me lo comunique e intentaré corregir el algoritmo.

Ver entradas relacionadas

• Por mi podrían haber utilizado otra palabra
• And now for something completely different
• Recuperar canciones de un iPod: manera divertida
• ¡¡¡Me he cruzado con un gato negro!!!
• Con un poquito de suerte