algorithm - lyrics - Encuentra un número entero no entre cuatro mil millones dados

algorithms book (30)

Elimine los espacios en blanco y los caracteres no numéricos del archivo y adjúntelos 1. Su archivo ahora contiene un solo número que no figura en el archivo original.

Desde Reddit por Carbonetc.

Es una pregunta de entrevista:

Dado un archivo de entrada con cuatro mil millones de enteros, proporcione un algoritmo para generar un entero que no esté contenido en el archivo. Supongamos que tiene 1 GB de memoria. Haga un seguimiento de lo que haría si solo tuviera 10 MB de memoria.

Mi análisis:

El tamaño del archivo es 4 × 10 ⁹ × 4 bytes = 16 GB.

Podemos hacer una clasificación externa, por lo que podemos conocer el rango de los enteros. Mi pregunta es ¿cuál es la mejor manera de detectar el número entero faltante en los grandes conjuntos enteros ordenados?

Mi comprensión (después de leer todas las respuestas):

Suponiendo que estamos hablando de enteros de 32 bits. Hay 2 ^ 32 = 4 * 10 ⁹ enteros distintos.

Caso 1: tenemos 1 GB = 1 * 10 ⁹ * 8 bits = 8 mil millones de bits de memoria. Solución: si usamos un bit que representa un entero distinto, es suficiente. no necesitamos orden Implementación:

int radix = 8; byte[] bitfield = new byte[0xffffffff/radix]; void F() throws FileNotFoundException{ Scanner in = new Scanner(new FileReader("a.txt")); while(in.hasNextInt()){ int n = in.nextInt(); bitfield[n/radix] |= (1 << (n%radix)); } for(int i = 0; i< bitfield.lenght; i++){ for(int j =0; j<radix; j++){ if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j); } } }

Caso 2: 10 MB de memoria = 10 * 10 ⁶ * 8 bits = 80 millones de bits

Solution: For all possible 16-bit prefixes, there are 2^16 number of integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build 65536 buckets. For each bucket, we need 4 bytes holding all possibilities because the worst case is all the 4 billion integers belong to the same bucket. step1: Build the counter of each bucket through the first pass through the file. step2: Scan the buckets, find the first one who has less than 65536 hit. step3: Build new buckets whose high 16-bit prefixes are we found in step2 through second pass of the file step4: Scan the buckets built in step3, find the first bucket which doesnt have a hit. The code is very similar to above one.

Conclusión: disminuimos la memoria al aumentar el paso del archivo.

Una aclaración para aquellos que llegan tarde: la pregunta, como se hizo, no dice que exista exactamente un entero que no esté contenido en el archivo, al menos no es así como la mayoría de la gente lo interpreta. Sin embargo, muchos comentarios en el hilo de comentarios se refieren a esa variación de la tarea. Desafortunadamente, el comentario que lo introdujo en el hilo de comentarios fue posteriormente eliminado por su autor, por lo que ahora parece que las respuestas huérfanas simplemente lo malinterpretaron todo. Es muy confuso. Lo siento.

¿Por qué hacerlo tan complicado? ¿Pides un entero no presente en el archivo?

De acuerdo con las reglas especificadas, lo único que necesita almacenar es el entero más grande que haya encontrado hasta ahora en el archivo. Una vez que se haya leído el archivo completo, devuelva un número 1 mayor que eso.

No hay riesgo de golpear maxint ni nada, porque de acuerdo con las reglas, no hay ninguna restricción al tamaño del número entero o al número devuelto por el algoritmo.

Dado que el problema no especifica que tenemos que encontrar el número más pequeño posible que no esté en el archivo, podríamos generar un número que sea más largo que el archivo de entrada. :)

Esto se puede resolver en muy poco espacio usando una variante de búsqueda binaria.

