J'ai des contacts stockés dans mon mobile. Disons que mes contacts sont lorsque je tape lettre maintenant je sais une lettre de plus concevoir et développer un programme pour cela. Ceci est la question de l'entrevue sur Samsung Mobile Development < / p> J'ai essayé de résoudre avec question est comment rechercher les contacts pour chaque lettre saisie de réutiliser les résultats de recherche de la recherche de la recherche ? Quelle structure de données et quelle algorithme doit être utilisée pour résoudre efficacement le problème. Je ne demande pas de programme. Un langage de programmation est donc immatériel pour moi. L'ordinateur apparaît comme une bonne solution. Est-ce que quelqu'un a une suggestion? solution doit être suffisamment rapide pendant un million de contacts. 'a' Je devrais obtenir tous les contacts correspondants disent "RAM, Feat, Manger, AT" . t . Maintenant, ma chaîne totale est "at" Mon programme doit maintenant réutiliser les résultats de la recherche précédente de "A" . Maintenant, il devrait me renvoyer "feat, manger, à" structures de données Trie . Impossible d'obtenir une bonne solution pour la réutilisation des résultats de chaîne déjà recherchés. J'ai également essayé une solution avec la structure de données de dictionnaire, la solution a le même désavantage que trie .
3 Réponses :
Cela dépend du nombre d'articles que vous recherchez. Si c'est une liste relativement petite, vous pouvez faire un puis les types d'utilisateurs "T" et recherchez séquentiellement les résultats renvoyés précédents: P> string.Contains code> Vérifiez tout. Ainsi, lorsque l'utilisateur Type "A", vous recherchez la liste complète: r - ram
a - ram, feat, eat, a
m - ram
h - hello, hi
...
ra - ram
am - ram
...
at - feat, eat, at
...
etc.
Qu'est-ce que je pense faire est de garder une trace de la chaîne assortie jusqu'à présent. Supposons dans la première étape, nous identifions les cordes qui ont "A" en eux et nous gardons la trace des positions de "A". Puis à l'étape suivante, nous ne faisons que surtout sur ces cordes et au lieu de les chercher complet que nous recherchons uniquement occurrence de "T" comme le prochain caractère à "A", nous avons gardé la trace à l'étape précédente, etc.
Recherchez "Tree de suffixe généralisé", par ex. https://fr.wikipedia.org/wiki/generalized_suffix_tree . Pour une taille d'alphabet fixe Cette structure de données donne une solution optimale asymptotique pour trouver toutes les correspondances Z d'une sous-chaîne de longueur M dans un ensemble de cordes dans le temps O (Z + M). Ainsi, vous obtenez le même type de prestation que si vous limitez votre recherche aux correspondances du préfixe précédent. De plus, la structure est optimale O (n) espace et de la durée de construction où n est la longueur totale de tous vos contacts. Je crois que vous pouvez modifier la structure de sorte que vous ne trouviez que les k Strings contenant la sous-chaîne de l'heure O (k + m), mais en général, vous ne devriez probablement pas avoir trop de matchs par contact qui a une correspondance, donc cela peut donc pas même être nécessaire.
J'aime cette idée pour un grand ensemble de noms. Mais j'ai une question. Un arbre suffixe aiderait à identifier les sous-chaînes. Avons-nous besoin de mapper les sous-chaînes sur les mots originaux qui les ont générés? C'est à dire. Dans l'exemple, l'utilisateur a donné, il semblerait que nous devions générer des noms complets et non suffixants. Droit?
Je crois comprendre que l'arbre de suffixe trouve tous les emplacements des matchs (emplacements de la concaténation des contacts où chaque contact se termine par un symbole unique), de sorte que ces emplacements peuvent être mappés facilement en fonction de la position de départ de chaque contact de la concaténation. Pour déterminer quelles chaînes contiennent des matchs.
Ou peut-être déterminer quelle chaîne est déjà prise en charge par l'algorithme classique du suffixe généralisé de suffixe généralisée pour trouver les matchs dans un ensemble de chaînes. Cela semble probablement, mais je devrais revenir en arrière et lire les papiers pour être sûr.
Jon Bentley a eu un bel article dans le journal du Dr Dobb en avril 2001 qui a décrit un suffixe de temps et d'espace efficace Array (qui est très similaire dans le concept de suffixe). Je ne trouve pas le lien DDJ en ce moment, mais cela semble être une copie de l'article: collaboration.cmc.ec.gc.ca/science/rpn/biblio/ddj/website/...
Ah, voici l'article sur le site DDJ: drdobbs.com/architecture-and-design/algorithm-alley/...
Oui, ma compréhension est que les tableaux de suffixe peuvent être utilisés pour enregistrer un stockage sans sacrifier la performance asymptotique, bénéficiant d'une supercheuse supplémentaire.