Les algorithmes sont l’ensemble des règles à suivre dans les calculs ou autres opérations de résolution de problèmes. Il est considéré comme l’un des sujets les plus importants considérés du level de vue de la programmation. En outre, l’un des sujets les plus complexes mais intéressants. Du level de vue de l’entretien, si vous souhaitez réussir un entretien de codage, vous devez maîtriser parfaitement Algorithmes et Buildings de données. Dans cet article, nous découvrirons certains des algorithmes les plus importants qui vous aideront à déchiffrer les entretiens de codage.
Il existe de nombreux algorithmes importants dont quelques-uns sont mentionnés ci-dessous :
- Algorithmes de tri
- Algorithmes de recherche
- Algorithmes de chaîne
- Diviser et conquérir
- Retour en arrière
- Algorithmes gourmands
- Programmation dynamique
- Algo lié aux arbres
- Algorithmes de graphe
- Autres algorithmes importants
1. Algorithmes de tri
Les algorithmes de tri sont utilisés pour organiser les données dans un ordre spécifique et utiliser les mêmes données pour obtenir les informations requises. Voici quelques-uns des algorithmes de tri qui sont les meilleurs en ce qui concerne le temps nécessaire pour trier les données.
A. Tri à bulles
Le tri à bulles est l’algorithme de tri par permutation le plus basique. Il proceed à échanger toutes les paires adjacentes qui ne sont pas dans le bon ordre. L’algorithme de tri à bulles, puisqu’il evaluate toutes les paires adjacentes, prend O(N2) temps.
Tri à bulles est un algorithme de tri secure. Il a également un espace O (1) pour le tri. Dans tous les cas (Finest, Common, Worst case), Sa la complexité temporelle est O(N2). Le tri à bulles n’est pas un algorithme très efficace pour les grands ensembles de données.
B. Tri par insertion
Comme son nom l’indique, c’est un algorithme d’insertion. Un élément est choisi et inséré dans sa place correcte dans un tableau. C’est aussi easy que de trier des cartes à jouer. Le tri par insertion est efficace pour les petits ensembles de données. Il faut généralement SUR2) temps. Mais lorsque les éléments sont triés, il faut À temps.
C. Tri de sélection
Dans tri par sélection, nous conservons deux events du tableau, une partie triée et une autre partie non triée. Nous sélectionnons le plus petit élément (si nous considérons l’ordre croissant) de la partie non triée et le plaçons au début de ce tableau non trié, et nous continuons à le faire et nous obtenons ainsi le tableau trié. La complexité temporelle du tri par sélection est SUR2).
D. Tri par fusion
Le tri par fusion est un algorithme de tri basé sur la division pour mieux régner. Cet algorithme proceed de diviser le tableau en deux moitiés jusqu’à ce que tous les éléments soient indépendants, puis il begin à fusionner les éléments dans un ordre trié. Tout ce processus prend O(nlogn) temps, O(log2(n)) temps pour diviser le tableau, et Sur) le temps de fusionner.
Tri par fusion est un algorithme de tri secure. Il prend également l’espace O (n) pour le tri. Dans tous les cas (Finest, Common, Worst case), sa complexité en temps est O(nlogn). Le tri par fusion est un algorithme très efficace pour les ensembles de données volumineux, mais pour les ensembles de données plus petits, il est un peu plus lent que le tri par insertion.
E. Tri rapide
Tout comme le tri par fusion, le tri rapide est également basé sur l’algorithme diviser pour mieux régner. Dans le tri rapide, nous choisissons un élément pivot et divisons le tableau en deux events en prenant l’élément pivot comme level de division.
La complexité temporelle de Tri rapide est O(nlogn) sauf pour le pire des cas qui peut être aussi mauvais que O(n2). Afin d’améliorer sa complexité temporelle dans le pire des cas, nous utilisons Algorithme de tri rapide aléatoire. Dans lequel, nous choisissons l’élément pivot comme index aléatoire.
2. Algorithmes de recherche
A. Recherche linéaire
Recherche linéaire est une méthode de recherche naïve. Il begin dès le début et proceed de chercher jusqu’à ce qu’il atteigne la fin. Cela prend un temps O(n). C’est une méthode très importante pour rechercher quelque selected dans des données non triées.
B. Recherche binaire
La recherche binaire est l’un des algorithmes de recherche les plus efficaces. Cela ne fonctionne que dans les données triées. Il tourne dans O(log2(n)) temps. Il divise à plusieurs reprises les données en deux moitiés et recherche dans chaque partie en fonction des situations.
Recherche binaire peut être implémenté en utilisant à la fois la méthode itérative et la méthode récursive.
Approche itérative :
binarySearch(arr, x, low, excessive)
repeat until low = excessive
mid = (low + excessive)/2
if (x == arr(mid))
return mid
else if (x > arr(mid)) // x is on the best aspect
low = mid + 1
else // x is on the left aspect
excessive = mid - 1
Approche récursive :
binarySearch(arr, x, low, excessive)
if low > excessive
return False
else
mid = (low + excessive) / 2
if x == arr(mid)
return mid
else if x > arr(mid) // x is on the best aspect
return binarySearch(arr, x, mid + 1, excessive) // recall with the best half solely
else // x is on the left aspect
return binarySearch(arr, x, low, mid - 1) // recall with the left half solely
3. Algorithme de chaîne
Algorithme de A. Rabin Karp
Le Algorithme de Rabin-Karp est l’un des algorithmes les plus demandés pour coder les interviews en chaînes. Cet algorithme nous aide efficacement à trouver les occurrences d’une sous-chaîne dans une chaîne. Supposons que nous recevions une chaîne S et que nous devions trouver le nombre d’occurrences d’une sous-chaîne S1 dans S, nous pouvons le faire en utilisant l’algorithme de Rabin Karp. Complexité temporelle de Rabin Karp dans laquelle la complexité moyenne est O(m+n) et la complexité dans le pire des cas est O(nm). Où n est la longueur de la chaîne S et m est la longueur de la chaîne S1.
Algorithme B.Z
L’algorithme Z est encore meilleur que l’algorithme de Rabin Karp. Cela aide également à trouver le nombre d’occurrences d’une sous-chaîne dans une chaîne donnée mais en temps linéaire O(m+n) dans tous les cas (meilleur, moyen et pire). Dans cet algorithme, nous construisons un tableau Z qui contient une valeur Z pour chaque caractère de la chaîne. La complexité temporelle moyenne de la Algorithme Z est O(n+m) et la complexité spatiale moyenne est également O(n+m). Où n est la longueur de la chaîne S et m est la longueur de la chaîne S1.
4. Diviser pour mieux régner
Comme son nom l’indique, il est d’abord divisé en sous-problèmes plus petits, puis ces sous-problèmes sont résolus et plus tard, ces problèmes sont combinés pour obtenir la answer finale. Il y a tellement d’algorithmes importants qui fonctionnent sur le Diviser et conquérir stratégie.
Voici quelques exemples d’algorithmes Divide and Conquer :
5. Retour en arrière
Retour en arrière est une variante de la récursivité. Dans le retour en arrière, nous résolvons le sous-problème avec quelques changements un à la fois et supprimons ce changement après avoir calculé la answer du problème à ce sous-problème. Il faut toutes les combinaisons possibles de problèmes pour les résoudre.
Il y a quelques questions normal sur le retour en arrière comme mentionné ci-dessous :
6. Algorithme gourmand
UN algorithme gourmand est une méthode de résolution de problèmes avec l’possibility la plus optimale disponible. Il est utilisé dans de telles conditions où l’optimisation est requise, c’est-à-dire lorsque la maximisation ou la minimisation est requise.
Certains des problèmes les plus courants avec les algorithmes gourmands sont les suivants –
7. Programmation dynamique
Programmation dynamique est l’un des algorithmes les plus importants qui est demandé dans le codage des entretiens. La programmation dynamique fonctionne sur la récursivité. C’est une optimisation de la récursivité. La programmation dynamique peut être appliquée à tous ces problèmes, où nous devons résoudre un problème en utilisant ses sous-problèmes. Et la answer finale est dérivée des options de sous-problèmes plus petits. Il stocke essentiellement les options des sous-problèmes et utilise simplement le résultat stocké chaque fois que nécessaire, malgré le fait de calculer la même selected encore et encore.
Certaines des questions très importantes basées sur la programmation dynamique sont les suivantes :
8. Algorithmes de traversée d’arbres
Il existe principalement trois sorts de traversée algorithmes :
A. Traversée dans l’ordre
- Traversez le sous-arbre de gauche, puis
- Le nœud racine traverse, puis
- Traverser le sous-arbre droit
B. Traversée de pré-commande
- Le nœud racine traverse, puis
- Traverser le nœud gauche, puis
- Traverser le sous-arbre droit
C. Traversée post-commande
- Traversez le sous-arbre de gauche, puis
- Traversez le sous-arbre droit, puis
- Traverser le nœud racine
9. Algorithmes basés sur des graphes
A. Recherche étendue d’abord (BFS)
Recherche en largeur d’abord (BFS) est utilisé pour parcourir les graphes. Il begin à partir d’un nœud (nœud racine dans les arbres et n’importe quel nœud aléatoire dans les graphiques) et traverse le niveau, c’est-à-dire que dans cette traversée, il traverse tous les nœuds du niveau actuel, puis tous les nœuds du niveau suivant. Ceci est également appelé parcours par niveau.
La mise en œuvre de l’approche est mentionnée ci-dessous :
- Nous créons une file d’attente et poussons le nœud de départ du graphe.
- Ensuite, nous prenons un tableau visité, qui garde une hint de tous les nœuds visités jusqu’à présent.
- Tant que la file d’attente n’est pas vide, nous continuons à effectuer les tâches suivantes :
- Faites éclater le premier élément de la file d’attente, visitez-le et poussez tous ses éléments adjacents dans la file d’attente (qui ne sont pas encore visités).
B. Recherche en profondeur (DFS)
Recherche en profondeur d’abord (DFS) est aussi une méthode pour parcourir un graphe. Partant d’un sommet, il parcourt en profondeur. L’algorithme begin à partir d’un nœud (nœud racine dans les arbres et n’importe quel nœud aléatoire dans les graphes) et discover autant que attainable le lengthy de chaque branche avant de revenir en arrière.
L’approche consiste à itérer récursivement tous les nœuds non visités, jusqu’à ce que tous les nœuds soient visités. La mise en œuvre de l’approche est mentionnée ci-dessous :
- Nous créons une fonction récursive, qui s’appelle elle-même avec le sommet et le tableau visité.
- Visitez le nœud actuel et insérez-le dans la réponse.
- Maintenant, parcourez tous ses nœuds adjacents non visités et appelez la fonction pour chaque nœud qui n’est pas encore visité.
Algorithme de C. Dijkstra
Algorithme de Dijkstra est utilisé pour trouver le chemin le plus courtroom de tous les sommets à partir d’un nœud supply dans un graphe qui a tous les poids d’arête positifs. L’approche de l’algorithme est mentionnée ci-dessous :
- Tout d’abord, conservez un tableau non visité de la taille du nombre complete de nœuds.
- Maintenant, prenez le nœud supply et calculez les longueurs de chemin de tous les sommets.
- Si la longueur du chemin est inférieure à la longueur précédente, mettez à jour cette longueur, sinon continuez.
- Répétez le processus jusqu’à ce que tous les nœuds soient visités.
Algorithme de D. Floyd Warshall
Salle de guerre Flyod L’algorithme est utilisé pour calculer le chemin le plus courtroom entre chaque paire de sommets dans les graphes pondérés avec des arêtes positives uniquement. L’algorithme utilise une answer DP. Il proceed de relâcher les paires de sommets qui ont été calculées. La complexité temporelle de l’algorithme est O(V3).
E. Algorithme de Bellman-Ford
Algorithme de Bellman Ford est utilisé pour trouver les chemins les plus courts de tous les autres nœuds à partir d’un sommet supply. Cela peut être fait avidement en utilisant l’algorithme de Dijkstra mais l’algorithme de Dijkstra ne fonctionne pas pour le graphe avec des arêtes négatives. Ainsi, pour les graphes avec des poids négatifs, l’algorithme de Bellman Ford est utilisé pour trouver le chemin le plus courtroom de tous les autres nœuds à partir d’un nœud supply. La complexité temporelle est O(V*E).
10. Autres algorithmes importants
A. Algorithmes binaires
Ces algorithmes effectuent des opérations sur les bits d’un nombre. Ces algorithmes sont très rapides. Il existe de nombreuses opérations au niveau du bit telles que And (&), OR ( | ), XOR ( ^ ), l’opérateur de décalage à gauche ( << ), l'opérateur de décalage à droite (>>), and so on. Les opérateurs de décalage à gauche sont utilisés pour multiplier un nombre par 2 et les opérateurs de décalage à droite ( >> ), sont utilisés pour diviser un nombre par 2. Voici quelques-uns des problèmes normal qui sont fréquemment posés dans les entretiens de codage-
- Échanger des bits dans les nombres
- Élément supérieur suivant avec le même nombre de bits définis
- Algorithmes de Karatsuba pour la multiplication
- Masquage de bits avec programmation dynamique
et beaucoup plus…..
B. La tortue et le lièvre
L’algorithme de la tortue et du lièvre est l’un des algorithmes les plus utilisés de Linked Checklist. Il est également connu sous le nom d’algorithme de Floyd. Cet algorithme est utilisé pour –
- Trouver le milieu de la liste chaînée
- Détecter un cycle dans la liste chaînée
Dans cet algorithme, nous prenons deux pointeurs sur la liste chaînée et l’un d’eux se déplace avec une vitesse double (lièvre) que l’autre (tortue). L’idée est que si elles se croisent à un second donné, cela prouve qu’il y a un cycle dans la liste chaînée.
Algorithme C. Kadane
L’algorithme de Kadane est utilisé pour trouver la somme maximale d’un sous-tableau contigu dans le tableau donné avec des nombres positifs et négatifs.
Instinct:
- Continuez à mettre à jour une variable de somme en ajoutant les éléments du tableau.
- Chaque fois que la somme devient négative, mettez-la à zéro.
- Continuez à maximiser la somme dans une nouvelle variable appelée somme_max
- En fin de compte, le somme_max sera la réponse.
