Table des matières[Cacher][Montrer]
- 1. Comment définit-on un Array ?
- 2. Tableaux dynamiques : que sont-ils ? Qu'est-ce qui les différencie des Basic Arrays ?
- 3. Comment un tableau et un dictionnaire diffèrent-ils l'un de l'autre ?
- 4. Énumérez certains des avantages et des inconvénients des baies.
- 5. À quoi fait référence « Sparse Array » ?
- 6. Quand choisiriez-vous une liste chaînée plutôt qu'un tableau ?
- 7. Qu'est-ce qui distingue un tableau indexé d'un tableau associatif ?
- 8. Quels sont les avantages de Heap par rapport aux tableaux triés ?
- 9. Pouvons-nous définir la taille du tableau comme étant négative ?
- 10. Comment localisez-vous l'entier manquant dans un tableau de 1 à 100 éléments ?
- 11. Comment trouve-t-on l'index d'un élément dans un tableau ?
- 12. Comment se débarrasser d'un élément spécifique d'un tableau ?
- 13. Comment vérifier l'égalité de deux tableaux ?
- 14. Lorsque nous parlons de tableaux, qu'entendez-vous par les expressions "Dimension" et "Indice" ?
- Codage des questions d'entrevue
- 15. Cherchez une paire dans un tableau qui a la somme spécifiée
- 16. Tri de tableaux binaires avec temps linéaire
- 17. Trouvez le plus grand produit à deux entiers dans un tableau.
- 18. Comment déplacer tous les zéros du tableau à la fin
- 19. Comment trier un tableau avec deux entrées commutées en une seule opération.
- 20. Comment combiner deux tableaux triés en place.
- 21. Comment réorganiser un tableau d'articles en alternant positions hautes et basses ?
- 22. Comment remplacer chaque élément d'un tableau sans utiliser d'opérateur de division par le produit de chaque élément du tableau ?
- 23. Trouver l'élément le plus impair d'un tableau en temps logarithmique
- 24. Comment obtenir le plus grand élément suivant pour chaque élément d'un tableau circulaire ?
- 25. Trouver le nombre d'inversions d'un tableau ?
- 26. Qu'est-ce que le problème de piégeage de l'eau de pluie ?
- Conclusion
Les entretiens de codage contiennent une série de questions DSA. Vous devriez être habile avec les baies si vous vous préparez pour votre prochain entretien technique avec FAANG ou une autre entreprise technologique de niveau 1.
Dans la plupart des entretiens de codage, il vient en deuxième position après Strings. Un tableau est un groupement d'éléments de données liés conservés à proximité les uns des autres en mémoire.
Comme ils sont connectés à tous les langages de programmation, tels que C, C++, Java, Python, Perl et Ruby, ils sont partout. Continuez à lire pour découvrir des défis de codage et des questions et réponses d'entretien basées sur des tableaux.
Python sera utilisé dans cet article pour résoudre les problèmes de codage car il est simple à utiliser, à comprendre et doit être familier à la plupart d'entre nous.
Commençons.
1. Comment définit-on un Array ?
- Un groupe de types de données associés est un tableau.
- Les tableaux sont toujours fixes.
- Le même type de variable est stocké à plusieurs endroits par des objets tableau.
- Les types primitifs et les références d'objet sont tous deux compatibles avec lui.
2. Tableaux dynamiques : que sont-ils ? Qu'est-ce qui les différencie des Basic Arrays ?
La mise à l'échelle automatique fournie par les tableaux dynamiques (également appelés tableaux évolutifs, tableaux redimensionnables, tableaux modifiables ou ArrayLists en Java) est un avantage significatif.
Vous devez toujours savoir combien d'éléments votre tableau stockera à l'avance puisque les tableaux ont une taille fixe. Un tableau dynamique, en revanche, s'agrandit à mesure que vous y ajoutez des membres supplémentaires, vous n'avez donc pas besoin de connaître sa taille exacte au préalable.
3. Comment un tableau et un dictionnaire diffèrent-ils l'un de l'autre ?
Il s'agit d'un ensemble de questions d'entretien basées sur les fondamentaux qui sont régulièrement posées. Voici les principales distinctions entre les tableaux et les dictionnaires :
- Un tableau est une liste ordonnée d'éléments similaires. Le dictionnaire, en revanche, a des paires clé-valeur.
- La taille des tableaux peut changer dynamiquement. De telles idées dynamiques n'existent pas dans les dictionnaires.
- Avant d'utiliser un tableau, sa taille doit être spécifiée. Les tailles de dictionnaire n'ont pas besoin d'être personnalisées.
- Utilisez l'instruction Redim si vous souhaitez étendre la taille du tableau. Dans les dictionnaires, un élément peut être ajouté sans déclaration.
4. Énumérez certains des avantages et des inconvénients des baies.
Avantages:
- Les tableaux peuvent trier plusieurs éléments simultanément.
- Autre structures de données, comme des piles, des files d'attente, des listes chaînées, des arbres, des graphiques, etc., peuvent être implémentés dans un tableau.
- Un index peut être utilisé pour atteindre un élément d'un tableau.
Désavantages:
- La taille d'un tableau doit être déclarée à l'avance. Au moment de la déclaration du tableau, nous pourrions cependant ne pas être conscients de la taille dont nous avons besoin.
- La structure du tableau est statique. Cela implique que la taille du tableau est toujours fixe et que l'allocation de mémoire ne peut pas être augmentée ou diminuée.
5. À quoi fait référence « Sparse Array » ?
Un tableau clairsemé est un tableau de données contenant de nombreuses entrées avec des valeurs nulles. En revanche, un tableau dense contient la majorité de ses éléments avec des valeurs non nulles. Les indices d'un tableau clairsemé, qui convertit les nombres en objets, peuvent inclure des espaces. Par rapport à un HashMap, ils sont plus économes en mémoire.
6. Quand choisiriez-vous une liste chaînée plutôt qu'un tableau ?
Lorsque vous utilisez des listes chaînées au lieu de tableaux, considérez :
- Vous n'avez besoin d'aucun élément pour avoir un accès aléatoire.
- Lorsque la prévisibilité temporelle est essentielle, vous avez besoin d'insertions et de suppressions à temps constant de la liste.
- Afin de créer une file d'attente prioritaire, vous devrez peut-être placer des éléments au centre de la liste.
- Vous n'avez aucune idée de la longueur de la liste. Si la taille du tableau augmente, vous devez re-déclarer et dupliquer la mémoire, comme avec les tableaux simples.
7. Qu'est-ce qui distingue un tableau indexé d'un tableau associatif ?
Les principales distinctions entre les tableaux associatifs et indexés sont répertoriées dans le tableau suivant.
- Une paire clé-valeur au format texte ou numérique est utilisée pour trier un tableau associatif. Les clés du tableau indexé sont toutes numériques et chaque clé est connectée à une valeur distincte.
- Dans un tableau associatif, la clé peut être une chaîne. Tableau indexé avec des clés entières commençant à 0.
- Un tableau à deux colonnes imite le comportement d'un tableau associatif. Les tableaux indexés sont similaires à un tableau à une seule colonne.
- Les cartes sont un type de tableau associatif. Un tableau d'index n'est pas une carte.
8. Quels sont les avantages de Heap par rapport aux tableaux triés ?
L'efficacité temporelle de l'utilisation de Heap over Sorted Arrays est le principal avantage. Bien que les opérations de tas soient plus rapides, le tri d'un tableau nécessite beaucoup de temps. Un tas peut découvrir le plus petit élément beaucoup plus rapidement qu'un tableau ne peut être trié.
Une collection donnée de nombres peut être organisée de deux manières à l'aide de tableaux triés. D'autre part, pour une collection donnée de nombres, il peut y avoir plus d'un tas potentiel.
9. Pouvons-nous définir la taille du tableau comme étant négative ?
Non, nous ne pouvons pas définir un entier négatif comme étant la taille d'un tableau. Il n'y aura pas d'erreur de compilation si nous déclarons. Au moment de l'exécution, nous rencontrerons cependant une NegativeArraySizeException.
10. Comment localisez-vous l'entier manquant dans un tableau de 1 à 100 éléments ?
Le total de la série peut être calculé en appliquant la fonction suivante : n (n + 1) / 2
Cette fonction ne fonctionnera que si le tableau n'a pas de doublons ou s'il manque plus d'un entier. Si un tableau a des éléments en double, vous pouvez trier le tableau pour voir s'il y a des éléments qui sont équivalents.
11. Comment trouve-t-on l'index d'un élément dans un tableau ?
L'index d'un élément peut être découvert via une recherche linéaire ou binaire. Jusqu'à ce qu'elle localise la correspondance de l'élément requis, une fonction de recherche linéaire boucle sur chaque élément d'un tableau. Il renvoie l'index une fois qu'il a localisé l'élément correspondant. Par conséquent, la complexité temporelle de la recherche linéaire est O. (n). Un tableau trié et un tableau non trié peuvent utiliser la recherche linéaire.
En utilisant une recherche binaire, qui divise continuellement le tableau en deux jusqu'à ce que la médiane de l'intervalle corresponde à l'élément requis et fournisse l'index, vous pouvez obtenir l'index de l'élément si le tableau est trié. Par conséquent, la complexité temporelle de la recherche binaire est O. (log n).
12. Comment se débarrasser d'un élément spécifique d'un tableau ?
Étant donné que vous ne pouvez pas simplement supprimer des éléments du tableau d'origine puisqu'il s'agit d'ensembles fixes avec une taille définie, l'intervieweur vous demande de suggérer une approche différente et de traiter le problème soulevé par la question. La meilleure solution consiste à créer un nouveau tableau afin de supprimer un élément. Vous pouvez dupliquer les éléments du premier tableau dans ce tableau et n'inclure que l'élément que vous souhaitez supprimer.
Une autre stratégie consiste à trouver l'élément cible dans le tableau, puis à inverser l'ordre de tous les éléments qui se trouvent à droite de l'élément cible.
13. Comment vérifier l'égalité de deux tableaux ?
Vous devez d'abord vérifier les longueurs des deux tableaux fournis. Les éléments correspondants des deux tableaux sont comparés lorsque leurs longueurs sont égales. Les deux tableaux seront considérés comme égaux. si chaque paire de composants dans chaque correspondance est égale. Cette approche n'est pas conseillée pour vérifier l'égalité de deux tableaux si les tableaux sont de grande taille car cela prendra beaucoup de temps. Vous pouvez également utiliser la méthode equals () incluse dans la classe Arrays, cependant, si l'intervieweur vous demande de comparer deux tableaux sans utiliser de méthodes intégrées, cette méthode sera utile.
14. Lorsque nous parlons de tableaux, qu'entendez-vous par les expressions "Dimension" et "Indice" ?
La « dimension » d'un tableau est le nombre d'indices, ou d'indices, requis pour identifier chaque membre individuel. Les indices et les dimensions peuvent ne pas être clairs. Une dimension est une description de la plage de clés autorisées, tandis qu'un indice est un nombre. Il n'y a qu'un seul indice requis pour chaque dimension de tableau.
Par exemple, le tableau arr[10][5] a deux dimensions. Tailles 10 sur l'un et 5 sur l'autre. Pour adresser ses composants, vous avez besoin de deux indices. Les deux sont compris entre 0 et 4 ; un entre 0 et 9 inclus.
Codage des questions d'entrevue
15. Cherchez une paire dans un tableau qui a la somme spécifiée
Par exemple,
Contribution:
- nombres = [8, 7, 2, 5, 3, 1]
- cible = 10
Sortie :
- Paire trouvée (8, 2)
- Or
- Paire trouvée (7, 3)
Contribution:
- nombres = [5, 2, 6, 8, 1, 9]
- cible = 12
Sortie :
- Paire introuvable
16. Tri de tableaux binaires avec temps linéaire
Trier un tableau binaire en temps linéaire et dans une zone fixe. La sortie doit d'abord afficher tous les zéros, puis tous les uns.
Par exemple,
- Entrée : { 1, 0, 1, 0, 1, 0, 0, 1 }
- Sortie : { 0, 0, 0, 0, 1, 1, 1, 1 }
Une approche simple serait de calculer le nombre total de 0 du tableau, disons k, puis de remplir les k premiers indices du tableau avec des 0 et les indices restants avec 1. Comme alternative, nous pourrions calculer combien de 1 sont au total dans le tableau k, remplissez les k derniers indices du tableau avec 1 et laissez le reste des indices remplis avec 0.
L'approche donnée a une complexité temporelle O (n) et n'utilise aucun stockage supplémentaire, où n est la taille de l'entrée.
17. Trouvez le plus grand produit à deux entiers dans un tableau.
Trouver le plus grand produit de deux nombres dans un tableau d'entiers.
Pensez au tableau 10 3 5 6 2 comme exemple. La paire (-10, -3) ou (5, 6) est le produit le plus élevé.
Penser à chaque combinaison d'éléments et comprendre leur produit est une approche insensée. Si le produit de la paire actuelle est supérieur au produit maximum obtenu jusqu'à présent, mettez à jour le produit maximum. Imprimez les composants du produit final en dernier.
La solution ci-dessus, où n est la quantité d'entrée, a une complexité temporelle de O(n2) et ne prend plus de place.
18. Comment déplacer tous les zéros du tableau à la fin
Déplacez tous les zéros d'un tableau d'entiers vers la fin. La réponse doit éviter d'utiliser un espace constant et préserver l'ordre relatif des composants du tableau.
Entrée: {1,2,3,0,8,0,4,7}
La sortie sera {1,2,3,8,4,7,0,0}
Placez l'élément à la position disponible suivante dans le tableau si l'élément actuel n'est pas zéro. Remplissez tous les index restants avec 0 une fois que les éléments du tableau ont tous été traités.
La solution précédente a une complexité temporelle O(n), où n est la taille de l'entrée.
19. Comment trier un tableau avec deux entrées commutées en une seule opération.
Trier un tableau dans le temps linéaire étant donné deux éléments échangés et un tableau avec tous ses éléments disposés par ordre croissant. Imaginez que le tableau ne contient pas de doublons.
Entrée := [1,9,3,4,7,2] ou [9,3,7,2,1,4] ou [2,4,1,7,3,9]
Sortie : = [1,2,3,4,7,9]
En commençant par le deuxième élément du tableau, l'objectif est de comparer chaque élément à son prédécesseur. La position du litige est stockée en prenant deux pointeurs, x et y.
Met à jour x à l'index de l'élément précédent et y à l'index de l'élément actuel si le premier est plus grand que le second. Mettez à jour y à l'index de l'élément courant s'il s'avère que l'élément précédent est supérieur à l'élément courant.
Enfin, changez les éléments aux indices x et y une fois que nous avons fini de traiter chaque paire d'éléments adjacents.
Du fait que la méthode précitée n'effectue qu'un seul parcours du tableau d'entrée de taille n, sa complexité temporelle est O(n). Aucune pièce supplémentaire n'est nécessaire pour la solution.
20. Comment combiner deux tableaux triés en place.
Fusionner les éléments des tableaux X[] et Y[]—deux tableaux triés de taille m et n chacun—en conservant l'ordre de tri, c'est-à-dire en remplissant X[] avec les m premiers éléments les plus petits et en remplissant Y[] avec les éléments restants.
Si un élément du tableau X[] est déjà à la bonne position (c'est-à-dire celui qui est le plus petit parmi les éléments restants), ignorez-le ; sinon, remplacez-le par le plus petit élément, qui se trouve être également le premier membre de Y[]. Pour conserver l'ordre trié après l'échange, transférez l'élément (maintenant à Y[0]) à son emplacement approprié dans Y[].
La taille du premier tableau est m et la taille du second tableau est n, et la complexité temporelle est O(mn).
21. Comment réorganiser un tableau d'articles en alternant positions hautes et basses ?
Réorganisez un tableau d'entiers afin que chaque membre suivant soit plus grand que les éléments précédents et suivants. Supposons que le tableau n'inclut aucun élément en double.
Le tri du tableau ou l'utilisation d'espace supplémentaire n'est pas nécessaire pour une approche efficace. Le plan est, pour commencer, le deuxième membre du tableau et augmente de deux à chaque itération de boucle.
Échangez les composants si le dernier élément dépasse le premier. Dans le même ordre d'idées, changez les deux éléments si l'élément suivant est plus grand que l'élément actuel. Nous obtiendrons le tableau souhaité qui respecte les restrictions spécifiées à la fin de la boucle.
22. Comment remplacer chaque élément d'un tableau sans utiliser d'opérateur de division par le produit de chaque élément du tableau ?
Sans utiliser l'opérateur de division, remplacez chaque élément d'un tableau d'entiers par le produit de tous les autres éléments.
En temps linéaire et en espace constant, nous pouvons utiliser la récursivité pour résoudre ce problème. Calculer récursivement les produits de chaque élément dans le sous-tableau droit et transmettre le produit du sous-tableau gauche comme paramètres de fonction est la notion.
La complexité temporelle est O(n).
23. Trouver l'élément le plus impair d'un tableau en temps logarithmique
Étant donné un tableau d'entiers dans lequel tous les membres sauf un ont un nombre pair d'occurrences, le problème est de déterminer combien de fois cet élément apparaît. Trouvez l'élément apparaissant impair dans le temps logarithmique et l'espace constant si les mêmes éléments apparaissent par paires dans le tableau et qu'il ne peut jamais y avoir plus de deux instances d'un élément donné dans une rangée.
L'opération XOR nous permet de résoudre ce problème en temps linéaire. Le but est de XOR chaque élément du tableau. Seuls les éléments apparaissant impairs restent après que les éléments apparaissant pairs s'annulent.
Ce problème peut même être résolu en temps O(log(n)).
24. Comment obtenir le plus grand élément suivant pour chaque élément d'un tableau circulaire ?
L'élément le plus grand suivant pour chaque élément d'un tableau circulaire d'entiers doit être localisé. Le premier plus grand entier après un élément x dans le tableau est le plus grand élément suivant de cet élément.
De droite à gauche, nous pouvons opérer sur des éléments de tableau. Le but est de boucler pour chaque élément x jusqu'à ce que la pile soit vide ou que nous ayons un élément supérieur au-dessus. Définissez le prochain plus grand élément de x pour qu'il apparaisse au-dessus de la pile lorsqu'il apparaît.
25. Trouver le nombre d'inversions d'un tableau ?
Trouver le nombre total d'inversions d'un tableau. Une paire I j) est appelée inversion d'un tableau A si I j) et (A[i] > A[j]). Nous devons compter chaque paire de ceux-ci dans le tableau.
Compter tous les membres du tableau qui sont moins nombreux que lui à sa droite et ajouter le résultat à la sortie est une approche simple.
Cette solution a une complexité O(n2), où n est la taille de l'entrée.
26. Qu'est-ce que le problème de piégeage de l'eau de pluie ?
Trouver le plus d'eau qui peut être piégée dans un ensemble donné de barres d'une largeur d'une unité chacune est connu sous le nom de problème de « piégeage des précipitations ».
Le but est de déterminer la barre la plus haute qui peut être placée à gauche et à droite de chaque barre. Le minimum des barres de tête à gauche et à droite, moins la hauteur de la barre actuelle, est la quantité d'eau stockée au-dessus de chaque barre.
Conclusion
Par rapport à d'autres sujets de structure de données, les tableaux sont plus simples. Afin de réussir les questions d'entretien sur les tableaux, vous devez avoir une compréhension fondamentale des tableaux.
Vous devez revoir en détail les fondements des tableaux, y compris les opérations sur les tableaux (de la déclaration/création d'un tableau à l'accès/la modification des éléments du tableau), ainsi que les concepts de programmation tels que les boucles, la récursivité et les opérateurs de base afin de répondre avec succès aux questions d'entretien sur les tableaux. Reconnaissez complètement le problème.
Vous devriez demander des éclaircissements si vous avez des questions. Pensez à diviser le problème en parties plus gérables. Assurez-vous d'avoir l'algorithme à l'esprit avant de commencer la programmation ; notez-le ou visualisez-le dans un organigramme. puis commencez à écrire du code.
Soyez sympa! Laissez un commentaire