Dada una cadena de un millón de números, devuelve todos los números de 3 dígitos que se repiten

Tuve una entrevista con una compañía de fondos de cobertura en Nueva York hace unos meses y, desafortunadamente, no obtuve la oferta de pasantía como ingeniero de datos / software. (También pidieron que la solución estuviera en Python).

Casi arruine el problema de la primera entrevista …

Pregunta: Dado una cadena de un millón de números (por ejemplo, Pi), escriba una función / progtwig que devuelva todos los números repetidos de 3 dígitos y el número de repeticiones mayor que 1

Por ejemplo: si la cadena era: 123412345123456 entonces la función / progtwig devolvería:

 123 - 3 times 234 - 3 times 345 - 2 times 

No me dieron la solución después de que fallara la entrevista, pero sí me dijeron que la complejidad del tiempo para la solución era constante de 1000 ya que todos los resultados posibles se encuentran entre:

000 -> 999

Ahora que lo estoy pensando, no creo que sea posible crear un algoritmo de tiempo constante. ¿Lo es?

Se salió a la ligera, es probable que no quiera trabajar para un fondo de cobertura donde los cuantos no entienden los algoritmos básicos 🙂

No hay manera de procesar una estructura de datos de tamaño arbitrario en O(1) si, como en este caso, necesita visitar cada elemento al menos una vez. Lo mejor que puedes esperar es O(n) en este caso, donde n es la longitud de la cadena.

Aunque, aparte, un algoritmo O(n) nominal será O(1) para un tamaño de entrada fijo, por lo que, técnicamente, pueden haber sido correctos aquí. Sin embargo, no suele ser así como las personas utilizan el análisis de complejidad.

Me parece que podría haberlos impresionado de varias maneras.

Primero, informándoles que no es posible hacerlo en O(1) , a menos que use el razonamiento “sospechoso” que se indica anteriormente.

En segundo lugar, mostrando sus habilidades de élite al proporcionar un código Pythonic como:

 inpStr = '123412345123456' # O(1) array creation. freq = [0] * 1000 # O(n) string processing. for val in [int(inpStr[pos:pos+3]) for pos in range(len(inpStr) - 2)]: freq[val] += 1 # O(1) output of relevant array values. print ([(num, freq[num]) for num in range(1000) if freq[num] > 1]) 

Esto produce:

 [(123, 3), (234, 3), (345, 2)] 

aunque podría, por supuesto, modificar el formato de salida a cualquier cosa que desee.

Y, finalmente, al decirles que es casi seguro que no hay problema con una solución O(n) , ya que el código anterior ofrece resultados para una cadena de un millón de dígitos en menos de medio segundo. Parece que la escala también es bastante lineal, ya que una cadena de 10,000,000 caracteres toma 3.5 segundos y una de 100,000,000 caracteres toma 36 segundos.

Y, si necesitan algo más que eso, hay formas de paralelizar este tipo de cosas que pueden acelerarlo enormemente.

Por supuesto, no dentro de un solo intérprete de Python, debido a la GIL, pero podría dividir la cadena en algo parecido (se requiere superposición indicada por vv para permitir el procesamiento adecuado de las áreas de límite):

  vv 123412 vv 123451 5123456 

Puede distribuirlos a trabajadores separados y combinar los resultados después.

Es probable que la división de entrada y la combinación de salida inunden cualquier ahorro con cadenas pequeñas (y posiblemente cadenas de un millón de dígitos) pero, para conjuntos de datos mucho más grandes, puede marcar la diferencia. Mi mantra habitual de “medir, no adivinar” se aplica aquí, por supuesto.


Este mantra también se aplica a otras posibilidades, como omitir Python por completo y usar un lenguaje diferente que puede ser más rápido.

Por ejemplo, el siguiente código C, que se ejecuta en el mismo hardware que el código Python anterior, maneja cien millones de dígitos en 0,6 segundos, aproximadamente la misma cantidad de tiempo que el código Python procesó un millón. En otras palabras, mucho más rápido:

 #include  #include  int main(void) { static char inpStr[100000000+1]; static int freq[1000]; // Set up test data. memset(inpStr, '1', sizeof(inpStr)); inpStr[sizeof(inpStr)-1] = '\0'; // Need at least three digits to do anything useful. if (strlen(inpStr) <= 2) return 0; // Get initial feed from first two digits, process others. int val = (inpStr[0] - '0') * 10 + inpStr[1] - '0'; char *inpPtr = &(inpStr[2]); while (*inpPtr != '\0') { // Remove hundreds, add next digit as units, adjust table. val = (val % 100) * 10 + *inpPtr++ - '0'; freq[val]++; } // Output (relevant part of) table. for (int i = 0; i < 1000; ++i) if (freq[i] > 1) printf("%3d -> %d\n", i, freq[i]); return 0; } 

El tiempo constante no es posible. Todos los 1 millón de dígitos deben considerarse al menos una vez, por lo que es una complejidad de tiempo de O (n), donde n = 1 millón en este caso.

