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 en 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 repeticiones mayor que 1

Por ejemplo: si la cadena era:123412345123456 entonces 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?