Comience con el rango permitido de números, 0 a 4294967295 .
Calcula el punto medio.
Recorra el archivo y cuente cuántos números eran iguales, menores o mayores que el valor del punto medio.
Si no hay números iguales, ya está hecho. El número del punto medio es la respuesta.
De lo contrario, elija el rango que tenga menos números y repita desde el paso 2 con este nuevo rango.

Esto requerirá hasta 32 exploraciones lineales a través del archivo, pero solo usará unos pocos bytes de memoria para almacenar el rango y los conteos.

Esta es esencialmente la misma que la solución de Henning , excepto que usa dos contenedores en lugar de 16k.

Los algoritmos estadísticamente informados resuelven este problema utilizando menos pases que los enfoques deterministas.

Si se permiten enteros muy grandes, entonces se puede generar un número que probablemente sea único en el tiempo O (1). Un entero pseudoaleatorio de 128 bits como un GUID solo colisionará con uno de los cuatro mil millones de enteros existentes en el conjunto en menos de uno de cada 64 mil millones de billones de casos.

Si los enteros están limitados a 32 bits, entonces se puede generar un número que probablemente sea único en una sola pasada usando mucho menos de 10 MB. Las probabilidades de que un entero pseudoaleatorio de 32 bits colisione con uno de los 4 mil millones de enteros existentes son aproximadamente el 93% (4e9 / 2 ^ 32). Las probabilidades de que 1000 enteros pseudoaleatorios colisionen son menos de uno en 12,000 billones de billones (probabilidad de una colisión ^ 1000). Entonces, si un programa mantiene una estructura de datos que contiene 1000 candidatos pseudoaleatorios e itera a través de los enteros conocidos, eliminando las coincidencias de los candidatos, es casi seguro encontrar al menos un entero que no está en el archivo.

Para la variante de RAM de 1 GB puede usar un vector de bits. Debe asignar 4 mil millones de bits == 500 MB byte array. Para cada número que lea de la entrada, establezca el bit correspondiente a ''1''. Una vez que haya terminado, repita la iteración sobre los bits, encuentre el primero que aún sea ''0''. Su índice es la respuesta.

Pueden estar buscando para ver si ha oído hablar de un filtro Bloom probabilístico que puede determinar de manera muy eficiente si un valor no es parte de un conjunto grande (pero solo puede determinar con alta probabilidad que es un miembro del conjunto).

Según la redacción actual de la pregunta original, la solución más sencilla es:

Encuentre el valor máximo en el archivo, luego agregue 1.

Si asumimos que el rango de números siempre será 2 ^ n (una potencia par de 2), entonces la función exclusiva o funcionará (como lo muestra otro póster). En cuanto a por qué, vamos a demostrarlo:

La teoría

Dado cualquier rango de enteros basado en 0 que tenga 2^n elementos con un elemento faltante, puede encontrar ese elemento faltante simplemente al juntar los valores conocidos para obtener el número faltante.

La prueba

Veamos n = 2. Para n = 2, podemos representar 4 enteros únicos: 0, 1, 2, 3. Tienen un patrón de bits de:

0 - 00
1 - 01
2 - 10
3 - 11

Ahora, si miramos, cada bit se establece exactamente dos veces.Por lo tanto, dado que se establece un número par de veces, y exclusivo -o de los números arrojará 0. Si falta un solo número, el exclusivo- o producirá un número que, si se excluye con el número faltante, dará como resultado 0. Por lo tanto, el número faltante y el número de origen exclusivo resultante son exactamente los mismos. Si eliminamos 2, el xor resultante será 10(o 2).

Ahora, veamos n + 1. Vamos a llamar al número de veces que cada bit se pone en n, xy el número de veces que cada bit se pone en n+1 y. El valor de yserá igual a y = x * 2porque hay xelementos con el n+1bit establecido en 0, y los xelementos con el n+1bit establecido en 1. Y como 2xsiempre será par, n+1siempre habrá un conjunto de bits un número par de veces.

Por lo tanto, dado que n=2funciona y n+1funciona, el método xor funcionará para todos los valores de n>=2.

El algoritmo para rangos basados en 0

