7
votes

Algorithme efficace perl ou python

Intervieweur a posé une question dans une interview d'écrire un algorithme rapide et efficace pour la fonction ci-dessous,

Problème: Écrivez une fonction pour analyser une chaîne donnée pour les règles ci-dessous et produire une chaîne analysée finale à la sortie

Écrivez une fonction qui acceptera la chaîne en tant qu'entrée, la longueur de la chaîne se situe entre [0..2000000000]

String doit être fabriqué à partir de 'A' 'A', 'B' & 'C' Personnages J'aime 'AAA', 'ABCABC', 'AAAABBBBABAAACCCA'
Règles de transformation:

1) 'AB' -> 'AA'
2) 'AC' -> 'AA'
3) 'AA' -> 'A'
4) 'CC' -> 'C'
5) 'BC' -> 'BB'
6) 'BB' -> 'B'

Appliquer toutes les 6 règles ci-dessus sur une chaîne donnée chacune à la fois et faire une chaîne transformée finale en tant que sortie
par exemple entrée à la fonction est la suivante: 'Abcaab' String
Abcaab -> AACAAB [AB = AA]
AACAAB -> Acaab [AA = A]
ACAAB -> AAAAB [AC = AA]
AAAAB -> AAAB [AA = A]
AAAB -> AAB [AA = A]
AAB -> AB [AA = A]
AB -> AA [AB = AA]
AA -> A [AA = A]

résultat final: 'a' de
Parce que nous ne pouvons appliquer plus de règles à la chaîne maintenant.
Ma réponse était comme (pseudocode): xxx
peut suggérer une meilleure algorithme et approche Pour le problème ci-dessus?

python algorithm perl

8 commentaires

... Et quelle est votre question / problème?

@Karoly: Veuillez suggérer une solution optimisée / algorithme pour le problème ci-dessus.

Comment le code ci-dessus "applique-t-il toutes les 7 règles au hasard"? Aussi (si cela ne doit pas être aléatoire), il ne serait pas plus efficace d'utiliser si d'autre (comme vous n'auriez pas besoin de la boucle tandis que)?

@ROB: J'ai écrit une boucle parce qu'ils m'ont dit d'appliquer une règle à la fois, nous ne pouvons donc pas utiliser l'identifiant global 'g' dans la correspondance des motifs. :(

Je suppose un tour: l'ordre des substitutions n'a pas d'importance.

Si le code fonctionne complètement, cela serait meilleur sur codereview.se

Pourquoi avez-vous ajouté Perl et Python aux tags?

@Izkata: parce que je connais à la fois Perl & Python :)

4 Réponses :

8
votes

Vous pouvez répéter la substitution lorsqu'il correspond à des règles de transformation, xxx
sortie xxx

4 commentaires

@ N33RMA Il n'y a aucun commutateur / g.

Laissez-moi essayer, merci beaucoup pour votre solution

Désolé je ne peux pas voter votre réponse, il est dit "Vous avez besoin de 15 réputation pour voter"

@ N33RMA: Vous pouvez maintenant voter. Vous avez suffisamment de réputation à UPVOTE :)

15
votes

Les règles 1 à 3 jettent n'importe quel caractère suivant un A.
Les règles 5 et 6 jetteront tous les B et C suivant un B.
La règle 4 jettera tout C Suivre un C. L'ordre des substitutions n'a pas d'importance.
Ainsi, après le traitement, la chaîne sera l'une des C, CB, CA, CBA, B, BA, A.
Un seul balayage de la chaîne suffira. Si vous voyez un C, gardez-le et sautez le prochain C; Ensuite, si vous voyez un B, conservez-le et sautez le prochain B; Ensuite, si vous voyez une garde et arrête.
L'exemple donné AbCaab donne immédiatement un.
solutions avec application explicite des règles et plusieurs passes sont inacceptables car leur comportement peut être O (n²) ou même o (n³) , tandis que n = 2000000000 .
4 commentaires Merci d'avoir fait tellement simple Je vous en prie. Voyant la longueur jusqu'à 200000000000 m'a allongé qu'il y avait un tour. Avez-vous une bonne idée de la façon de le mettre en œuvre? Dans ma réponse, j'utilise trouver () , car il est très rapide. Mais j'ai besoin de deux scans. Et je ne peux pas penser à une manière plus rapide qui scanne une seule fois. Trois si des tests et trois boucles. Sauf pour les cas pathologiques, la vitesse n'est pas un problème ici, l'analyse s'arrête au premier A.
1 votes Voici une solution Python: xxx 2 commentaires Merci beaucoup pour votre solution Oui j'ai essayé mais cela dit "Vous avez besoin de 15 réputation pour voter" désolé pour cela. 0 votes La réponse de Yves Daoust a raison de le simuler. On dirait une question d'astuce et que vous étiez censé réaliser cela et comprendre le comportement et la mettre en œuvre directement. la méthode Yves 'fonctionne, mais voici une implémentation réelle d'un similaire: xxx i recherchez le premier "A", puis recherchez une "B" à gauche de celui-ci (ou dans toute la chaîne, s'il n'y avait pas de 'A'). Cela me dit si "B" et "A" appartiennent à la sortie. Pour 'C', j'ai juste besoin de vérifier le début de la chaîne. Tandis que je balaye potentiellement la chaîne entière deux fois plutôt que simplement une fois que Yves suggère, à l'aide de la fonction Rechercher le rend assez rapide, environ 100 fois plus rapide que de boucler sur la chaîne "à la main" et à la recherche de Pour un 'A' (qui n'est qu'à la fin de mes testerstring): xxx Vous pouvez le faire avec une seule numérisation en utilisant lstrip ("c ' ) Pour trouver le premier caractère non-'C ', et c'est plus rapide que de le faire à la main, mais qui utilise une mémoire supplémentaire et reste beaucoup plus lent que (code>: < PRE> XXX Les expressions régulières pourraient probablement aussi le faire, mais même simplement scanner mon testant une fois que je cherche «A» prend plus de temps que tout mon transformer : < Pré> xxx 0 commentaires

Articles qui pourrait vous intéresser : Python: ConnectionError: HTTPSConnectionPool (hôte = 'api.foursquare-com', port = 443) L'exécution de Flask sous Windows n'exécute pas la commande d'exécution de flask Chatbot installé mais obtention d'une erreur lors de l'importation de ChatBot Administrateur Django: __str__ a renvoyé une non-chaîne (type int)