Se le proporciona un archivo que contiene todos los números posibles en una arquitectura de 32 bits. Faltan 4 números de ese archivo. Encuentra los 4 números que faltan

Esta es una pregunta de entrevista que me he encontrado varias veces, y realmente no estoy seguro de cómo resolverla dado que faltan cuatro números. Estoy familiarizado con los algoritmos para encontrar uno o dos números que faltan, pero no veo una forma de generalizar ninguno de ellos a cuatro.

Ya sea para una entrevista o un trabajo real, su primera prioridad debe ser una solución de trabajo que tenga sentido para usted . Que por lo general significa que debe ofrecer la primera solución que se pueda imaginar que es simple y fácil para usted para explicarle.

Para mí, eso significa ordenar los números y buscar huecos. Pero trabajo en sistemas comerciales y aplicaciones web. ¡No jugueteo con pedacitos, y no quiero que mi equipo lo haga!

Si está entrevistando para un trabajo de bajo nivel, más cercano al metal, la "clasificación" probablemente se encontrará con miradas en blanco. Quieren que te sientas cómodo pensando en cosas y demás. Su primera respuesta debería ser: "Oh, usaría un mapa de bits". (O conjunto de bits o conjunto de bits).

Y luego, de cualquier manera, incluso si da una solución "incorrecta", si su entrevistador (¡o su jefe!) Lo presiona , puede sugerir algunas mejoras o alternativas, centrándose en el área específica de interés del gerente.

• RAM severamente limitada? ¿Menos de 512 MB?
  Clasifíquelo en su lugar, en el disco. Puede utilizar una cantidad de RAM mayoritariamente arbitraria para optimizar y / o ordenar los bloques en el búfer.
• ¿Tiempo limitado?
  ¡Usa esa RAM! La clasificación ya está O(n*log(n)). (O O (n) para un tipo de cubo entero!)
• Mantenibilidad?
  ¿Qué podría ser más fácil que ordenar?
• ¿No demuestra conocimiento de banderas / campos de bits? ( BitSet/ BitMap/ BitArray)
  Bueno, está bien ... adelante y usa a BitArraypara marcar los "números encontrados" Y luego escanea por 0's.