Esto es bastante simple. Utiliza 2 * n bits de memoria, por lo que para cualquier rango <= 32, funcionarán 2 enteros de 32 bits (ignorando cualquier memoria consumida por el descriptor de archivo). Y hace una sola pasada del archivo.

long supplied = 0; long result = 0; while (supplied = read_int_from_file()) { result = result ^ supplied; } return result;

El algoritmo para rangos de base arbitraria

Este algoritmo funcionará para rangos de cualquier número inicial a cualquier número final, siempre que el rango total sea igual a 2 ^ n ... Esto básicamente vuelve a basar el rango para tener el mínimo en 0. Pero requiere 2 pases a través del archivo (el primero en tomar el mínimo, el segundo en calcular el int faltante).

long supplied = 0; long result = 0; long offset = INT_MAX; while (supplied = read_int_from_file()) { if (supplied < offset) { offset = supplied; } } reset_file_pointer(); while (supplied = read_int_from_file()) { result = result ^ (supplied - offset); } return result + offset;

Rangos Arbitrarios

Podemos aplicar este método modificado a un conjunto de rangos arbitrarios, ya que todos los rangos cruzarán una potencia de 2 ^ n al menos una vez. Esto funciona solo si falta un solo bit. Toma 2 pases de un archivo no clasificado, pero encontrará el número faltante solo cada vez:

long supplied = 0; long result = 0; long offset = INT_MAX; long n = 0; double temp; while (supplied = read_int_from_file()) { if (supplied < offset) { offset = supplied; } } reset_file_pointer(); while (supplied = read_int_from_file()) { n++; result = result ^ (supplied - offset); } // We need to increment n one value so that we take care of the missing // int value n++ while (n == 1 || 0 != (n & (n - 1))) { result = result ^ (n++); } return result + offset;

Básicamente, vuelve a basar el rango alrededor de 0. Luego, cuenta el número de valores sin clasificar que se agregan a medida que calcula la exclusiva o. Luego, agrega 1 al conteo de valores no clasificados para cuidar el valor faltante (cuente el faltante). Luego, mantenga xoring el valor n, incrementado en 1 cada vez hasta que n sea una potencia de 2. El resultado se vuelve a basar en la base original. Hecho.

Aquí está el algoritmo que probé en PHP (usando una matriz en lugar de un archivo, pero el mismo concepto):

