Vous vous en êtes tiré à bon compte, vous avez probablement Ne le fais pas. je veux travailler pour un fonds spéculatif où les quants ne comprennent pas les algorithmes de base :-)
Hay pas de manière de traiter une structure de données de taille arbitraire en O(1) si, comme dans ce cas, vous devez visiter chaque élément au moins une fois. Le site meilleur que vous pouvez espérer est O(n) dans ce cas, où n est la longueur de la chaîne.
Bien que, en passant, un nominal O(n) algorithme sera être O(1) pour une taille d'entrée fixe, donc, techniquement, ils peuvent avoir eu raison ici. Cependant, ce n'est généralement pas ainsi que les gens utilisent l'analyse de la complexité.
Il me semble que vous auriez pu les impressionner de plusieurs façons.
D'abord, en les informant que c'est no possible de le faire en O(1) sauf si vous utilisez le raisonnement "suspect" donné ci-dessus.
Deuxièmement, en montrant vos compétences d'élite en fournissant du code Pythonique tel que :
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])
Ces sorties :
[(123, 3), (234, 3), (345, 2)]
mais vous pouvez, bien sûr, modifier le format de sortie comme vous le souhaitez.
Et, finalement, en leur disant qu'il y a presque certainement pas de problème avec un O(n) puisque le code ci-dessus fournit des résultats pour une chaîne d'un million de caractères en moins d'une demi-seconde. L'échelle semble également être assez linéaire, puisqu'il faut 3,5 secondes pour une chaîne de 10 000 000 de caractères et 36 secondes pour une chaîne de 100 000 000 de caractères.
Et, s'ils besoin de Mieux encore, il existe des moyens de paralléliser ce genre de choses qui peuvent accélérer considérablement le processus.
Pas dans un simple L'interpréteur Python bien sûr, en raison de la GIL, mais vous pourriez diviser la chaîne en quelque chose comme (chevauchement indiqué par vv est nécessaire pour permettre un traitement correct des zones limites) :
vv
123412 vv
123451
5123456
Vous pouvez confier ces tâches à des travailleurs distincts et combiner les résultats par la suite.
Le fractionnement de l'entrée et la combinaison de la sortie risquent d'annihiler toute économie avec les petites chaînes de caractères (et peut-être même les chaînes de caractères à un million de chiffres) mais, pour les ensembles de données beaucoup plus importants, cela peut faire une différence. Mon mantra habituel de "mesure, ne devine pas" s'applique ici, bien sûr.
Ce mantra s'applique également à otros des possibilités, telles que le contournement total de Python et l'utilisation d'un autre langage qui peut être plus rapide.
Par exemple, le code C suivant, qui s'exécute sur le même matériel que le code Python précédent, traite un fichier cent millions de chiffres en 0,6 seconde, soit à peu près le même temps que le code Python a traité un million. En d'autres termes, beaucoup plus rapide :
#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;
}
