Questions d'entretien DSA les plus fréquemment posées

Q : Comment inverser une liste chaînée ?

• Réponse : Inverser une liste chaînée implique de changer la direction de ses pointeurs afin que la liste commence au dernier élément et se termine au premier.
• Exemple : Entrée : 1 -> 2 -> 3 -> 4 -> nul Sortie : 4 -> 3 -> 2 -> 1 -> nul

Q : Comment effectuer une recherche binaire sur un tableau trié ?

• Réponse : la recherche binaire divise le tableau en deux à plusieurs reprises, vérifiant si l'élément du milieu correspond à la cible.
• Exemple : Entrée : Tableau [1, 3, 5, 7, 9], cible = 7 Sortie : 3 (indice de 7)
• Approche de la solution : vérifiez l'élément du milieu ; si c'est la cible, renvoie l'index. Si la cible est plus petite, recherchez la moitié gauche ; s'il est plus grand, recherchez la moitié droite.

Q : Comment trouver le premier caractère unique dans une chaîne ?

• Réponse : Pour trouver le premier caractère unique, comptez les occurrences de chaque personnage et identifiez le premier qui n'apparaît qu'une seule fois.
• Exemple : Saisie : "Suisse" Sortie : "w"
• Approche de la solution : utilisez une carte de hachage pour stocker la fréquence de chaque caractère, puis parcourez la chaîne pour trouver le premier caractère avec un nombre de 1.

Q : Comment détecter un cycle dans une liste chaînée ?

• Réponse : Pour détecter un cycle dans une liste chaînée, utilisez deux pointeurs (lent et rapide). S'il y a un cycle, le pointeur rapide finira par rencontrer le pointeur lent.
• Exemple : Entrée : 1 -> 2 -> 3 -> 4 -> 2 (cycle) Sortie : Vrai (le cycle existe)
• Approche : utilisez l'algorithme de détection de cycle de Floyd. Déplacez le pointeur rapide de deux pas et le pointeur lent d'un pas. S’ils se rencontrent, il y a un cycle.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!