java-comprendre les questions d'entrevue LinkedList avec des nœuds
Je lis actuellement en train de craquer l'interview de codageet de regarder des questions sur leetcode et j'ai rencontré la même confusion aux deux endroits. En particulier avec les problèmes LinkedList, qui impliquent souvent l'utilisation de nœuds et la création d'implémentations de classes personnalisées de listes chaînées. Maintenant, je comprends ce qu'est une LinkedList et comment chaque élément est appelé un "nœud", etc. Mais ce niveau semble être un niveau trop bas lorsque vous travaillez réellement avec la structure de données java LinkedList et est ce qui me cause de la confusion.
Tout cela a-t-il réellement à voir avec l'api java Collections List/ LinkedList? il ne semble pas si. Par exemple, si je recherche l'API LinkedList pour "node", je n'obtiens même pas un seul hit.
Prenez la question leetcode suivante:
On vous donne deux listes chaînées non vides représentant deux listes non négatives entier. Les chiffres sont stockés dans l'ordre inverse, et chacun de leurs les nœuds contiennent un seul chiffre. Ajoutez les deux nombres et renvoyez-les comme un liste liée.
Vous pouvez supposer que les deux nombres ne contiennent aucun zéro principal, sauf le nombre 0 lui-même.
Exemple
Entrée: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Sortie: 7 -> 0 -> 8
Explication: 342 + 465 = 807.
Après avoir lu ce problème, je suis allé sur mon tableau blanc et j'ai codé une solution. Comme vous pouvez l'imaginer, quand je suis allé comparer ma réponse à la solution, j'ai été immédiatement choqué car mon code différait de la solution en première ligne!
J'ai écrit ce qui suit:
public LinkedList<Integer> addLinkedLists(LinkedList<Integer> l1, LinkedList<Integer> l2)
Et la solution était la suivante:
public ListNode addTwoNumbers(ListNode l1, ListNode l2)
Veuillez expliquer ce qui me semble manquer. Pourquoi la solution ne reçoit-elle pas une structure de données LinkedList réelle? La question indique clairement de renvoyer une LinkedList, mais elle renvoie un ListNode implémenté personnalisé. Il me semble manquer une compréhension de base de ce qui a été demandé.
Question sur leetcode: https://leetcode.com/problems/add-two-numbers/description/
3 answers
Cela n'a rien à voir avec le Java intégré LinkedList, sauf dans le concept.
Une des choses qu'ils enseignent dans la programmation 101 (ou quel que soit son nom), c'est comment les listes liées fonctionnent en général.
Elles commencent généralement par des listes à liens simples, comme illustré sur Wikipedia, et couvriront ensuite d'autres types de listes liées, telles que les listes à liens doubles (c'est ainsi que le LinkedList intégré est implémenté). Voir l'article Wikipedia pour la liste complète des liens types de liste (section 3).
Dans une liste liée individuellement, la liste est composée de nœuds, chacun avec un value et une référence à la next nœud. Dans une implémentation de liste complète, les nœuds sont internes à une classe List (comme c'est fait par LinkedList), mais pour les implémentations simples/précoces, seule la classe ListNode existe et une liste est représentée par la référence au "head" / premier nœud de la liste.
C'est ce type de liste trop simple avec lequel les questions fonctionnent. Si vous voulez vous "casser la entretien de codage " pour ce faible niveau de programmation, vous devriez étudier comment les listes chaînées fonctionnent en interne.
Vous pouvez lire cet article Wikipedia ou rechercher sur le Web du matériel sur les listes chaînées en Java.
Bien que la réponse @Andreas soit bonne, et plus à un niveau supérieur, mon malentendu semble être que je ne suis pas familier avec le fonctionnement du leetcode et que l'appareil sur lequel j'ai consulté la question rendait la partie "Soumettre la solution" pas facilement perceptible. Mon erreur était de penser que c'était une question autonome. Je n'ai pas remarqué ce qui suit en bas de la page, ce qui implique comment répondre à la question:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
}
}
Dans l'interview, l'intervieweur ne vous dira pas à quoi ressemble la signature de la fonction. Vous devrez décider de la signature de la fonction en fonction de la question d'entrevue (Bien sûr, l'interviewé devrait discuter avec l'intervieweur avant d'écrire le code).
Pour ce problème, LinkedList est une boîte noire, avec seulement quelques Api à utiliser. Donc, boucler la liste prendra réellement O (n ^ 2). Puisque pour chaque élément, vous devrez commencer par la tête ou la queue et vous déplacer étape par étape vers le désiré position. Cependant, avec ListNode il y a beaucoup plus de liberté, vous pouvez donc boucler la liste à O(n), ce qui est également la complexité temporelle optimisée pour ce problème.