Para una solución O (n) simple, cree una matriz de tamaño 1000 que represente el número de ocurrencias de cada número posible de 3 dígitos. Avance 1 dígito a la vez, el primer índice == 0, el último índice == 999997 y la matriz de incrementos [número de 3 dígitos] para crear un histogtwig (recuento de ocurrencias para cada número posible de 3 dígitos). Luego, muestre el contenido de la matriz con conteos> 1.

La solución simple O (n) sería contar cada número de 3 dígitos:

 for nr in range(1000): cnt = text.count('%03d' % nr) if cnt > 1: print '%03d is found %d times' % (nr, cnt) 

Esto buscaría a través de todos los 1 millón de dígitos 1000 veces.

Atravesando los dígitos una sola vez:

 counts = [0] * 1000 for idx in range(len(text)-2): counts[int(text[idx:idx+3])] += 1 for nr, cnt in enumerate(counts): if cnt > 1: print '%03d is found %d times' % (nr, cnt) 

El tiempo muestra que la iteración de una sola vez sobre el índice es dos veces más rápida que usar el count .

Un millón es pequeño por la respuesta que doy a continuación. Solo esperando que pueda ejecutar la solución en la entrevista, sin pausa, lo siguiente funciona en menos de dos segundos y proporciona el resultado requerido:

 from collections import Counter def triple_counter(s): c = Counter(s[n-3: n] for n in range(3, len(s))) for tri, n in c.most_common(): if n > 1: print('%s - %i times.' % (tri, n)) else: break if __name__ == '__main__': import random s = ''.join(random.choice('0123456789') for _ in range(1_000_000)) triple_counter(s) 

Esperemos que el entrevistador esté buscando el uso de las colecciones de bibliotecas estándar. Clase de encuentro.

Versión de ejecución paralela

Escribí una publicación de blog sobre esto con más explicación.

Aquí hay una implementación NumPy del algoritmo O (n) de “consenso”: recorra todos los trillizos y el contenedor a medida que avanza. El binning se realiza al encontrar, por ejemplo, “385”, agregando uno al bin [3, 8, 5] que es una operación O (1). Los contenedores están dispuestos en un cubo de 10x10x10 . Como el binning está completamente vectorizado, no hay ningún bucle en el código.

 def setup_data(n): import random digits = "0123456789" return dict(text = ''.join(random.choice(digits) for i in range(n))) def f_np(text): # Get the data into NumPy import numpy as np a = np.frombuffer(bytes(text, 'utf8'), dtype=np.uint8) - ord('0') # Rolling triplets a3 = np.lib.stride_tricks.as_strided(a, (3, a.size-2), 2*a.strides) bins = np.zeros((10, 10, 10), dtype=int) # Next line performs O(n) binning np.add.at(bins, tuple(a3), 1) # Filtering is left as an exercise return bins.ravel() def f_py(text): counts = [0] * 1000 for idx in range(len(text)-2): counts[int(text[idx:idx+3])] += 1 return counts import numpy as np import types from timeit import timeit for n in (10, 1000, 1000000): data = setup_data(n) ref = f_np(**data) print(f'n = {n}') for name, func in list(globals().items()): if not name.startswith('f_') or not isinstance(func, types.FunctionType): continue try: assert np.all(ref == func(**data)) print("{:16s}{:16.8f} ms".format(name[2:], timeit( 'f(**data)', globals={'f':func, 'data':data}, number=10)*100)) except: print("{:16s} apparently crashed".format(name[2:])) 

Como era de esperar, NumPy es un poco más rápido que la solución Python pura de @ Daniel en grandes conjuntos de datos. Salida de muestra:

 # n = 10 # np 0.03481400 ms # py 0.00669330 ms # n = 1000 # np 0.11215360 ms # py 0.34836530 ms # n = 1000000 # np 82.46765980 ms # py 360.51235450 ms 

Solucionaría el problema de la siguiente manera:

 def find_numbers(str_num): final_dict = {} buffer = {} for idx in range(len(str_num) - 3): num = int(str_num[idx:idx + 3]) if num not in buffer: buffer[num] = 0 buffer[num] += 1 if buffer[num] > 1: final_dict[num] = buffer[num] return final_dict 

Aplicado a su cadena de ejemplo, esto produce:

 >>> find_numbers("123412345123456") {345: 2, 234: 3, 123: 3} 

Esta solución se ejecuta en O (n), siendo n la longitud de la cadena provista, y es, supongo, lo mejor que puede obtener.

Según mi entendimiento, no puede tener la solución en un tiempo constante. Tomará al menos una pasada sobre el número de un millón de dígitos (asumiendo que es una cadena). Puede tener una iteración sucesiva de 3 dígitos sobre los dígitos del número de longitud del millón y boost el valor de la clave hash en 1 si ya existe o crear una nueva clave hash (inicializada por el valor 1) si no existe ya en el diccionario.

