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

Me equivoqué bastante con el primer problema de la entrevista ...

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

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

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

No me dieron la solución después de que fallé 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 están entre:

000 -> 999

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

Saliste a la ligera, probablemente no quieras estar trabajando para un fondo de cobertura donde los quants no entienden los algoritmos básicos :-)

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

Aunque, en un aparte, un valor nominal O(n)algoritmo va a ser O(1)de un tamaño fijo de entrada por lo que, técnicamente, que pueden haber sido correcto en este caso. Sin embargo, no suele ser así como las personas usan el análisis de complejidad.

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

En primer lugar, informándoles que es no es posible hacerlo en O(1), a menos que utilice el "sospechoso" razonamiento expuesto anteriormente.

En segundo lugar, al mostrar 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 lo que desee.

Y, finalmente, al decirles que casi con seguridad no hay problema con una O(n)solució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 escalar también de manera 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 mejor que eso, hay formas de paralelizar este tipo de cosas que pueden acelerarlo enormemente.

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

    vv
123412  vv
    123451
        5123456

Puede cultivarlos para separar a los trabajadores y luego combinar los resultados.

Es probable que la división de la entrada y la combinación de la salida empañen cualquier ahorro con cadenas pequeñas (y posiblemente cadenas de incluso millones de dígitos) pero, para conjuntos de datos mucho más grandes, bien puede hacer la diferencia. Mi mantra habitual de "medir, no adivinar" se aplica aquí, por supuesto.

Este mantra también se aplica a otras posibilidades, como evitar 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 <stdio.h>
#include <string.h>

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 observarse al menos una vez, por lo que es una complejidad temporal 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 posible número de 3 dígitos. Avance 1 dígito a la vez, primer índice == 0, último índice == 999997 e incremente la matriz [número de 3 dígitos] para crear un histograma (recuento de ocurrencias para cada posible número de 3 dígitos). Luego, muestre el contenido de la matriz con conteos> 1.

Un millón es pequeño para la respuesta que doy a continuación. Esperando solo que debe poder ejecutar la solución en la entrevista, sin pausa, entonces lo siguiente funciona en menos de dos segundos y da 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 contadores.

Versión de ejecución paralela

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

La solución simple de 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 todos los 1 millón de dígitos 1000 veces.

Recorriendo los dígitos solo una 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 iterar solo una vez sobre el índice es dos veces más rápido que usarlo count.

Aquí hay una implementación NumPy del algoritmo de "consenso" O (n): recorra todos los tripletes y bin a medida que avanza. El binning se realiza al encontrar, digamos "385", agregando uno al bin [3, 8, 5] que es una operación O (1). Los contenedores están dispuestos en un 10x10x10cubo. Como el binning está completamente vectorizado, no hay 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

Resolverí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) porque n es la longitud de la cadena proporcionada y es, supongo, lo mejor que puede obtener.

Según tengo entendido, 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 (suponiendo que sea una cadena). Puede tener una iteración continua de 3 dígitos sobre los dígitos del número de millones de longitud y aumentar el valor de la clave hash en 1 si ya existe o crear una nueva clave hash (inicializada por el valor 1) si aún no existe en el diccionario.

El código se verá 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 a las teclas 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 puede obtener.

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

Supongo que o bien el entrevistador habló mal cuando le dieron la solución, o usted escuchó mal el "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 matriz es muy rápido (¡incluso más rápido que el método numpy de @paul-panzer!). Por supuesto, hace trampa ya que no está técnicamente terminado 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 ayudará 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:

Parece una ventana deslizante.

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 el bucle for (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 dict que visitamos una vez hasta ese momento . Espero eso ayude :)

-Dirigiendo desde la perspectiva de C. -Puede tener una matriz int 3-d resultados [10] [10] [10]; -Vaya de la ubicación 0 a la ubicación n-4, donde n es el tamaño de la matriz de cadenas. -En cada ubicación, verifique la siguiente, la siguiente y la siguiente. -Incremente el cntr como resultados [actual] [siguiente] [siguiente es el siguiente] ++; -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 hora (n), no hay comparaciones involucradas. -Puede ejecutar algunas cosas paralelas aquí al particionar la matriz y calcular 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