function find($array) { $offset = min($array); $n = 0; $result = 0; foreach ($array as $value) { $result = $result ^ ($value - $offset); $n++; } $n++; // This takes care of the missing value while ($n == 1 || 0 != ($n & ($n - 1))) { $result = $result ^ ($n++); } return $result + $offset; }

Alimentado en una matriz con cualquier rango de valores (he probado incluyendo negativos) con uno dentro de ese rango que falta, encontró el valor correcto cada vez.

Otro enfoque

Ya que podemos usar la clasificación externa, ¿por qué no solo buscar una brecha? Si asumimos que el archivo está ordenado antes de ejecutar este algoritmo:

long supplied = 0; long last = read_int_from_file(); while (supplied = read_int_from_file()) { if (supplied != last + 1) { return last + 1; } last = supplied; } // The range is contiguous, so what do we do here? Let''s return last + 1: return last + 1;

Si le falta un entero del rango [0, 2 ^ x - 1], entonces solo xo todos ellos juntos. Por ejemplo:

>>> 0 ^ 1 ^ 3 2 >>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7 5

(Sé que esto no responde exactamente a la pregunta, pero es una buena respuesta a una pregunta muy similar).

Si no hay un límite de tamaño, la forma más rápida es tomar la longitud del archivo y generar la longitud del archivo + 1 número de dígitos aleatorios (o simplemente "11111 ..." s). Ventaja: ni siquiera necesita leer el archivo, y puede minimizar el uso de memoria casi a cero. Desventaja: Imprimirás miles de millones de dígitos.

Sin embargo, si el único factor era minimizar el uso de la memoria, y nada más es importante, esta sería la solución óptima. Incluso podría obtener un premio por "el peor abuso de las reglas".

Si son enteros de 32 bits (probablemente de la elección de ~ 4 mil millones de números cercanos a 2 ^ 32), su lista de 4 mil millones de números ocupará como máximo el 93% de los enteros posibles (4 * 10 ^ 9 / (2 ^ 32)). Entonces, si crea una matriz de bits de 2 ^ 32 bits con cada bit inicializado a cero (que ocupará 2 ^ 29 bytes ~ 500 MB de RAM; recuerde un byte = 2 ^ 3 bits = 8 bits), lea su lista entera y para cada conjunto int el elemento de matriz de bits correspondiente de 0 a 1; y luego lea la matriz de bits y devuelva el primer bit que aún es 0.

En el caso de que tenga menos RAM (~ 10 MB), esta solución debe modificarse ligeramente. 10 MB ~ 83886080 bits todavía es suficiente para hacer una matriz de bits para todos los números entre 0 y 83886079. Por lo tanto, puede leer su lista de caracteres; y solo registre los #s que están entre 0 y 83886079 en su matriz de bits. Si los números se distribuyen al azar; con una probabilidad abrumadora (difiere en un 100% en aproximadamente 10^-2592069 ) encontrará un int faltante. De hecho, si solo elige los números del 1 al 2048 (con solo 256 bytes de RAM) todavía encontrará un número faltante en un porcentaje abrumador (99.9999999999999999999999999999999999999999999999999999999999999999%) del tiempo.

Pero digamos que en lugar de tener unos 4 mil millones de números; tenías algo así como 2 ^ 32 - 1 números y menos de 10 MB de RAM; por lo tanto, cualquier rango pequeño de entradas solo tiene una pequeña posibilidad de no contener el número.

Si tuviera la garantía de que cada int en la lista era único, podría sumar los números y restar la suma faltando un # a la suma completa (1/2) (2 ^ 32) (2 ^ 32 - 1) = 9223372034707292160 para encontrar el int perdido Sin embargo, si se produce un int dos veces, este método fallará.

Sin embargo, siempre puedes dividir y conquistar. Un método ingenuo sería leer la matriz y contar el número de números que están en la primera mitad (0 a 2 ^ 31-1) y la segunda mitad (2 ^ 31, 2 ^ 32). Luego elija el rango con menos números y repita dividiendo ese rango a la mitad. (Diga que si hubiera dos números menos en (2 ^ 31, 2 ^ 32) entonces su próxima búsqueda contaría los números en el rango (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32). Continúe repitiendo hasta que encuentre un rango con cero números y tenga su respuesta. Debe tomar O (lg N) ~ 32 lecturas a través de la matriz.

Ese método era ineficiente. Solo utilizamos dos enteros en cada paso (o aproximadamente 8 bytes de RAM con un entero de 4 bytes (32 bits)). Un método mejor sería dividir en sqrt (2 ^ 32) = 2 ^ 16 = 65536 intervalos, cada uno con 65536 números en un intervalo. Cada bin requiere 4 bytes para almacenar su conteo, por lo que necesita 2 ^ 18 bytes = 256 kB. Entonces, la casilla 0 es (0 a 65535 = 2 ^ 16-1), la bandeja 1 es (2 ^ 16 = 65536 a 2 * 2 ^ 16-1 = 131071), la bandeja 2 es (2 * 2 ^ 16 = 131072 a 3 * 2 ^ 16-1 = 196607). En python tendrías algo como:

import numpy as np nums_in_bin = np.zeros(65536, dtype=np.uint32) for N in four_billion_int_array: nums_in_bin[N // 65536] += 1 for bin_num, bin_count in enumerate(nums_in_bin): if bin_count < 65536: break # we have found an incomplete bin with missing ints (bin_num)

Lea la lista de enteros de ~ 4 billones; y cuente la cantidad de entradas que caen en cada una de las 2 ^ 16 bandejas y encuentre una papelera incompleta que no tenga todos los 65536 números. Luego lees de nuevo la lista de enteros de 4 billones; pero esta vez solo note cuando los enteros están en ese rango; Volteando un poco cuando los encuentres.

del nums_in_bin # allow gc to free old 256kB array from bitarray import bitarray my_bit_array = bitarray(65536) # 32 kB my_bit_array.setall(0) for N in four_billion_int_array: if N // 65536 == bin_num: my_bit_array[N % 65536] = 1 for i, bit in enumerate(my_bit_array): if not bit: print bin_num*65536 + i break

Una discusión detallada sobre este problema ha sido discutida en Jon Bentley "Columna 1. Rompiendo la ostra" Programando Perlas Addison-Wesley pp.3-10

Bentley discute varios enfoques, incluyendo la clasificación externa, Combinar clasificación usando varios archivos externos, etc., pero el mejor método que Bentley sugiere es un algoritmo de un solo paso que usa campos de bits , que con humor llama "Wonder Sort" :) Llegando al problema, 4 mil millones Los números se pueden representar en:

4 billion bits = (4000000000 / 8) bytes = about 0.466 GB

El código para implementar el conjunto de bits es simple: (tomado de la página de soluciones )

#define BITSPERWORD 32 #define SHIFT 5 #define MASK 0x1F #define N 10000000 int a[1 + N/BITSPERWORD]; void set(int i) { a[i>>SHIFT] |= (1<<(i & MASK)); } void clr(int i) { a[i>>SHIFT] &= ~(1<<(i & MASK)); } int test(int i){ return a[i>>SHIFT] & (1<<(i & MASK)); }

El algoritmo de Bentley hace una sola pasada sobre el archivo, set el bit apropiado en la matriz y luego examina esta matriz utilizando la macro de test arriba para encontrar el número faltante.

Si la memoria disponible es inferior a 0,466 GB, Bentley sugiere un algoritmo de K-pass, que divide la entrada en rangos dependiendo de la memoria disponible. Para tomar un ejemplo muy simple, si solo estaba disponible 1 byte (es decir, memoria para manejar 8 números) y el rango era de 0 a 31, lo dividimos en rangos de 0 a 7, 8-15, 16-22, etc. y manejar este rango en cada uno de 32/8 = 4 pases.

HTH.

Utilice un BitSet . 4 mil millones de enteros (asumiendo hasta 2 ^ 32 enteros) empaquetados en un BitSet a 8 por byte es 2 ^ 32/2 ^ 3 = 2 ^ 29 = aprox. 0.5 Gb.

Para agregar un poco más de detalles, cada vez que lea un número, establezca el bit correspondiente en el BitSet. Luego, haga un pase sobre el BitSet para encontrar el primer número que no está presente. De hecho, puede hacer esto con la misma eficacia al seleccionar repetidamente un número aleatorio y probar si está presente.

En realidad, BitSet.nextClearBit (0) le dirá el primer bit no establecido.

Al observar la API de BitSet, parece que solo es compatible con 0..MAX_INT, por lo que es posible que necesite 2 BitSets, uno para los números + ve y otro para los números, pero los requisitos de memoria no cambian.

EDICIÓN Ok, esto no fue muy pensado ya que asume que los enteros en el archivo siguen alguna distribución estática. Aparentemente no necesitan hacerlo, pero incluso entonces uno debería intentar esto:

Hay ≈4.3 mil millones de enteros de 32 bits. No sabemos cómo se distribuyen en el archivo, pero el peor de los casos es el que tiene la mayor entropía de Shannon: una distribución equitativa. En este caso, la probabilidad de que un entero no se produzca en el archivo es

((2³²-1) / 2³²) ⁴ ⁰⁰⁰ ⁰⁰⁰ ≈ .4

Cuanto más baja es la entropía de Shannon, mayor es la probabilidad de que llegue al promedio, pero incluso en este caso peor, tenemos una probabilidad del 90% de encontrar un número que no ocurra después de 5 intentos con enteros aleatorios. Simplemente cree dichos números con un generador pseudoaleatorio, guárdelos en una lista. Luego lee int after int y compáralo con todas tus conjeturas. Cuando haya una coincidencia, elimine esta entrada de la lista. Después de haber revisado todo el archivo, es probable que le quede más de una conjetura. Usa cualquiera de ellos. En el evento raro (10% incluso en el peor de los casos) en el que no queda ninguna conjetura, obtenga un nuevo conjunto de enteros aleatorios, quizás más esta vez (10-> 99%).

Consumo de memoria: unas pocas docenas de bytes, complejidad: O (n), sobrecarga: es posible que la mayor parte del tiempo se dedique a los accesos inevitables al disco duro en lugar de comparar ints de todos modos.

El peor de los casos reales, cuando no asumimos una distribución estática, es que cada número entero se produce como máximo. una vez, porque entonces solo 1 - 4000000000 / 2³² ≈ 6% de todos los enteros no aparecen en el archivo. Así que necesitarás algunas conjeturas más, pero eso no costará grandes cantidades de memoria.

Eliminación de bits

Una forma es eliminar los bits, sin embargo, esto podría no producir un resultado (es probable que no lo haga). Psuedocode:

long val = 0xFFFFFFFFFFFFFFFF; // (all bits set) foreach long fileVal in file { val = val & ~fileVal; if (val == 0) error; }

Bit Counts

Mantenga un registro de los recuentos de bits; y usa los bits con las cantidades mínimas para generar un valor. De nuevo esto no tiene garantía de generar un valor correcto.

Logica de rango

Mantenga un registro de los rangos ordenados de una lista (ordenados por inicio). Un rango está definido por la estructura:

struct Range { long Start, End; // Inclusive. } Range startRange = new Range { Start = 0x0, End = 0xFFFFFFFFFFFFFFFF };

Ir a través de cada valor en el archivo y tratar de eliminarlo del rango actual. Este método no tiene garantías de memoria, pero debería funcionar bastante bien.

Suponiendo que "entero" significa 32 bits : tener 10 MB de espacio es más que suficiente para que cuente cuántos números hay en el archivo de entrada con cualquier prefijo de 16 bits dado, para todos los posibles prefijos de 16 bits en una sola pasada el archivo de entrada. Al menos uno de los cubos será golpeado menos de 2 ^ 16 veces. Haga una segunda pasada para averiguar cuál de los posibles números de ese grupo ya se está utilizando.

Si significa más de 32 bits, pero aún de tamaño acotado : haga lo mismo que antes, ignorando todos los números de entrada que caigan fuera del rango de 32 bits (firmado o sin firmar; su elección).

Si "entero" significa entero matemático : lea la entrada una vez y haga un seguimiento de la longitud del ~~número más grande del número más~~ largo que haya visto. Cuando haya terminado, envíe ~~el máximo más uno~~ un número aleatorio que tenga un dígito más. (Uno de los números en el archivo puede ser un bignum que toma más de 10 MB para representar exactamente, pero si la entrada es un archivo, al menos puede representar la longitud de cualquier cosa que se ajuste).

Como Ryan lo dijo básicamente, ordena el archivo y luego repasa los enteros y cuando se omite un valor allí, lo tienes :)

EDITAR en downvoters: el OP mencionó que el archivo podría ordenarse por lo que este es un método válido.

Creo que este es un problema resuelto (ver más arriba), pero hay un caso secundario interesante que se debe tener en cuenta porque puede que se le pregunte:

Si hay exactamente 4,294,967,295 (2 ^ 32 - 1) enteros de 32 bits sin repeticiones, y por lo tanto solo falta uno, hay una solución simple.

Inicie un total acumulado en cero, y para cada entero en el archivo, agregue ese entero con desbordamiento de 32 bits (efectivamente, runningTotal = (runningTotal + nextInteger)% 4294967296). Una vez completado, agregue 4294967296/2 al total acumulado, nuevamente con un desbordamiento de 32 bits. Resta esto de 4294967296, y el resultado es el entero que falta.

El problema de "solo falta un entero" puede resolverse con una sola ejecución y solo 64 bits de RAM dedicados a los datos (32 para el total acumulado, 32 para leer en el siguiente entero).

Corolario: la especificación más general es extremadamente simple de igualar si no nos preocupa la cantidad de bits que debe tener el resultado entero. Simplemente generamos un número entero lo suficientemente grande como para que no pueda estar contenido en el archivo que se nos da. De nuevo, esto ocupa una memoria RAM absolutamente mínima. Ver el pseudocódigo.

# Grab the file size fseek(fp, 0L, SEEK_END); sz = ftell(fp); # Print a ''2'' for every bit of the file. for (c=0; c<sz; c++) { for (b=0; b<4; b++) { print "2"; } }

Mientras estemos haciendo respuestas creativas, aquí hay otra.

Utilice el programa de clasificación externa para ordenar el archivo de entrada numéricamente. Esto funcionará para cualquier cantidad de memoria que pueda tener (usará el almacenamiento de archivos si es necesario). Lea el archivo ordenado y muestre el primer número que falta.

Para la restricción de memoria de 10 MB:

Convertir el número a su representación binaria.
Crea un árbol binario donde izquierda = 0 y derecha = 1.
Inserta cada número en el árbol usando su representación binaria.
Si ya se ha insertado un número, las hojas ya se habrán creado.

Cuando termine, simplemente tome una ruta que no se haya creado antes para crear el número solicitado.

4 mil millones de números = 2 ^ 32, lo que significa que 10 MB podrían no ser suficientes.

EDITAR

Es posible una optimización, si se han creado dos hojas finales y tienen un padre común, entonces se pueden eliminar y el padre se marca como una solución. Esto corta ramas y reduce la necesidad de memoria.

Editar II

No hay necesidad de construir el árbol completamente también. Solo necesitas construir ramas profundas si los números son similares. Si cortamos ramas también, entonces esta solución podría funcionar de hecho.

Puede usar marcas de bit para marcar si un entero está presente o no.

Después de recorrer todo el archivo, escanee cada bit para determinar si el número existe o no.

Suponiendo que cada entero sea de 32 bits, cabrán convenientemente en 1 GB de RAM si se realiza el marcado de bits.

Solo para completar, aquí hay otra solución muy simple, que probablemente demorará mucho tiempo en ejecutarse, pero usa muy poca memoria.

Deje que todos los enteros posibles sean el rango de int_mina int_max, y bool isNotInFile(integer)una función que devuelve verdadero si el archivo no contiene un cierto número entero y falso lo demás (mediante la comparación de que ciertos entero con cada número entero en el archivo)

for (integer i = int_min; i <= int_max; ++i) { if (isNotInFile(i)) { return i; } }

Voy a responder a la versión de 1 GB:

No hay suficiente información en la pregunta, por lo que haré algunas suposiciones primero:

El número entero es de 32 bits con un rango de -2,147,483,648 a 2,147,483,647.

Pseudo-código:

var bitArray = new bit[4294967296]; // 0.5 GB, initialized to all 0s. foreach (var number in file) { bitArray[number + 2147483648] = 1; // Shift all numbers so they start at 0. } for (var i = 0; i < 4294967296; i++) { if (bitArray[i] == 0) { return i - 2147483648; } }

2 ^{128 * 10 ¹⁸} + 1 (que es (2 ⁸ ) ^{16 * 10 ¹⁸} + 1): ¿no puede ser una respuesta universal para hoy? Esto representa un número que no se puede mantener en un archivo de 16 EB, que es el tamaño máximo de archivo en cualquier sistema de archivos actual.

Por alguna razón, tan pronto como leí este problema, pensé en la diagonalización. Estoy asumiendo enteros arbitrariamente grandes.

Lea el primer número. A la izquierda, rellene con cero bits hasta que tenga 4 mil millones de bits. Si el primer bit (orden alto) es 0, salida 1; de lo contrario, salida 0. (Realmente no tiene que usar el pad izquierdo: simplemente genera un 1 si no hay suficientes bits en el número). Haga lo mismo con el segundo número, excepto que use el segundo bit. Continuar a través del archivo de esta manera. Obtendrá un número de 4 billones de bits un bit a la vez, y ese número no será el mismo que cualquier otro en el archivo. Prueba: era el mismo que el número n, entonces estarían de acuerdo en el nth bit, pero no lo hacen por construcción.

Pregunta de truco, a menos que haya sido citado incorrectamente. Solo lea el archivo una vez para obtener el número entero máximo ny regrese n+1.

Por supuesto, necesitaría un plan de respaldo en caso de n+1que se desborde un entero.

Si no asume la restricción de 32 bits, simplemente devuelva un número de 64 bits generado aleatoriamente (o 128 bits si es un pesimista). La posibilidad de colisión es 1 in 2^64/(4*10^9) = 4611686018.4(aproximadamente 1 en 4 mil millones). ¡Tendrías razón la mayor parte del tiempo!

(Bromeando ... algo así.)

Verifique el tamaño del archivo de entrada, luego emita cualquier número que sea demasiado grande para ser representado por un archivo de ese tamaño. Esto puede parecer un truco barato, pero es una solución creativa para un problema de entrevista, evita el problema de la memoria y técnicamente es O (n).

void maxNum(ulong filesize) { ulong bitcount = filesize * 8; //number of bits in file for (ulong i = 0; i < bitcount; i++) { Console.Write(9); } }

Debe imprimir 10 ^bitcount - 1 , que siempre será mayor que 2 ^bitcount . Técnicamente, el número que debe superar es 2 ^bitcount - (4 * 10 ⁹ - 1) , ya que sabe que hay (4 billones - 1) otros enteros en el archivo, e incluso con una compresión perfecta, ocuparán al menos un bit cada uno.

El enfoque más simple es encontrar el número mínimo en el archivo y devolver 1 menos que eso. Esto utiliza O (1) almacenamiento y O (n) tiempo para un archivo de n números. Sin embargo, fallará si el rango de números es limitado, lo que podría hacer que min-1 no sea un número.
El método simple y directo de usar un mapa de bits ya se ha mencionado. Ese método usa O (n) tiempo y almacenamiento.
También se ha mencionado un método de 2 pases con 2 ^ 16 cubos de conteo. Lee 2 * n enteros, por lo que usa O (n) tiempo y O (1) almacenamiento, pero no puede manejar conjuntos de datos con más de 2 ^ 16 números. Sin embargo, se puede extender fácilmente a (por ejemplo) 2 ^ 60 enteros de 64 bits ejecutando 4 pases en lugar de 2, y se adapta fácilmente a usar memoria pequeña usando solo tantos bins como caben en la memoria y aumentando el número de pases correspondientemente, en el tiempo de ejecución del caso ya no es O (n) sino que es O (n * log n).
El método de XOR''ing todos los números juntos, mencionado hasta ahora por rfrankel y en detalle por ircmaxell responde a la pregunta formulada en #35185 , como señala ltn100. Utiliza O (1) almacenamiento y O (n) tiempo de ejecución. Si por el momento asumimos enteros de 32 bits, XOR tiene un 7% de probabilidad de producir un número distinto. Justificación: dados ~ 4G distintos números XOR juntos, y ca. 300M no en el archivo, el número de bits establecidos en cada posición de bit tiene la misma probabilidad de ser par o impar. Por lo tanto, 2 ^ 32 números tienen la misma probabilidad de surgir que el resultado XOR, de los cuales el 93% ya está en el archivo. Tenga en cuenta que si los números en el archivo no son todos distintos, la probabilidad de éxito del método XOR aumenta.