J'ai récemment rencontré cette question dans une interview. Je n'ai pas été vraiment capable de trouver une réponse à cela. J'ai commencé avec, prenez le premier élément de première matrice, puis trouvez combien d'éléments sont supérieurs à cet élément dans l'autre tableau. Mais alors, je veux dire, je ne sais pas, ne pouvait pas vraiment former une solution. Le problème est le suivant:
donné deux tableaux triés A et B, générer tous les tableaux possibles de telle sorte que le premier élément est extrait d'A puis de B puis de A et ainsi de suite dans une commande croissante jusqu'à ce que les tableaux épuisés. Les matrices générées devraient se terminer par un élément de b. Je ne cherche pas un code, juste un code algo / pséduo ferait bien. Merci!
4 Réponses :
Que diriez-vous d'utiliser un graphique dirigé avec une recherche BFS de chemins.
par suggestion par @miljenmikic, vous pouvez exploiter le fait que les matrices sont triées en accélérant l'étape 1. Vous n'avez pas à rechercher tous les éléments de l'autre matrice pour trouver plusieurs éléments. Gardez simplement une trace de la dernière trouvée et déplacez le pointeur en avant pendant votre recherche.
solution BFS que @DPMCMLXXVI proposé est intéressant. De plus, je suggérerais une variante récursive. Quelques points de base:
Les matrices sont triées - utilisez cette information! Lorsque vous voyez des tableaux de tri, pensez toujours à Recherche binaire - dans ce cas, vous devez passer de manière récursive dernier élément ajouté, puis, dans l'autre tableau, recherche binaire du premier élément supérieur à ce dernier élément
Si le dernier élément ajouté était de B, ajoutez la matrice de travail en cours à la liste résultante
Quelle est la complexité temporelle de cette solution? O (n * m) où N & M sont des longueurs des deux tableaux?
@YeshwanthvenKatesh en fait, dans le pire des cas lorsque des éléments alternaient (c'est-à-dire un [i]
Une solution basée sur Java simple récursive peut être comme celle-ci
Désolé, je suis un peu paresseux d'écrire l'algorithme, mais vous pouvez le conduire du code. Vous trouverez ci-dessous ma solution que vous pouvez l'utiliser
Demandez toujours à l'intervieweur de vous fournir une feuille de réponses suggérées par la suite.
Qu'est-ce qu'une feuille de réponses suggérée? : /
Ce qu'ils sentent que votre réponse devrait aborder. Plus que souvent, les gens ne peuvent même pas résoudre les problèmes qu'ils posent.
Oh! À droite. Je garderai cela à l'esprit à partir de la prochaine fois. Beau bout. Merci! Mais comme je suis juste un débutant en ce moment, cela ne sera-t-il pas offensant à l'intervieweur? Ne peut-il pas dire juste, répondit juste à la question posée. Je ne faisais que demander.
@John Donc, le premier numéro doit toujours être à partir de 1er tableau?
Cela dépend vraiment. Ce n'est pas une question triviale. Pas trop difficile, mais je dirais assez fort pour un débutant. S'ils refusent, dites-leur que vous aimeriez apprendre des erreurs possibles et avoir une référence pour vous comparer. S'ils trouvent cette offensive, je les trouverais offensant. (J'ai eu des entretiens où ils m'ont demandé de résoudre des problèmes qu'ils n'avaient pas de réponses. Certains ont fini par nécessiter une expérience mathématique post-diplômée ... quelque chose qu'ils sauraient que je n'avais pas eu si elles regardaient mon CV et ont élaboré le problème eux-mêmes. .)
@karthik, oui le premier numéro sera toujours du premier tableau.
@leppie, droite. Bien que, il existe une grande variété de personnes avec leurs propres esprits et on ne peut jamais deviner ce qui pourrait sortir comme offensant pour les autres, mais oui, ce qui précède semble raisonnable. Merci pour le conseil. :)
Pourquoi
{10,20,25} et{15,20,25} non inclus dans votre exemple résultat?@ גגעד ברקן Ces deux entrées n'ont pas été incluses dans le résultat car le dernier élément doit toujours être de B (qui n'a pas 25).
@Saigudigundla merci, j'ai raté cela.