• Complejidad predecible "en tiempo real"?
  Use la solución de mapa de bits. Es un solo paso sobre el archivo y otro paso sobreBitArray/BitSet(para encontrar el0's). Eso esO(n), creo!

O lo que sea.

Aborde las preocupaciones que realmente tiene. Simplemente resuelva el problema primero, utilizando soluciones ingenuas si es necesario. No pierdas el tiempo de todos abordando preocupaciones que aún no existen.

Como se trata de un archivo, supongo que puede hacer varios pases. Primero cree una matriz de 256 contadores, itere sobre el archivo y para cada número incremente el contador indexado como el primer byte del número. Cuando haya terminado, la mayoría de los contadores deben estar en 2 ^ 24, pero 1 hasta 4 contadores deben tener valores más bajos. Cada uno de estos índices representa un primer byte de uno de los números faltantes (si hay menos de 4 es porque varios números faltantes comparten el mismo primer byte).

Para cada uno de estos índices, cree otra matriz de 256 contadores y realice una segunda pasada en el archivo. Esta vez, si el primer byte es uno de los valores anteriores, incremente un contador en su matriz en función del segundo byte. Cuando haya terminado, busque nuevamente los contadores inferiores a 2 ^ 16, y obtendrá el segundo byte de los números que faltan, cada uno de los cuales coincide con su primer byte.

Vuelva a hacerlo para el tercer byte (tenga en cuenta que necesita un máximo de 4 matrices en cada pasada, aunque cada byte puede ir seguido de hasta 4 bytes diferentes) y para el cuarto byte, y ha encontrado todos los números que faltan.

Complejidad del tiempo - Complejidad del O(n * log n)
espacio - ¡ constante !

Editar:

En realidad, consideré n=2^32que era el parámetro, pero el número de números faltantes k=4también es un parámetro. Suponiendo que k<<nesto significa que la complejidad del espacio es O(k).

Actualizar:

Solo por diversión (y porque actualmente estoy tratando de aprender Rust) lo implementé en Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . Elegí tener una representación textual, ya que uno la ejecutará con ~ 2 ^ 32 números ...

Si esto fuera Java, podría usar un BitSet. Bueno, dos de ellos, porque no pueden contener todos los números de 32 bits. Código esquelético, quizás con errores:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Luego use BitSet.nextClearBit()para encontrar quién falta.

Nota añadida mucho más tarde:

Tenga en cuenta que con este algoritmo, es bastante fácil ejecutar la parte que consume mucho tiempo en paralelo . Digamos que el archivo original se ha dividido en cuatro partes más o menos iguales. Asigne 4 pares de BitSets (2GB, aún manejables).

1. Tenga cuatro subprocesos, en paralelo, cada uno procesa un archivo en su propio par de BitSets.
2. Cuando termine, regrese a un solo subproceso, o Bitsets (tiempo trivial), luego llame a nextClearBit cuatro veces (también tiempo bastante trivial).

Esperaría que la E / S siga siendo el paso de limitación de velocidad, pero si mágicamente todos los números estuvieran en la memoria, realmente podría acelerar las cosas.

Esta pregunta se puede resolver utilizando una matriz de bits (verdadero / falso). Esta debería ser la estructura más eficiente para contener las respuestas para todos los números usando el índice de la matriz para contener si se encontró ese número en particular.

DO#

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Luego, simplemente repita la matriz y para aquellos valores que aún son falsos, no están en el archivo.

Podría dividir el archivo en fragmentos más pequeños, pero pude asignar una matriz de tamaño máximo int32 (2147483647) en mi computadora portátil de 16.0 GB con Windows 7 (64 bits).

Incluso si no estuviera ejecutando 64 bits, podría asignar matrices de bits más pequeñas. Preprocesaría el archivo creando un conjunto de archivos más pequeños, cada uno con un rango de [0-64000] [64001-128000], etc., números que serían adecuados para los recursos ambientales disponibles. Revise el archivo grande y escriba cada número en su archivo de conjunto correspondiente. Luego procese cada archivo más pequeño. Llevaría un poco más de tiempo debido al paso de preprocesamiento, pero esto evitaría las limitaciones de recursos si hubiera recursos limitados.

Como se trata de una pregunta de entrevista, le mostraría al entrevistador cierta comprensión sobre las limitaciones. Entonces, ¿qué significa "todos los números posibles"? ¿Es realmente 0 ... 2 <(32-1) como todos adivinan? Las arquitecturas habituales de 32 bits pueden funcionar con muchos más que solo números de 32 bits. Es solo una cuestión de representación, obviamente.

¿Tiene que resolverse en un sistema de 32 bits, o es más bien una parte de la restricción de números? Por ejemplo, un sistema típico de 32 bits no podrá cargar el archivo en la RAM de una vez. También mencionaría que un sistema de 32 bits a menudo no podrá tener un archivo que contenga todos los números debido a la limitación del tamaño del archivo. Bueno, a menos que tenga una codificación inteligente, como "Todos los números excepto esos cuatro", en cuyo caso el problema se resuelve trivialmente.

Pero si realmente quieres entender la pregunta como "Dado un archivo con todos los números del 0 ... 2 ^ (32-1) excepto algunos, dame los que faltan" (¡y este es un gran si !), Entonces Hay muchas formas de resolverlo.

Trivial pero no factible: para cada número posible, escanee el archivo y vea si está allí.

Con 512 MB de RAM y un archivo de paso único: marque cada número (= bit establecido en ese índice) leído del archivo, y luego pase la RAM una vez y vea los que faltan.

Un enfoque que es fácil de recordar y fácil de articular en una entrevista sería utilizar el hecho de que si observa todos los números en N bits, cada bit se establecerá exactamente en la mitad de esos valores y no en la otra mitad .

Si itera sobre todos los valores en el archivo y mantiene 32 recuentos de los valores al final, terminará con 32 valores que son exactamente (2 ^ 32/2) o un poco menos que ese valor. La diferencia entre el máximo (2 ^ 32/2) y el total le da el total de bits establecidos en cada posición de los valores faltantes.

Una vez que tenga eso, puede determinar todos los conjuntos posibles de 4 valores que podrían dar esos totales. Dado eso, puede revisar los valores en el archivo nuevamente buscando cualquier valor que sea parte de esas combinaciones. Cuando encuentra uno, las combinaciones que contienen ese valor se eliminan como posibilidades. Una vez que solo le quede una combinación posible, tendrá su respuesta.

Por ejemplo, usando un mordisco, tiene los siguientes valores:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

El total de bits establecidos en cada posición es:

7867

Restando los de 8 (4 ^ 2/2) obtenemos:

1021

Lo que significa que existen los siguientes conjuntos posibles de 4 valores:

1000
0000
0011
0010

1010
0001
0010
0000

(perdóname si me he perdido alguno, solo estoy haciendo esto de vista)

Y luego, mirando nuevamente los números originales, encontramos 1010 de inmediato, lo que significa que el primer conjunto fue la respuesta.

Suponiendo que el archivo está ordenado por números crecientes:

Asegúrese de que la sangría contenga números (2³²-4).
Ahora, si el archivo estuviera completo (o si los 4 números faltantes fueran los 4 últimos), leer cualquier palabra en el archivo en la posición N devolvería el valor correspondiente N.

Utilice una búsqueda de dicotomía en las posiciones [0..2³²-4-1) para buscar el primer número no esperado X1.
Una vez que encuentre el primer número que falta, realice una búsqueda de dichtotomía nuevamente en las posiciones [X1 .. (2³²-4-1)] para encontrar el segundo que falta, X2: esta vez, leer una palabra en la posición N debería devolver el valor correspondiente N-1 si no hubiera más números faltantes (ya que pasó un número faltante).
Iterar igualmente para los dos números restantes. En la tercera iteración, leer la palabra en la posición N debería devolver N-2, y en la cuarta, debería devolver N-3.

Advertencia: no he probado esto. Pero creo que debería funcionar. :)

Ahora en la vida real, estoy de acuerdo con otras respuestas: las primeras preguntas serían sobre el medio ambiente. ¿Tenemos disponibilidad de RAM (cuánto), es el archivo en un dispositivo de almacenamiento de acceso directo, es una operación de una sola vez (no se requiere optimización) o crítica (cuenta de cada ciclo), tenemos una utilidad de clasificación externa disponible , etc.
Luego encuentre un compromiso aceptable para el contexto. Esto al menos muestra que comienza a analizar el problema antes de buscar un algoritmo.

Como con todas las preguntas estándar, la solución es buscarlas en Google antes de la entrevista.

Esta pregunta y sus variaciones tienen una respuesta 'correcta' muy definida que involucra XORing todos los números. Se supone que muestra que entiendes índices en bases de datos o algo así. Por lo tanto, cero puntos para cualquier "podría funcionar pero no lo que dice en el papel" responden de inmediato

En el lado positivo, hay un conjunto finito de estas preguntas. Unas pocas horas de revisión te harán ver como un genio. Solo recuerda fingir que lo estás resolviendo en tu cabeza.

Editar. Ahh parece que para 4 hay un enfoque diferente que XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Editar. Votantes: Esta es una solución de libro de texto O (n) publicada para el problema exacto establecido en el OP.