El código se verá algo así:

 def calc_repeating_digits(number): hash = {} for i in range(len(str(number))-2): current_three_digits = number[i:i+3] if current_three_digits in hash.keys(): hash[current_three_digits] += 1 else: hash[current_three_digits] = 1 return hash 

Puede filtrar hasta las claves que tienen un valor de elemento mayor que 1.

Como se mencionó en otra respuesta, no puede hacer este algoritmo en tiempo constante, porque debe mirar al menos n dígitos. El tiempo lineal es lo más rápido que puedes conseguir.

Sin embargo, el algoritmo se puede hacer en el espacio O (1). Solo necesita almacenar los conteos de cada número de 3 dígitos, por lo que necesita una matriz de 1000 entradas. A continuación, puede transmitir el número en.

Mi conjetura es que o bien el entrevistador habló mal cuando le dieron la solución, o bien no escuchó “tiempo constante” cuando dijo “espacio constante”.

Aquí está mi respuesta:

 from timeit import timeit from collections import Counter import types import random def setup_data(n): digits = "0123456789" return dict(text = ''.join(random.choice(digits) for i in range(n))) def f_counter(text): c = Counter() for i in range(len(text)-2): ss = text[i:i+3] c.update([ss]) return (i for i in c.items() if i[1] > 1) def f_dict(text): d = {} for i in range(len(text)-2): ss = text[i:i+3] if ss not in d: d[ss] = 0 d[ss] += 1 return ((i, d[i]) for i in d if d[i] > 1) def f_array(text): a = [[[0 for _ in range(10)] for _ in range(10)] for _ in range(10)] for n in range(len(text)-2): i, j, k = (int(ss) for ss in text[n:n+3]) a[i][j][k] += 1 for i, b in enumerate(a): for j, c in enumerate(b): for k, d in enumerate(c): if d > 1: yield (f'{i}{j}{k}', d) for n in (1E1, 1E3, 1E6): n = int(n) data = setup_data(n) print(f'n = {n}') results = {} for name, func in list(globals().items()): if not name.startswith('f_') or not isinstance(func, types.FunctionType): continue print("{:16s}{:16.8f} ms".format(name[2:], timeit( 'results[name] = f(**data)', globals={'f':func, 'data':data, 'results':results, 'name':name}, number=10)*100)) for r in results: print('{:10}: {}'.format(r, sorted(list(results[r]))[:5])) 

El método de búsqueda de matrices es muy rápido (incluso más rápido que el método numpy de @ paul-panzer). Por supuesto, hace trampa ya que no se termina técnicamente después de que se completa, porque está devolviendo un generador. Tampoco tiene que verificar cada iteración si el valor ya existe, lo que probablemente ayude mucho.

 n = 10 counter 0.10595780 ms dict 0.01070654 ms array 0.00135370 ms f_counter : [] f_dict : [] f_array : [] n = 1000 counter 2.89462101 ms dict 0.40434612 ms array 0.00073838 ms f_counter : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] f_dict : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] f_array : [('008', 2), ('009', 3), ('010', 2), ('016', 2), ('017', 2)] n = 1000000 counter 2849.00500992 ms dict 438.44007806 ms array 0.00135370 ms f_counter : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] f_dict : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] f_array : [('000', 1058), ('001', 943), ('002', 1030), ('003', 982), ('004', 1042)] 

Imagen como respuesta:

LA IMAGEN COMO RESPUESTA

Parece una ventana corrediza.

Aquí está mi solución:

 from collections import defaultdict string = "103264685134845354863" d = defaultdict(int) for elt in range(len(string)-2): d[string[elt:elt+3]] += 1 d = {key: d[key] for key in d.keys() if d[key] > 1} 

Con un poco de creatividad en for loop (y una lista de búsqueda adicional con True / False / None, por ejemplo), debería poder deshacerse de la última línea, ya que solo desea crear claves en el dict que visitamos una vez hasta ese momento . Espero eso ayude 🙂

-Dirigir desde la perspectiva de C. -Usted puede tener una matriz de resultados en 3-d int [10] [10] [10]; -Vaya de la ubicación 0 a la ubicación n-4th, donde n es el tamaño de la matriz de cadenas. -En cada ubicación, marque la actual, la siguiente y la siguiente. -Incrementar el cntr como resutls [current] [next] [next’s next] ++; -Imprimir los valores de

 results[1][2][3] results[2][3][4] results[3][4][5] results[4][5][6] results[5][6][7] results[6][7][8] results[7][8][9] 

-Es tiempo O (n), no hay comparaciones involucradas. -Puedes ejecutar algunas cosas paralelas aquí dividiendo la matriz y calculando las coincidencias alrededor de las particiones.

 inputStr = '123456123138276237284287434628736482376487234682734682736487263482736487236482634' count = {} for i in range(len(inputStr) - 2): subNum = int(inputStr[i:i+3]) if subNum not in count: count[subNum] = 1 else: count[subNum] += 1 print count