Interview: Trouver des éléments similaires à partir de deux listes liées et renvoyer le résultat sous la forme d'une liste chaînée

Cette question a été posée lors d'une interview pour mon ami. L'enquêteur a demandé de trouver l'algorithme et le code en JavaInterview: Trouver des éléments similaires à partir de deux listes liées et renvoyer le résultat sous la forme d'une liste chaînée

Question: Trouver des éléments similaires à partir de deux listes chaînées et retourner le résultat sous la forme d'une liste chaînée

Par exemple: Si linkedlist1 a 1-> 2-> 3 -> 4-> 4-> 5-> 6 et linkedlist2 a 1-> 3-> 6-> 4-> 2-> 8

Liste liée résultante 1-> 2-> 3-> 4-> 6

Merci

Source

2010-12-15 SuperMan

amazon question d'interview? – zengr

Les listes seront-elles triées? – codaddict

@zengr Nope MSFT :), De toute façon les deux sociétés sont sur les mêmes lignes dans les questions d'entrevue;) – SuperMan

Que diriez-vous:

return new LinkedList(new LinkedHashSet(list1).retainAll(list2));

Cela préserve l'ordre comme dans list1. Bien sûr, quelqu'un pourrait se plaindre de cette triche, si le questionneur voulait dire que vous deviez construire l'algorithme vous-même, mais si la seule restriction était de le "coder en Java", alors c'est une solution valide (et probablement plus efficace et libre que la solution de bas niveau fabriquée à la main).

Source

2010-12-15 07:38:45

Bien!Mais il a probablement été invité à coder à partir de zéro. – fastcodejava

@Joonas Well interviewer a demandé un algorithme, puis le code :). Handy :) – SuperMan

Si la question était, comme écrit ci-dessus, "Question: Trouver des éléments similaires à partir de deux listes liées et renvoyer le résultat sous forme de liste chaînée", alors il n'a pas spécifiquement demandé un * algorithme *. –

Créez une table de hachage.
Parcourez la première liste de liens, marquez les entrées lorsque vous les visitez. O (N) Parcourez la deuxième liste de liens, notez les entrées (drapeau différent, etc.) lorsque vous les visitez. O (M)

Traverse la table de hachage et trouve toutes les entrées avec les deux membres LL. Créez de nouveaux membres LL lorsque vous trouvez des entrées. O (H)

totale Complexité: O (N) + O (M) + O (Max (N, H, M)) => O (N)

Note: réponse Edité pour Saurabh.

Source

2010-12-15 07:35:48 Jack

comment se fait-il que la complexité soit O (N), pouvez-vous expliquer? – TalentTuner

@Saurabh, la première traversée prend 'O (n)' heure, la seconde prend 'O (m)' heure et la troisième prend 'O (n + m)' heure. En supposant 'n = m', l'algorithme global est linéaire dans la taille des listes. –

Au lieu d'une table de hachage, tout ce dont vous avez besoin est un ensemble de hachage. –

obtenir la première liste chaînée et commencer à partir du premier élément, le comparer avec le premier élément de la deuxième liste chaînée, s'ils sont identiques, ajouter la valeur au résultat et passer au deuxième élément de la première liste, sinon le deuxième élément de la deuxième liste, faites ceci jusqu'à ce que les valeurs soient identiques ou que vous atteigniez la et de la deuxième liste.

Source

2010-12-15 07:47:31 nafiseh

o (n^2) solution. Très cher. – zengr

Utiliser HashSet pour l'heure constante contient une opération.

par la première Itérer liste et les ajouter à un HashSet --- O (n) (Note addding à HashSet est une constante de temps)

par seconde liste Itérer et si hashSet.contains puis les ajouter à une liste de résultats.

À la fin de la boucle, retournez la liste des résultats

Source

2011-11-10 12:28:21 Barry

Interview: Trouver des éléments similaires à partir de deux listes liées et renvoyer le résultat sous la forme d'une liste chaînée

Répondre

Questions connexes